How 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 structural comb-partition hypothesis
Definition
Let be finite families of finite graphs, and suppose that and have the Erdős–Hajnal property (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class). We say that satisfies the structural comb-partition hypothesis if the following universal assertion holds.
For every -free finite graph (Graph isomorphisms, automorphisms and graph complements, -free and -free graphs under the induced-subgraph convention) and every -comb in with (Combs in a graph), each has a partition such that:
- is -free;
- has a partition which is a pure blockade, its blocks being nonempty, whose pattern graph is -free (Complete, anticomplete, pure, weakly sparse, and -sparse blockades, The pattern graph of a pure blockade); and
- for every , every vertex of is pure to .
The quantifiers range over every ambient -free graph and every indicated comb, rather than fixing one graph from which a property of could not follow.
Depends on
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
- Combs in a graph
- The pattern graph of a pure blockade
- Complete, anticomplete, pure, weakly sparse, and $x$-sparse blockades
- Graph isomorphisms, automorphisms and graph complements
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
Used by
- A large Y-part in a structural comb partition yields the clique-or-stable-set outcome Lemma
- A transversal of wide structural blocks yields the pure blockade outcome Lemma
- A wide integral geometric layer forces the complete-or-anticomplete property-(*) blockade Lemma
- Failure of the first and third property-(*) outcomes forces one small-block structural partition Lemma
- The structural comb-partition criterion implies property (*) Theorem
Dependency tree · two levels
16 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
- Huang, Ju, and Zhou, Erdős–Hajnal beyond the five-vertex path, Lemma 5.1 (standard reference, not scraped)