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.
Generalized niceness yields four reduction outcomes
Statement
Let be a generalized nice, leaf-reducible, wonderful finite family of graphs. Then there exist constants and such that for every and every -restricted -free graph , at least one of the following holds:
- has a clique or stable set of size at least
- has a -restricted induced subgraph with at least vertices;
- has a complete or anticomplete -blockade with ; or
- there exist disjoint sets with and complete or anticomplete to .
Facts & Assumptions
Given: A generalized nice, leaf-reducible, wonderful finite family , a parameter , and a -restricted -free graph .
Generalized niceness supplies constants , , , , and with the four alternatives in Generalized nice finite graph families.
Leaf-reducibility supplies constants and such that every -sparse -free graph yields either a large anticomplete pair or a deeper restricted induced subgraph (Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph).
Restrictedness is invariant under graph complementation (A set is -sparse in exactly when it is -dense in , so -restrictedness is complement-invariant).
Wonderfulness supplies an exponent as in Wonderful finite graph families.
A complete-or-weakly-sparse blockade can be thinned to equal-sized subblocks with directional sparsity (A complete-or-weakly-sparse blockade can be thinned to equal subblocks with directional sparsity).
Such an equal-sized blockade either contains a complete subblockade or can be thinned further to anticonnected subblocks (A complete-or-weakly-sparse blockade yields a complete subblockade or an anticonnected thinning).
A wonderful anticonnected blockade with small support yields either a -restricted induced subgraph or a large anticomplete pair (A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair).
Proof
Fix constants from [L1], [L2], and [L4], and set , , , , and . These choices depend only on .
If , then any one-vertex induced subgraph of is -restricted and has size at least . So outcome 2 holds.
Suppose is -sparse. Apply [L2] to the family inside with the parameter . Either has a -restricted induced subgraph of size at least , or there are disjoint sets with , , and anticomplete to in . By [L3], the restricted induced subgraph is also -restricted in , and the anticomplete pair in is a complete pair in . Since and , this gives outcome 2 or outcome 4 in .
We may therefore assume that itself is -sparse. Put , where is the witness from [L4]. Because is -free, [L1] applies to and . If [L1] produces a clique or stable set of size , then this is exactly outcome 1 by the choice and . If [L1] produces a complete or anticomplete -blockade with , then because , and because , so outcome 3 holds. If [L1] produces an -restricted induced subgraph of size at least , then and , so outcome 2 holds. We are left only with the blockade alternative from [L1].
Thus has a blockade with , each , and every distinct pair complete or weakly -sparse. Apply [L5] to obtain equal-sized subblocks with and every noncomplete pair mutually -sparse. Then apply [L6] to . If [L6] yields a complete -blockade, then , because for and step 1.1 has . Since also , outcome 3 follows.
We may therefore assume [L6] yields anticonnected subsets of common size such that every distinct pair is either complete or mutually -sparse. Because , every noncomplete pair is in fact mutually -sparse. Also , since and . Since step 2.1 fails, , and because with , this gives and hence . Therefore , where . Since , one has . Therefore the hypotheses of [L7] hold for .
Applying [L7] to yields either a -restricted induced subgraph of size at least , giving outcome 2, or disjoint sets with , , and anticomplete to , giving outcome 4.
The cases in steps 2.1, 2.2, 2.3, and 5.1 exhaust all possibilities, so one of the four stated outcomes always holds.
Depends on
- Generalized nice finite graph families
- Wonderful finite graph families
- A complete-or-weakly-sparse blockade can be thinned to equal subblocks with directional sparsity
- A complete-or-weakly-sparse blockade yields a complete subblockade or an anticonnected thinning
- A wonderful anticonnected complete-or-sparse blockade yields a restricted subgraph or a large anticomplete pair
- Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph
- A set is $c$-sparse in $G$ exactly when it is $c$-dense in $\overline G$, so $c$-restrictedness is complement-invariant
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
- Graph isomorphisms, automorphisms and graph complements
Used by
Dependency tree · two levels
28 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, Erdos-Hajnal beyond the five-vertex path, Lemma 3.1 (standard reference, not scraped)
- Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Lemma 7.1 (standard reference, not scraped)