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.
A sparse host has many leaf extensions, few smaller copies, or a long sparse blockade
Statement
Let be a finite graph on vertices with leaf , and put . Let and . Suppose a finite graph on vertices has maximum degree at most . Then at least one of the following holds:
- ;
- some has and ;
- has an -sparse blockade of length at least and width at least .
Facts & Assumptions
Given: The data in the statement.
With parameters , the preceding leaf-extension lemma gives many -embeddings, a set with few -embeddings, or a sparse pair with first side of size at least times the host order and second side of size at least times that order (A sparse host has many leaf extensions, few smaller copies, or a sparse pair). The bound holds for .
Proof
Suppose all three outcomes fail. If , a singleton gives outcome 2 since . If , a greedy stable-set algorithm gives at least stable vertices: each selected vertex removes itself and at most neighbors. Taking those vertices as singleton blocks gives outcome 3. Consequently .
Among sequences of disjoint nonempty sets with -sparse to every earlier block, for , and , choose one with maximum . Such a sequence exists with and ; finiteness bounds . Since outcome 3 fails, . For , (for example, is concave and nonnegative at both endpoints). As , this gives |B_k|\ge(1-hy)^kn\ge4^{-hyk}n>4^{-h}n\ge yn\ge xn.\tag{1}
The graph has maximum degree at most by (1). Failure of outcome 1 and (1) give Because , failure of outcome 2 gives . Thus [L1] applied to supplies disjoint such that , , and is -sparse to .
Replace the old final block by . Since every vertex of was -sparse to each earlier block, the same is true of its subsets and ; the new last pair is sparse by step 3.1. The new sequence satisfies all the size conditions of step 2.1 with index , contradicting maximality. Therefore at least one stated outcome holds.
Depends on
Used by
Dependency tree · two levels
7 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
- Nguyen, Scott and Seymour, Induced subgraph density IV, Lemma 5.2 (standard reference, not scraped)