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 singleton Bird family is generalized nice
Statement
The singleton finite family is generalized nice.
Facts & Assumptions
Given: The singleton family .
The singleton family has property , with its special-vertex comb trigger in co-Bird-free graphs (The singleton Bird family has property (*)).
The singleton family is leaf-reducible: deleting the added leaf from Bird gives the bull, and the reduced singleton family has the Erdős-Hajnal property (The -graph and Bird singleton families are leaf-reducible).
If a finite family has property and is leaf-reducible, then it is generalized nice (Property (*) and leaf reducibility imply generalized niceness).
Generalized niceness of a finite family is the four-outcome schema quantified over -free graphs (Generalized nice finite graph families).
Property for a finite family is a condition on -free graphs, and leaf-reducibility asks that deleting one leaf from one member produce a family with the Erdős-Hajnal property (Property (*) for a finite graph family, Leaf-reducible finite graph families).
co-Bird is the complement of the Bird graph (The Bird graph and co-Bird).
Proof
The family satisfies both hypotheses of [L3]: property by [L1] and leaf-reducibility by [L2].
Applying [L3] to the finite family gives that is generalized nice.
The ambient class of that generalized-niceness condition is the class of graphs free of by [L4] and [L6], and step 2.1 is exactly the assertion of the statement.
Remarks
- This is the direct specialization of the source's Lemma 4.5 to ; the companion E corollary is the analogous specialization to , and the two are independent instances of the same published implication.
- No Choice. The argument is finite and makes no selection from a family of nonempty sets.
Depends on
- The singleton Bird family has property (*)
- The $E$-graph and Bird singleton families are leaf-reducible
- Property (*) and leaf reducibility imply generalized niceness
- Generalized nice finite graph families
- Property (*) for a finite graph family
- The Bird graph and co-Bird
- Leaf-reducible finite graph families
Used by
Dependency tree · two levels
32 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 4.5 and Section 6.2 (standard reference, not scraped)