Alphabeta MathHow 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.
Rödl: for every and every there is such that every nonempty -free graph has an -restricted vertex set of size at least
Statement
For every graph and every there exists such that every nonempty -free finite simple graph has an -restricted vertex set of size at least .
Facts & Assumptions
Given: A graph and a real .
If is -free, then (-free and -free graphs under the induced-subgraph convention, The induced-embedding count ).
For every graph and there is such that every nonempty graph satisfying has an -restricted set of size at least (Nikiforov: for every and every there is such that every graph with has an -restricted vertex set of size at least ).
Proof
Let be the constant supplied by [L2] for the given and .
If is nonempty and -free, then [L1] gives .
Applying [L2] to step 1.2 yields the desired -restricted set.
Depends on
- Nikiforov: for every $H$ and every $\epsilon\in(0,\tfrac12)$ there is $\delta>0$ such that every graph $G$ with $\operatorname{ind}_H(G)<(\delta|V(G)|)^{|V(H)|}$ has an $\epsilon$-restricted vertex set of size at least $\delta|V(G)|$
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- The induced-embedding count $\operatorname{ind}_H(G)$
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
Used by
- For every λ>0 a bounded number of disjoint ε-restricted sets covers all but λ|V(G)| vertices of an H-free graph Corollary
- Rödl's theorem for a nonempty family of forbidden induced subgraphs Corollary
- The edge-density form of Rödl's theorem implies the maximum-degree form, with ε and δ each shrunk by a constant factor Corollary
- The edge-density form of Rödl's theorem: every nonempty H-free graph has a linearly large set of self-density at most ε or at least 1-ε Corollary
- The dense alternative in Rödl's theorem cannot be dropped Counterexample
- For P₃-free graphs Rödl's theorem holds with δ=ε, by an explicit argument Example
- Bounded degree against bounded density: the two statements of Rödl's theorem, and which one is stronger Remark
- What this proof gives for δ, and why the regularity route is expensive Remark
Dependency tree · two levels
22 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
- Y. Huang, Q. Ju, and X. Zhou, Erdős-Hajnal beyond the five-vertex path, Theorem 1.1 (standard reference, not scraped)