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 perfect-induced-subgraph formulation of the Erdos-Hajnal conjecture
The survey literature repeatedly reformulates the Erdos-Hajnal conjecture as a claim about large perfect induced subgraphs. Concretely, for a family of finite graphs one may ask whether every nonempty -free graph contains an induced subgraph that is perfect and whose order is bounded below by a positive power of the ambient order (Perfect graphs, -free and -free graphs under the induced-subgraph convention, Subgraphs, induced subgraphs and spanning subgraphs).
The next theorem proves that this perfect-graph formulation is equivalent to the usual homogeneous-set formulation from The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, and also to the cograph and formulations used in the later blockade arguments.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Maria Chudnovsky, The Erdos-Hajnal Conjecture - A Survey, Conjecture 1.2 and the surrounding discussion (standard reference, not scraped)
- Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdos-Hajnal for graphs with no 5-hole, Introduction (standard reference, not scraped)