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 -graph family is generalized nice
Statement
The singleton finite family is generalized nice, with the complement-family convention in the published definition.
Facts & Assumptions
Given: The singleton family and the complement family of the published generalized-niceness convention.
The singleton family has property (The singleton family has property (*)).
The family has the Erdős-Hajnal property, so it has an Erdős-Hajnal constant (The family consisting of and co- has the Erdős–Hajnal property).
Leaf/co-leaf transfer: if is a finite family, has a leaf , has a co-leaf , and the two modified families are and , then the Erdős-Hajnal property of both modified families implies it for (Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family).
In every co--free graph, every special-vertex comb of the property- trigger admits the structural partition: each block splits as with -free and carrying a nonempty-block pure blockade partition whose pattern is -free and whose blocks are pure to every vertex of the other comb blocks (A special-vertex comb in a co--free graph admits the structural partition).
Special-vertex-local criterion: if finite families have a common Erdős-Hajnal constant and every special-vertex comb in every -free graph admits a partition with clauses (1) and (2.1)--(2.3) of the structural comb partition, then has property (The special-vertex-local structural-partition criterion implies property (*)).
If a finite family has property and is leaf-reducible, then it is generalized nice (Property (*) and leaf reducibility imply generalized niceness).
The singleton family is leaf-reducible (The -graph and Bird singleton families are leaf-reducible).
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 carrying the special-vertex comb trigger (Property (*) for a finite graph family).
The -graph has edge set on six vertices, and co- is its complement (The -graph and co-).
A vertex is a co-leaf of a graph when , equivalently when is adjacent to every other vertex except one (Co-leaves of a finite graph).
If is an Erdős-Hajnal constant for a hereditary class and , then is one too (Every smaller positive exponent is again an Erdős–Hajnal constant).
Proof
By [L1], the singleton family has property . Since [L9] quantifies the trigger over graphs free of the complement family, and [L10] identifies that complement family as , the claim is a statement about co--free graphs.
By [L7], the singleton family is leaf-reducible.
The published proof behind [L1] is the instance of [L5] with : [L2] supplies the family's Erdős-Hajnal constant, lowered into by [L12], and [L4] supplies the partition clause for every special-vertex comb of a co--free graph. The induction step of the proof of [L2] replaces the family by the two families and , deleting from its pendant vertex and from co- the vertex ; here is a leaf of by the edge list [L10], so it has degree in the six-vertex graph co- and is a co-leaf of co- by [L11]. That replacement is exactly the transfer [L3], so every load-bearing input of the property- claim of step 1.1 is a published library item, with the transfer explicitly [L3].
Applying [L6] to the finite family : property holds by step 1.1 and leaf-reducibility by step 1.2, so is generalized nice.
By [L8] the ambient class of the generalized-niceness condition for is the co--free class, the complement-family convention named in the statement; step 2.2 establishes precisely that condition. This proves the corollary.
Remarks
- The corollary is the endpoint of the second reduction chain: property comes from the co- comb structure, and leaf-reducibility turns it into generalized niceness. It is deliberately stated for the family itself, not for the complement family ; the notation appears only inside the published definitions.
- No Choice. All quantified objects are finite graphs and finite families, and no selection from a family of nonempty sets occurs; the argument uses only published finite reductions.
Depends on
- The singleton family $\{E\}$ 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 family consisting of $H_5$ and co-$E$ has the Erdős–Hajnal property
- A special-vertex comb in a co-$E$-free graph admits the $\{H_5,\mathrm{co}\text{-}E\}$ structural partition
- The special-vertex-local structural-partition criterion implies property (*)
- Deleting a leaf and a co-leaf preserves the Erdős-Hajnal property of a finite forbidden family
- Every smaller positive exponent is again an Erdős–Hajnal constant
- The $E$-graph and co-$E$
- Co-leaves of a finite graph
Used by
Dependency tree · two levels
53 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, Lemmas 4.5, 5.1, 6.3 and 6.4 (standard reference, not scraped)
- Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Section 5 iterative-sparsification context (standard reference, not scraped)