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.
What this proof gives for , and why the regularity route is expensive
The proof of Rödl: for every and every there is such that every nonempty -free graph has an -restricted vertex set of size at least runs through the self-regular subset theorem and hence through Szemerédi regularity. Its constant is therefore extremely small: it is assembled from the regularity output, the counting-lemma constant, and the trimming loss in Nikiforov: for every and every there is such that every graph with has an -restricted vertex set of size at least . Nothing on this page claims that this bound is close to optimal.
The significance of the theorem is structural, not quantitative: every -free graph contains a linearly large region that is sparse or dense in a strong sense. Later work improves the constants by avoiding the full regularity machinery; this page does not.
Depends on
- Rödl: for every $H$ and every $\epsilon\in(0,\tfrac12)$ there is $\delta>0$ such that every nonempty $H$-free graph has an $\epsilon$-restricted vertex set of size at least $\delta|V(G)|$
- Every finite graph has a linearly large $\epsilon$-self-regular vertex subset
- Szemerédi regularity lemma with an equitable partition and an explicit tower-type upper bound for graphs of order at least $m_0$
- 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)|$
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
20 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
- J. Conlon, J. Fox, and B. Sudakov, Recent developments in graph Ramsey theory, sec. 3.3 (standard reference, not scraped)