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.
Star and special-vertex obstructions force wonderfulness
Statement
Let be a finite family of finite graphs. Assume one of the following.
- There exist and an integer such that is an induced subgraph of the -subdivision of .
- There exist a graph on vertex set with , with distinguished vertices , such that has the Erdős-Hajnal property and is not -free.
Then is wonderful.
Facts & Assumptions
Given: A finite family satisfying one of the two hypotheses in the Statement.
To prove that is wonderful, it suffices to exhibit a constant with the two-outcome property recorded in the definition of wonderfulness (Wonderful finite graph families).
Under either obstruction hypothesis, the auxiliary graph on the blocks with for a fixed outside vertex has a clique or stable set of size at least a positive power of its order (The auxiliary pattern then has a polynomial-size clique or stable set).
A polynomial-size clique or stable set in that auxiliary graph yields a -restricted union of whole blocks (A polynomial homogeneous set in the auxiliary pattern yields a -restricted union).
Proof
Choose in case 1. In case 2, let be the maximum order of a graph in . By [L2], fix a constant suitable for the corresponding obstruction hypothesis, and then choose .
Let , let be a -free graph, and let be an -blockade satisfying the hypotheses from [L1] for the constant . For each outside vertex , define . Suppose first that for every such . Then the number of pairs with and is at most . Averaging over the indices, some is contained in at most of the sets . That is exactly the second conclusion from [L1].
It remains to consider the opposite case. Choose with . Let be the increasing bijection, where , put , and form the auxiliary graph on by if and only if is complete to . The reordered family of blocks still has equal size, still satisfies , and still satisfies the pairwise complete-or-mutually--sparse hypothesis. Therefore [L2] applies and gives a clique or stable set with .
Put . In the auxiliary graph on the original index set , the set is a clique or stable set with . The original blockade has length , the subset has size at least , and . Thus [L3] applies to , , and . It follows that induces a -restricted subgraph of whose size is at least the common block size, and therefore at least the width of . This is the first conclusion from [L1].
Step 1.2 gives the second wonderfulness outcome when no outside vertex belongs to many index sets , and step 3.1 gives the first outcome otherwise. Thus the constant from step 1.1 satisfies [L1], so is wonderful.
Depends on
Used by
Dependency tree · two levels
14 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 2.1 (standard reference, not scraped)