LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

Large induced subgraphs in the property (*) four-outcome theorem contain a pure or x-sparse polynomial blockade

Statement

Let $F$ have property $(*)$ and be leaf-reducible, and let $c_{1}^{'} > 0$ , $c_{4}^{'} \geq 4$ , and $d \geq 58 c_{4}^{'}$ be the constants from Rödl initialization removes the constant-scale restriction in the property (*) four-outcome theorem. Fix $ϵ \in (0, \frac{1}{2})$ , put $x : = ϵ^{5 d}$ , and let $G$ be an $\overline{F}$ -free graph with $∣ G ∣ \geq ϵ^{- 10 d^{2}}$ such that

$G$ has no clique or stable set of size at least $(ϵ^{156 c_{4}^{'} d} ∣ G ∣)^{c_{1}^{'}}$ ;
$G$ has no complete or anticomplete $(k, ∣ G ∣ / k^{2 d})$ -blockade with $k \geq ϵ^{- 5 d}$ ;
$G$ has no $ϵ^{5 d}$ -restricted induced subgraph with at least $ϵ^{116 c_{4}^{'} d} ∣ G ∣$ vertices.

Then every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ has a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some integer $k \in [2, x^{- 1}]$ .

Facts & Assumptions

Given: The data and hypotheses in the Statement, together with an induced subgraph $F$ of $G$ satisfying $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ .

[L1]

The previous lemma says that every $\overline{F}$ -free graph of size at least $x^{- d}$ satisfies one of four outcomes: an $x$ -restricted induced subgraph of size at least $x^{23 c_{4}^{'}}$ times the ambient order, a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some integer $k \in [2, x^{- 1}]$ , a clique or stable set of size at least $(x^{31 c_{4}^{'}} ∣ F ∣)^{c_{1}^{'}}$ , or a complete or anticomplete polynomial blockade (Rödl initialization removes the constant-scale restriction in the property (*) four-outcome theorem).

[L2]

If $∣ G ∣ \geq ϵ^{- 10 d^{2}}$ and $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ , then $∣ F ∣ \geq ϵ^{- 5 d^{2}} = x^{- d}$ because $d \geq 1$ .

[L3]

If $k \geq x^{- 1} = ϵ^{- 5 d}$ , then $ϵ^{d} = x^{1 / 5} \geq k^{- 1 / 5}$ .

Proof

technique · apply the Rödl-initialized four-outcome theorem to $F$ and use the three standing failure hypotheses to rule out every branch except the pure-or-sparse blockade branch

1.1givenL1algebra

The size hypothesis on $G$ and the bound $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ imply $∣ F ∣ \geq ϵ^{d} ϵ^{- 10 d^{2}} = ϵ^{- 10 d^{2} + d} \geq ϵ^{- 5 d^{2}} = x^{- d},$ because $d \geq 1$ . Thus [L1] applies to $F$ .

2.1step 1.1L1

Apply [L1] to the induced subgraph $F$ . One of its four outcomes holds.

3.1step 2.1algebra

If [L1] yields an $x$ -restricted induced subgraph $S$ of $F$ with at least $x^{23 c_{4}^{'}} ∣ F ∣$ vertices, then $∣ S ∣ \geq x^{23 c_{4}^{'}} ϵ^{d} ∣ G ∣ = ϵ^{115 c_{4}^{'} d + d} ∣ G ∣ \geq ϵ^{116 c_{4}^{'} d} ∣ G ∣,$ because $c_{4}^{'} \geq 1$ . This contradicts standing hypothesis 3.

3.2step 2.1algebra

If [L1] yields a clique or stable set of size at least $(x^{31 c_{4}^{'}} ∣ F ∣)^{c_{1}^{'}}$ , then $x^{31 c_{4}^{'}} ∣ F ∣ \geq x^{31 c_{4}^{'}} ϵ^{d} ∣ G ∣ = ϵ^{155 c_{4}^{'} d + d} ∣ G ∣ \geq ϵ^{156 c_{4}^{'} d} ∣ G ∣,$ so standing hypothesis 1 is contradicted.

3.3step 2.1L3algebra

If [L1] yields a complete or anticomplete $(k, ∣ F ∣ / k^{d})$ -blockade with $k \geq x^{- 1}$ , then [L3] gives $ϵ^{d} \geq k^{- 1 / 5}$ , and therefore $\frac{∣ F ∣}{k^{d}} \geq \frac{ϵ^{d} ∣ G ∣}{k^{d}} \geq \frac{∣ G ∣}{k^{2 d}} .$ Since $k \geq x^{- 1} = ϵ^{- 5 d}$ , this contradicts standing hypothesis 2.

4.1step 3.1step 3.2step 3.3∎

The first three branches are impossible, so the remaining branch of [L1] must hold: $F$ has a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some integer $k \in [2, x^{- 1}]$ . This is exactly the desired conclusion.

Depends on

Used by

Dependency tree · two levels

9 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, Claim 4.5.1 (standard reference, not scraped)