LemmaStatement: Literature-sourcedProof: 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 without a polynomial clique or stable set force complete or anticomplete blockades

Statement

Let $F$ be a generalized nice, leaf-reducible, wonderful finite family. Let $c_{1} \geq 1$ and $c_{2} > 0$ be the constants from Rödl initialization upgrades generalized niceness to a restricted set, a complete or anticomplete blockade, or a polynomial clique or stable set. Fix an $\overline{F}$ -free graph $G$ , define

$q : = 42 c_{1}^{2}, c : = \min {q^{- 1}, c_{2} / 2}, x : = ∣ G ∣^{- 1 / (3 c_{1})}, ϵ : = x^{1 / (7 c_{1})} .$

and assume that $G$ has no clique or stable set of size at least $∣ G ∣^{c}$ . Then every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{2 c_{1}} ∣ G ∣$ has a complete or anticomplete $(k, ∣ F ∣ / k^{c_{1}})$ -blockade for some integer $k \in [2, ϵ^{- 1}]$ .

Facts & Assumptions

Given: The data and hypotheses in the Statement.

[L1]

The previous lemma gives every $\overline{F}$ -free graph either an $x$ -restricted induced subgraph of size at least $x^{c_{1}}$ times the ambient order, or a complete or anticomplete $(k, ∣ G ∣ / k^{c_{1}})$ -blockade with $k \geq 2$ , or a clique or stable set of size at least $(x^{c_{1}} ∣ G ∣)^{c_{2}}$ (Rödl initialization upgrades generalized niceness to a restricted set, a complete or anticomplete blockade, or a polynomial clique or stable set).

[L2]

A nonempty $x$ -sparse graph $H$ satisfies $χ (H) \leq x ∣ H ∣ + 1, ∣ H ∣ \leq χ (H) α (H),$ by The greedy colouring bound $χ (G) \leq Δ (G) + 1$ for every nonnull finite graph and The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ .

[L3]

A set is $x$ -restricted exactly when it is $x$ -sparse in one of $G$ and $\overline{G}$ , and cliques in one graph are stable sets in the complement ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets, A set is $c$ -sparse in $G$ exactly when it is $c$ -dense in $\overline{G}$ , so $c$ -restrictedness is complement-invariant, Complementation swaps cliques with stable sets, so $ω (\overline{G}) = α (G)$ ).

Proof

technique · apply the previous lemma to $F$ and show that the restricted and clique/stable branches contradict the assumed failure of the polynomial bound

1.1givenassume-contra

Let $F$ be an induced subgraph of $G$ with $∣ F ∣ \geq ϵ^{2 c_{1}} ∣ G ∣$ , and suppose for contradiction that $F$ has no complete or anticomplete $(k, ∣ F ∣ / k^{c_{1}})$ -blockade for any integer $k \in [2, ϵ^{- 1}]$ .

2.1

Apply [L1] to the graph $F$ with the parameter $x$ . Because the blockade branch is excluded by step 1.1, either:

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

[step 1.1, L1]

3.1step 2.1L3algebra

Suppose the restricted branch of step 2.1 holds. Then $∣ S ∣ \geq x^{c_{1}} ∣ F ∣ \geq x^{c_{1}} ϵ^{2 c_{1}} ∣ G ∣ = x^{c_{1} + 2 / 7} ∣ G ∣ = x^{- 2 c_{1} + 2 / 7} .$ Since $c_{1} \geq 1$ and $0 < x < 1$ , the exponent $- 2 c_{1} + 2 / 7$ is at most $- 1$ , so $∣ S ∣ \geq x^{- 1}$ . After replacing $S$ by the same set in the complementary graph if necessary, [L3] lets us assume that $S$ is $x$ -sparse.

3.2step 1.1step 2.1algebrachoose

Suppose instead that the blockade branch of step 2.1 holds. Then step 1.1 forces $k > ϵ^{- 1}$ . Choosing one vertex from each block gives a clique or stable set of size $k > ϵ^{- 1} = ∣ G ∣^{1 / (21 c_{1}^{2})} \geq ∣ G ∣^{c}$ , because $c \leq (42 c_{1}^{2})^{- 1}$ . This contradicts the hypothesis on $G$ .

3.3step 2.1algebra

Suppose instead that the clique-or-stable-set branch of step 2.1 holds. Then $(x^{c_{1}} ∣ F ∣)^{c_{2}} \geq (x^{c_{1}} ϵ^{2 c_{1}} ∣ G ∣)^{c_{2}} = (x^{c_{1} + 2 / 7} ∣ G ∣)^{c_{2}} .$ Since $x = ∣ G ∣^{- 1 / (3 c_{1})}$ , the inner factor equals $∣ G ∣^{1 - (c_{1} + 2 / 7) / (3 c_{1})}$ , whose exponent is at least $1 / 2$ because $c_{1} \geq 1$ . Therefore $F$ contains a clique or stable set of size at least $∣ G ∣^{c_{2} / 2} \geq ∣ G ∣^{c}$ , because $c \leq c_{2} / 2$ . This again contradicts the hypothesis on $G$ .

4.1step 3.1L2algebra

By [L2], $α (G [S]) \geq \frac{∣ S ∣}{x ∣ S ∣ + 1} = \frac{1}{x + ∣ S ∣^{- 1}} \geq \frac{1}{x + x} \geq x^{- 1 / 2} .$ Because $x = ∣ G ∣^{- 1 / (3 c_{1})}$ , this gives a clique or stable set of size at least $∣ G ∣^{1 / (6 c_{1})} \geq ∣ G ∣^{c}$ , contradicting the hypothesis on $G$ because $c \leq q^{- 1} = 1 / (42 c_{1}^{2}) \leq 1 / (6 c_{1})$ .

5.1step 4.1step 3.2step 3.3discharge-contradiction∎

All three branches from step 2.1 contradict the hypothesis on $G$ , so the assumption in step 1.1 was false. Therefore $F$ has a complete or anticomplete $(k, ∣ F ∣ / k^{c_{1}})$ -blockade for some integer $k \in [2, ϵ^{- 1}]$ .

Depends on

Used by

Dependency tree · two levels

22 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 3.5.1 (standard reference, not scraped)