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.
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
Statement
For every graph and every there exists such that every nonempty -free finite simple graph contains a set with and either or .
Facts & Assumptions
Given: A graph and a real .
Rödl's theorem supplies a constant such that every nonempty -free graph has an -restricted set of size at least (Rödl: for every and every there is such that every nonempty -free graph has an -restricted vertex set of size at least ).
A -sparse set has self-density at most , while a -dense set has self-density at least (A -sparse set has self-density at most , and a -dense set has self-density at least ).
Proof
Let be the constant from [L1] for the parameter , and set .
If is nonempty and -free, then [L1] gives a set with that is -restricted.
If is -sparse, then [L2] gives .
If is -dense and , then [L2] gives . If instead , then by step 2.1, and the single-vertex set has self-density and size by the choice of in step 1.1.
In every case there is a set of size at least whose self-density is at most or at least .
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)|$
- A $c$-sparse set has self-density at most $c$, and a $c$-dense set has self-density at least $1-c-1/|X|$
- Edge counts and densities between nonempty vertex sets
- $c$-sparse, $c$-dense and $c$-restricted vertex sets
- Real powers for positive bases, with the zero-base positive-exponent convention
Used by
- An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree Corollary
- The edge-density form of Rödl's theorem implies the maximum-degree form, with ε and δ each shrunk by a constant factor Corollary
- Bounded degree against bounded density: the two statements of Rödl's theorem, and which one is stronger Remark
- Every H-free graph partitions into boundedly many vertex sets of self-density at most ε or at least 1-ε Theorem
- For every k, the class forbidding Pₖ and Pₖ has the strong Erdős–Hajnal property Theorem
Dependency tree · two levels
19 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)