LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-05

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.

Rödl initialization upgrades generalized niceness to a restricted set, a complete or anticomplete blockade, or a polynomial clique or stable set

Statement

Let $F$ be a generalized nice, leaf-reducible, wonderful finite family. Then there exist constants $c_{1} \geq 1$ and $c_{2} > 0$ such that for every $x \in (0, \frac{1}{2})$ and every $\overline{F}$ -free graph $G$ , at least one of the following holds:

$G$ has an $x$ -restricted induced subgraph with at least $x^{c_{1}} ∣ G ∣$ vertices;
$G$ has a complete or anticomplete $(k, ∣ G ∣ / k^{c_{1}})$ -blockade for some integer $k \geq 2$ ;
$G$ has a clique or stable set of size at least $(x^{c_{1}} ∣ G ∣)^{c_{2}} .$

Facts & Assumptions

Given: A generalized nice, leaf-reducible, wonderful finite family $F$ , a parameter $x \in (0, \frac{1}{2})$ , and an $\overline{F}$ -free graph $G$ .

[L1]

There exist constants $c \in (0, \frac{1}{2})$ , $a_{1} \geq 1$ , and $a_{2} > 0$ such that every $c^{2}$ -restricted $\overline{F}$ -free graph satisfies the three-outcome conclusion with parameter $x$ whenever $x < c^{2}$ (Constant-scale restricted generalized niceness yields an x-scale restricted subgraph, a polynomial clique or stable set, or a blockade).

[L2]

For every graph $H$ and every $ξ \in (0, \frac{1}{2})$ , every nonempty $H$ -free graph has a $ξ$ -restricted induced subgraph of size at least $δ ∣ G ∣$ for some constant $δ > 0$ depending only on $H$ and $ξ$ (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) ∣$ ).

Proof

technique · use Rödl at the fixed scale $\xi=c^2$, then apply the constant-scale theorem unless $x$ is already above that scale

1.1L1L2choose

Let $c \in (0, \frac{1}{2})$ , $a_{1} \geq 1$ , and $a_{2} > 0$ be the constants supplied by [L1], and set $ξ : = c^{2}$ . Choose $δ > 0$ from [L2] for the forbidden family $\overline{F}$ and the parameter $ξ$ .

2.1step 1.1choose

Choose an integer $c_{1} \geq 1$ so large that $δ \geq ξ^{c_{1} / 2}, δ \geq 2^{a_{1} - c_{1}}, c_{1} \geq 2 a_{1},$ and set $c_{2} : = a_{2}$ .

2.2step 1.1L2

By [L2], the graph $G$ has a $ξ$ -restricted induced subgraph $F \subseteq G$ with $∣ F ∣ \geq δ ∣ G ∣$ .

3.1step 2.1step 2.2givenalgebra

Suppose first that $x \geq ξ$ . Then $F$ is also $x$ -restricted, and $∣ F ∣ \geq δ ∣ G ∣ \geq 2^{a_{1} - c_{1}} ∣ G ∣ \geq x^{c_{1} - a_{1}} ∣ G ∣ \geq x^{c_{1}} ∣ G ∣,$ because $x \leq \frac{1}{2}$ and $a_{1} \geq 1$ . Hence outcome 1 holds.

3.2step 1.1step 2.2L1

Assume now that $x < ξ = c^{2}$ . Then [L1] applies to the $c^{2}$ -restricted graph $F$ and yields one of three conclusions: an $x$ -restricted induced subgraph $S \subseteq F$ with $∣ S ∣ \geq x^{a_{1}} ∣ F ∣$ , a clique or stable set of size at least $(x^{a_{1}} ∣ F ∣)^{a_{2}}$ , or a complete or anticomplete $(k, ∣ F ∣ / k^{a_{1}})$ -blockade in $F$ for some integer $k \geq 2$ .

4.1step 2.1step 3.2algebra

In the first branch, $x^{a_{1}} ∣ F ∣ \geq x^{a_{1}} δ ∣ G ∣ \geq x^{a_{1}} ξ^{c_{1} / 2} ∣ G ∣ \geq x^{a_{1} + c_{1} / 2} ∣ G ∣ \geq x^{c_{1}} ∣ G ∣,$ because $x < ξ$ and $c_{1} \geq 2 a_{1}$ . So outcome 1 holds.

4.2step 2.1step 3.2algebra

In the third branch, $\frac{∣ F ∣}{k^{a_{1}}} \geq \frac{δ ∣ G ∣}{k^{a_{1}}} \geq \frac{2^{a_{1} - c_{1}} ∣ G ∣}{k^{a_{1}}} \geq \frac{∣ G ∣}{k^{c_{1}}},$ because $k \geq 2$ . Thus the same blocks give outcome 2 in $G$ .

5.1step 2.1step 3.2step 4.1algebra

In the second branch, the same inequality from step 4.1 gives $(x^{a_{1}} ∣ F ∣)^{a_{2}} \geq (x^{c_{1}} ∣ G ∣)^{c_{2}}$ , so outcome 3 holds.

6.1step 3.1step 3.2step 4.1step 5.1step 4.2∎

Steps 3.1, 4.1, 4.2, and 5.1 cover all possibilities, so one of the three stated outcomes always holds.

Depends on

Used by

Dependency tree · two levels

14 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

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Lemma 3.4 (standard reference, not scraped)
Tung H. Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Theorem 1.3 (standard reference, not scraped)