CorollaryStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

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.

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 - ϵ$

Statement

For every graph $H$ and every $ϵ \in (0, \frac{1}{2})$ there exists $δ > 0$ such that every nonempty $H$ -free finite simple graph $G$ contains a set $X \subseteq V (G)$ with $∣ X ∣ \geq δ ∣ V (G) ∣$ and either $d_{G} (X, X) \leq ϵ$ or $d_{G} (X, X) \geq 1 - ϵ$ .

Facts & Assumptions

Given: A graph $H$ and a real $ϵ \in (0, \frac{1}{2})$ .

[L1]

Rödl's theorem supplies a constant $δ_{0} > 0$ such that every nonempty $H$ -free graph $G$ has an $(ϵ / 2)$ -restricted set of size at least $δ_{0} ∣ V (G) ∣$ (Rödl: for every $H$ and every $ϵ \in (0, \frac{1}{2})$ there is $δ > 0$ such that every nonempty $H$ -free graph has an $ϵ$ -restricted vertex set of size at least $δ ∣ V (G) ∣$ ).

[L2]

A $(ϵ / 2)$ -sparse set has self-density at most $ϵ / 2$ , while a $(ϵ / 2)$ -dense set has self-density at least $1 - ϵ / 2 - 1 / ∣ X ∣$ (A $c$ -sparse set has self-density at most $c$ , and a $c$ -dense set has self-density at least $1 - c - 1 / ∣ X ∣$ ).

Proof

technique · direct

1.1

Let $δ_{0}$ be the constant from [L1] for the parameter $ϵ / 2$ , and set $δ : = \min {δ_{0}, ϵ δ_{0} / 2}$ .

L1choose

2.1

If $G$ is nonempty and $H$ -free, then [L1] gives a set $X$ with $∣ X ∣ \geq δ_{0} ∣ V (G) ∣$ that is $(ϵ / 2)$ -restricted.

step 1.1L1

3.1

If $X$ is $(ϵ / 2)$ -sparse, then [L2] gives $d_{G} (X, X) \leq ϵ / 2 \leq ϵ$ .

step 2.1L2

3.2

If $X$ is $(ϵ / 2)$ -dense and $∣ X ∣ \geq 2 / ϵ$ , then [L2] gives $d_{G} (X, X) \geq 1 - ϵ$ . If instead $∣ X ∣ < 2 / ϵ$ , then $∣ V (G) ∣ < 2 / (ϵ δ_{0})$ by step 2.1, and the single-vertex set ${v}$ has self-density $0 \leq ϵ$ and size $1 > δ ∣ V (G) ∣$ by the choice of $δ$ in step 1.1.

step 1.1step 2.1L2algebracases

4.1

In every case there is a set of size at least $δ ∣ V (G) ∣$ whose self-density is at most $ϵ$ or at least $1 - ϵ$ .

step 3.1step 3.2algebra∎

Depends on

Used by

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)

The edge-density form of Rödl's theorem: every nonempty HH-free graph has a linearly large set of self-density at most ϵϵ or at least 1−ϵ1−ϵ