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.
Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph
Statement
Let be a leaf-reducible finite family of graphs. Then there exist constants and such that for every , every , and every -sparse -free graph , at least one of the following holds:
- there are disjoint sets with and anticomplete to ; or
- has a -restricted induced subgraph with at least vertices.
Facts & Assumptions
Given: A leaf-reducible finite family , parameters and , and a -sparse -free graph .
Because is leaf-reducible, there exist and a leaf such that has the Erdős-Hajnal property (Leaf-reducible finite graph families).
For a finite family, the Erdős-Hajnal property, the polynomial Rödl property, and virality are equivalent (For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent).
Deleting a leaf from each of two forbidden graphs preserves virality (Deleting a leaf from each of two forbidden graphs preserves virality).
A graph is -free when it contains no induced copy of any member of (-free and -free graphs under the induced-subgraph convention).
Proof
By [L1], fix and so that the modified family has the Erdős-Hajnal property. By the implication from assertion 1 to assertion 3 in [L2], the family is viral.
Apply [L3] with both leaf-deletion slots equal to the same graph and with the same leaf . The two modified families are both , so step 1.1 makes them viral. Therefore itself is viral. Using the implication from assertion 3 to assertion 2 in [L2], choose such that every -free graph has an -restricted induced subgraph on at least times its number of vertices for every . Set .
Since is -free by [L4], step 2.1 applies to with . We obtain a -restricted induced subgraph of with at least vertices. Since , one has , so this induced subgraph also has at least vertices. Hence outcome 2 holds.
Because outcome 2 always holds, the displayed dichotomy is satisfied.
Depends on
- Leaf-reducible finite graph families
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
- The induced-embedding count $\operatorname{ind}_H(G)$
- The viral property for a finite forbidden family
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent
- Deleting a leaf from each of two forbidden graphs preserves virality
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
22 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
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 2.7 (standard reference, not scraped)
- Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. IV. New graphs with the Erdős-Hajnal property, Theorem 6.1 (standard reference, not scraped)