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 star-expansion four-family of a forest has the Erdős-Hajnal property
Statement
Let be a forest. Let be the star-expansion of , and let be the star-expansion of . Then the finite family
has the Erdős-Hajnal property.
Facts & Assumptions
Given: A forest .
Theorems 6.1 and 6.8 of the cited primary source prove exactly the displayed four-family result, with the critical exponent chosen after all blockade-length and width parameters.
Proof
The cited proof chooses the forest/blockade constants first and then chooses the critical exponent so the cograph-pattern blockade has the exact width required by the criticality theorem.
The alternative rainbow outcome supplies one of the four forbidden star-expansion graphs, while the quantitatively wide cograph outcome contradicts criticality. The source therefore proves exactly the stated four-family Erdős-Hajnal property.
Depends on
- The star-expansion of a graph
- A blockade-rainbow induced copy
- A long blockade yields a wide cograph-pattern subblockade or a rainbow forest
- A tau-critical graph with a large low-degree induced subgraph has a rooted stable-tooth comb
- A tau-critical graph has no wide pure blockade with cograph pattern
- A minimal counterexample to a kappa-bound is tau-critical
- An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree
- The Erdos-Hajnal property is equivalent to the large-cograph, large-perfect, and kappa formulations
Used by
Dependency tree · two levels
39 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, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdős-Hajnal for graphs with no 5-hole, Theorems 6.1 and 6.8 (standard reference, not scraped)
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Theorem 1.9 (standard reference, not scraped)