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.
Substituting two -narrow graphs yields another -narrow graph
Statement
Let . If and are -narrow finite graphs and the substitution is defined, then is -narrow.
Facts & Assumptions
Given: A real number , -narrow finite graphs and , and a defined substitution .
A graph is -narrow when every good function has -power sum at most (An -narrow graph).
In a substitution, every vertex of the substituted graph has exactly the outside adjacencies that the vertex had in (Substituting one graph for a vertex of another).
Substituting a perfect graph for a vertex of a perfect graph preserves perfection (Substituting perfect graphs preserves perfection ‡).
Proof
Let be a good function on . Let be the family of perfect induced subgraphs of , and let . If , then every one-vertex induced subgraph of has weight , so vanishes on . Choose any vertex , define on by copying outside and setting , and note from [F2] that every perfect induced subgraph of corresponds either to the same perfect induced subgraph of or to one obtained by replacing with . Hence is good on , so [F1] gives . Because vanishes on , this is exactly .
Assume now that . Define on by copying outside and setting . If is a perfect induced subgraph of not containing , then it appears unchanged in and has total -weight at most . If , choose with ; then [L1] makes the substitution a perfect induced subgraph of , so . Thus is good on . Likewise is good on by the definition of . Applying [F1] to and gives and .
In the case , step 1.2 yields . Together with step 1.1, this proves that every good function on has -power sum at most . Therefore [F1] shows that is -narrow.
Depends on
Used by
Dependency tree · two levels
10 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, The Erdős-Hajnal Conjecture: A Survey, Theorem 2.5 (standard reference, not scraped)
- Maria Chudnovsky and Shmuel Safra, The Erdős-Hajnal conjecture for bull-free graphs, proof of Theorem 1.3 (standard reference, not scraped)