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 classes of complete graphs and of empty graphs have Erdős–Hajnal constant
Example
The hereditary class of all complete graphs and the hereditary class of all empty graphs both have Erdős–Hajnal constant .
Facts & Assumptions
Given: The classes of complete graphs and of empty graphs.
A positive exponent is a constant for a hereditary class when every nonempty member satisfies (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).
The homogeneous number is the maximum of the clique and stable-set numbers (Homogeneous vertex sets and the homogeneous number ).
A complete graph has every possible edge and an empty graph has none (Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
Complementary hereditary classes have exactly the same Erdős–Hajnal constants (A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants).
Verification
Both classes are hereditary because an induced subgraph of a complete graph is complete and one of an empty graph is empty.
Every nonempty in either class has all vertices homogeneous, as a clique in or a stable set in , so .
Hence and [L1] gives constant for both classes; equivalently, the result for one class transfers to the other by [L4].
Depends on
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
- Homogeneous vertex sets and the homogeneous number $\operatorname{hom}(G)=\max\{\omega(G),\alpha(G)\}$
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants
Used by
Nothing in the library uses this result yet.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 29 results over 9 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)