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.
Bounded degree against bounded density: the two statements of Rödl's theorem, and which one is stronger
The maximum-degree form is stronger than the density form. If every vertex of has at most neighbours, then the self-density is at most by A -sparse set has self-density at most , and a -dense set has self-density at least . The converse fails: small average degree does not control exceptional vertices, and a large star is the basic witness.
What this page proves is the stronger form Rödl: for every and every there is such that every nonempty -free graph has an -restricted vertex set of size at least , then derives the density form The edge-density form of Rödl's theorem: every nonempty -free graph has a linearly large set of self-density at most or at least , and finally shows by The edge-density form of Rödl's theorem implies the maximum-degree form, with and each shrunk by a constant factor that the weaker statement implies the stronger one after shrinking the constants by a fixed factor.
Depends on
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
- A $c$-sparse set has self-density at most $c$, and a $c$-dense set has self-density at least $1-c-1/|X|$
- A set of self-density at most $c$ has a subset of at least half its size that is $4c$-sparse
- 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)|$
- The edge-density form of Rödl's theorem: every nonempty $H$-free graph has a linearly large set of self-density at most $\epsilon$ or at least $1-\epsilon$
- The edge-density form of Rödl's theorem implies the maximum-degree form, with $\epsilon$ and $\delta$ each shrunk by a constant factor
- Edge counts and densities between nonempty vertex sets
- Sparsity of one vertex set to another, and weak sparsity of a pair
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
25 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
- M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Strengthening Rödl's theorem, sec. 1 (standard reference, not scraped)