Alphabeta MathHow statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
Definition
Let be a hereditary class of finite graphs (Hereditary graph classes). A real number is an Erdős–Hajnal constant for if every nonempty satisfies where the homogeneous number is that of Homogeneous vertex sets and the homogeneous number and the power is that of Real powers for positive bases, with the zero-base positive-exponent convention. The class has the Erdős–Hajnal property if it has an Erdős–Hajnal constant.
For a finite graph , we say that has the Erdős–Hajnal property when the hereditary class of -free graphs has it. The same terminology applies to a finite family through its class of -free graphs.
Depends on
Used by
- Every graph on at most three vertices has the Erdős–Hajnal property Corollary
- The hereditary class of all finite graphs does not have the Erdős–Hajnal property Corollary
- Every hereditary graph class of bounded order has the Erdős–Hajnal property Example
- The classes of complete graphs and of empty graphs have Erdős–Hajnal constant 1 Example
- Every smaller positive exponent is again an Erdős–Hajnal constant Lemma
- A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants Proposition
- The Erdős–Hajnal property and each of its constants pass to hereditary subclasses Proposition
- The Erdős–Hajnal conjecture: every fixed forbidden induced graph admits a positive exponent Remark
- Every P₃-free graph G satisfies hom(G)≥√|V(G)| Theorem
- For every t≥1, the class of Kₜ-free graphs has the Erdős–Hajnal property Theorem
- The single-forbidden-graph and finite-nonempty-family formulations of the Erdős–Hajnal conjecture are equivalent Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 23 results over 6 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- M. Chudnovsky, The Erdos-Hajnal Conjecture: A Survey, sec. 1 (standard reference, not scraped)
- Erdos-Hajnal properties in graphs and hypergraphs, introduction (standard reference, not scraped)