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 Bird graph has the Erdős-Hajnal property
Statement
There exists such that every nonempty finite simple graph with no induced copy of Bird has a clique or stable set of size at least . Equivalently the singleton family has the Erdős-Hajnal property.
Facts & Assumptions
Given: The singleton family and its class of Bird-free finite graphs.
The singleton family is generalized nice (The singleton Bird family is generalized nice).
The singleton family is leaf-reducible; deleting the added leaf gives the bull, and the reduced singleton family has the Erdős-Hajnal property (The -graph and Bird singleton families are leaf-reducible).
The singleton family is wonderful (The -graph and the Bird graph are wonderful).
Every generalized nice, leaf-reducible, wonderful finite family has the Erdős-Hajnal property (Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property).
A positive real is an Erdős-Hajnal constant for a hereditary class when every nonempty satisfies ; a graph has the Erdős-Hajnal property when its class of -free graphs has such a constant, and is the size of the largest clique or stable set of (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number ).
Graph is -free when it has no induced copy of (-free and -free graphs under the induced-subgraph convention), and the class of -free graphs is hereditary for every finite graph (Every class defined by forbidden induced subgraphs is hereditary).
The Bird graph has vertex set and edge set (The Bird graph and co-Bird).
Proof
The family satisfies the three hypotheses of [L4]: it is generalized nice by [L1], leaf-reducible by [L2], and wonderful by [L3].
By [L4], the family has the Erdős-Hajnal property: the hereditary class of Bird-free graphs has an Erdős-Hajnal constant .
Unwinding [L5] and using that the class of Bird-free graphs is hereditary by [L6], the constant satisfies for every nonempty Bird-free graph ; since , this says exactly that has a clique or stable set of size at least .
The first assertion of the statement is step 3.1; the equivalence with the singleton family having the Erdős-Hajnal property is the definitional reading [L5] of the class of Bird-free graphs, which by [L6] and [L7] is the class in which absence of an induced copy of Bird is required.
Remarks
- This is Theorem 1.11 of the source. The E theorem of the companion A-page item is used only through the preceding property- corollary for Bird, never as forward input; the dependency order is before Bird.
- As for the -graph, no numerical value of is claimed: the generic reduction yields an unspecified positive exponent.
- No Choice. The proof composes published finite reductions and makes no selection from a family of nonempty sets.
Depends on
- The singleton Bird family is generalized nice
- The $E$-graph and Bird singleton families are leaf-reducible
- The $E$-graph and the Bird graph are wonderful
- Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property
- 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)\}$
- The Bird graph and co-Bird
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- Every class defined by forbidden induced subgraphs is hereditary
Used by
Dependency tree · two levels
41 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, Theorem 1.11 and Section 6 (standard reference, not scraped)
- Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Section 5, restricted-set/blockade exponent mechanism (standard reference, not scraped)