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.

✓ 11 results · all verified · 7 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Property (*) and Comb Outcomes

1 · Prerequisites

2 · Summary

This page packages the second reduction stage in Huang-Ju-Zhou. It starts from the comb trigger recorded as property (*), combines it with the earlier sparse comb and leaf-reduction lemmas, and then runs the same iterative-sparsification pattern used on the generalized-niceness page.

The later items separate the two load-bearing transfer claims from the final theorem. First the page reaches a constant-scale four-outcome theorem, then Rödl initialization removes that scale assumption, and finally the local pure-or-sparse blockade hypothesis is fed into the published blockade-to-nice theorem to recover generalized niceness.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 2026-09-05Open item page →

Property (*) for a finite graph family

Definition

Let $F$ be a finite family of finite graphs. We say that $F$ has property $(*)$ if there exist constants $c_{1}, c_{2}, c_{3} > 0$ such that the following holds for every $\overline{F}$ -free graph $G$ , where $\overline{F} : = {\overline{H} : H \in F}$ is the family of graph complements (Graph isomorphisms, automorphisms and graph complements) ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

Suppose there is an $(ℓ, w)$ -comb $((a_{i}, B_{i}) : i \in [ℓ])$ in $G$ (Combs in a graph) with $ℓ, w \geq 4$ , and suppose there is a vertex $v \in V (G) ∖ ({a_{i} : i \in [ℓ]} \cup ⋃_{i = 1}^{ℓ} B_{i})$ such that $v$ is complete to $⋃_{i} B_{i}$ and anticomplete to ${a_{i} : i \in [ℓ]}$ . Then at least one of the following holds:

$G$ has a clique or stable set of size at least $w^{c_{1}}$ (Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ );
$G$ has a complete or anticomplete $(k, w / k^{c_{2}})$ -blockade for some real $k \geq ℓ^{c_{3}}$ , where the real length threshold $k$ means that the blockade's integral length is at least $⌈ k ⌉$ (Blockades, their length, their width, and their support, Complete, anticomplete, pure, weakly sparse, and $x$ -sparse blockades);
$G$ has a pure $(ℓ, w / ℓ^{2})$ -blockade.

This condition records exactly the three ways the special-vertex comb trigger can terminate the second sparsification round.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-05Open item page →

Property (*) and leaf reducibility yield five comb outcomes in a restricted graph

Statement

Suppose that $F$ has property $(*)$ and that $F$ is leaf-reducible. Then there exist constants $c_{1}, c_{2}, c_{3} > 0$ and $c_{4}, c_{5} \geq 4$ such that for every $0 < x \leq y \leq 2^{- 4 c_{5}}$ and every $y^{3}$ -restricted $\overline{F}$ -free graph $G$ , at least one of the following holds:

there are disjoint sets $X, Y \subseteq V (G)$ with $∣ X ∣ \geq y^{c_{4}} ∣ G ∣, ∣ Y ∣ \geq (1 - c_{5} y) ∣ G ∣,$ and $Y$ is $x$ -sparse or complete to $X$ ;
$G$ has a $2 y^{4}$ -restricted induced subgraph with at least $y^{c_{4}} ∣ G ∣$ vertices;
$G$ has a clique or stable set of size at least $(x^{9} ∣ G ∣)^{c_{1}}$ ;
$G$ has a complete or anticomplete $(k, ∣ G ∣ / k^{c_{2} + 6 / c_{3}})$ -blockade for some real $k \geq y^{- c_{3}}$ ;
$G$ has a pure $(ℓ, ∣ G ∣ / ℓ^{8})$ -blockade for some real $ℓ \in [y^{- 1}, x^{- 2}]$ .

Facts & Assumptions

Given: A finite family $F$ with property $(*)$ and leaf-reducible, parameters $0 < x \leq y \leq 2^{- 4 c_{5}}$ , and a $y^{3}$ -restricted $\overline{F}$ -free graph $G$ .

[L1]

Because $F$ has property $(*)$ , there exist constants $c_{1}, c_{2}, c_{3} > 0$ such that every special-vertex $(ℓ, w)$ -comb with $ℓ, w \geq 4$ in an $\overline{F}$ -free graph yields either a clique or stable set of size $w^{c_{1}}$ , or a complete or anticomplete $(k, w / k^{c_{2}})$ -blockade with $k \geq ℓ^{c_{3}}$ , or a pure $(ℓ, w / ℓ^{2})$ -blockade (Property (*) for a finite graph family).

[L2]

Since $F$ is leaf-reducible, there exist constants $d > 0$ and $h \geq 1$ such that every $y^{3}$ -sparse $F$ -free graph has either a large anticomplete pair or a $y^{12}$ -restricted induced subgraph of size at least $(y^{3})^{4 d + 1} ∣ G ∣ = y^{12 d + 3} ∣ G ∣$ (Leaf-reducible families yield a large anticomplete pair or a deeper restricted induced subgraph).

[L3]

If $G$ is $y^{3}$ -sparse and $∣ G ∣ \geq y^{- 4}$ , then either there are disjoint sets $X, Y \subseteq V (G)$ with $∣ X ∣ \geq y^{4} ∣ G ∣$ , $∣ Y ∣ \geq (1 - 4 y) ∣ G ∣$ , and $Y$ $x$ -sparse to $X$ , or $G$ is $2 y^{4}$ -sparse, or $G$ contains a special-vertex comb with parameters $ℓ \in [y^{- 1}, x^{- 2}]$ and width $w = y^{4} ∣ G ∣ / ℓ^{2}$ (A sparse graph either sparsifies further or yields a comb or a large sparse pair).

[L4]

Restrictedness is preserved by complementation ( $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).

Proof

technique · treat the dense side by applying the leaf-reducible lemma to $\overline G$, and otherwise apply the sparse comb lemma to $G$ and feed the comb branch into property $(*)$

1.1

Let $c_{1}, c_{2}, c_{3}$ be the constants from [L1]. Let $d > 0$ and $h \geq 1$ be the constants from [L2], and set $c_{4} : = \max {12 d + 3, 4}, c_{5} : = \max {h, 4} .$

L1L2choose

1.2

[assume-case dense-side] Suppose first that $\overline{G}$ is $y^{3}$ -sparse. Because $G$ is $\overline{F}$ -free, the complement graph $\overline{G}$ is $F$ -free. Applying [L2] to $\overline{G}$ with the parameter $y^{3}$ and $b = 4$ , we obtain either:

disjoint sets $X, Y \subseteq V (G)$ with $∣ X ∣ \geq y^{12 d + 3} ∣ G ∣$ , $∣ Y ∣ \geq (1 - h y) ∣ G ∣$ , and $Y$ complete to $X$ in $G$ ; or
a $y^{12}$ -restricted induced subgraph of $\overline{G}$ with at least $y^{12 d + 3} ∣ G ∣$ vertices.

In the first branch, $c_{4} \geq 12 d + 3$ and $c_{5} \geq h$ , so outcome 1 holds. In the second branch, [L4] transfers restrictedness back to $G$ , and because $y^{12} \leq 2 y^{4}$ for $0 < y < 1$ , outcome 2 holds. [step 1.1, L2, L4, given, algebra]

2.1

[assume-case sparse-side] We may therefore assume that $G$ itself is $y^{3}$ -sparse. If $∣ G ∣ \leq x^{- 9}$ , then $(x^{9} ∣ G ∣)^{c_{1}} \leq 1$ , so any vertex of $G$ already gives outcome 3. Hence we may further assume that $∣ G ∣ \geq x^{- 9} \geq y^{- 4}$ .

step 1.1step 1.2given

3.1

Apply [L3] to the sparse graph $G$ . If its first branch holds, then outcome 1 holds immediately. If its second branch holds, then outcome 2 holds immediately. So only the comb branch remains.

step 2.1L3cases

4.1

In that comb branch, [L3] gives an integer $ℓ_{0} \in [y^{- 1}, ⌈ x^{- 2} ⌉]$ , a width $w : = y^{4} ∣ G ∣ / ℓ_{0}^{2}$ , an $(ℓ_{0}, w)$ -comb $((a_{i}, B_{i}) : i \in [ℓ_{0}])$ , and a vertex $v$ complete to $⋃_{i} B_{i}$ and anticomplete to the teeth. Since $x \leq y \leq 2^{- 4 c_{5}}$ and $c_{5} \geq 4$ , one has $x \leq 2^{- 16}$ and hence $ℓ_{0} \geq y^{- 1} \geq 4$ . Also $⌈ x^{- 2} ⌉ \leq x^{- 2} + 1 \leq 2 x^{- 2}$ , so $w = \frac{y^{4} ∣ G ∣}{ℓ_{0}^{2}} \geq \frac{y^{4} ∣ G ∣}{(2 x^{- 2})^{2}} \geq \frac{x^{8} ∣ G ∣}{4} \geq x^{9} ∣ G ∣,$ because $y \geq x$ and $x \leq \frac{1}{4}$ . Using $∣ G ∣ \geq x^{- 9}$ from step 2.1 and $x \leq 2^{- 16}$ again, this also gives $w \geq x^{- 1} / 4 \geq 4$ .

step 1.1step 2.1step 3.1algebra

5.1

Apply [L1] to this special-vertex comb. If it yields a clique or stable set of size at least $w^{c_{1}}$ , then step 4.1 gives $w^{c_{1}} \geq (x^{9} ∣ G ∣)^{c_{1}}$ , so outcome 3 holds.

step 1.1step 4.1L1algebra

5.2

If [L1] yields a complete or anticomplete $(k, w / k^{c_{2}})$ -blockade with $k \geq ℓ_{0}^{c_{3}}$ , then $\frac{w}{k^{c_{2}}} \geq \frac{∣ G ∣}{ℓ_{0}^{6} k^{c_{2}}} \geq \frac{∣ G ∣}{k^{c_{2} + 6 / c_{3}}},$ and also $k \geq ℓ_{0}^{c_{3}} \geq y^{- c_{3}}$ . So outcome 4 holds.

step 4.1L1algebra

5.3

If [L1] yields a pure $(ℓ_{0}, w / ℓ_{0}^{2})$ -blockade, set $ℓ : = \sqrt{ℓ_{0} / y} .$ Because $ℓ_{0} \geq y^{- 1}$ , one has $ℓ \geq y^{- 1}$ and also $ℓ_{0} \geq ℓ$ , so the same blockade has length at least $ℓ$ . Since $ℓ_{0} \leq 2 x^{- 2}$ and $y \geq x$ , $ℓ^{2} = ℓ_{0} / y \leq 2 x^{- 2} / x = 2 x^{- 3} \leq x^{- 4},$ because $x \leq \frac{1}{2}$ , and therefore $ℓ \leq x^{- 2}$ . Finally, $\frac{w}{ℓ_{0}^{2}} = \frac{y^{4} ∣ G ∣}{ℓ_{0}^{4}} = \frac{∣ G ∣}{ℓ^{8}} .$ Hence outcome 5 holds.

step 4.1L1algebra

6.1

Steps 1.2, 2.1, 3.1, 5.1, 5.2, and 5.3 exhaust all cases, so one of the five stated outcomes always holds.

step 1.2step 2.1step 3.1step 5.1step 5.2step 5.3cases-exhaustive∎

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

Property (*) and leaf reducibility yield a long x-sparse or complete blockade, or a better outcome

Statement

Suppose that $F$ has property $(*)$ and that $F$ is leaf-reducible. Then there exist constants $c_{1}, c_{2}, c_{3} > 0$ and $c_{4}, c_{5} \geq 4$ such that, with $c : = 2^{- 4 c_{5}}$ , for every $0 < x \leq y \leq c$ and every $c y^{3}$ -restricted $\overline{F}$ -free graph $G$ , at least one of the following holds:

$G$ has an $x$ -sparse or complete blockade of length at least $y^{- 1}$ and width at least $y^{c_{4} + 2} ∣ G ∣$ ;
$G$ has a $2 y^{4}$ -restricted induced subgraph with at least $y^{c_{4} + 2} ∣ G ∣$ vertices;
$G$ has a clique or stable set of size at least $(x^{10} ∣ G ∣)^{c_{1}}$ ;
$G$ has a complete or anticomplete $(k, ∣ G ∣ / k^{c_{2} + 7 / c_{3}})$ -blockade for some real $k \geq y^{- c_{3}}$ ;
$G$ has a pure $(ℓ, ∣ G ∣ / ℓ^{9})$ -blockade for some real $ℓ \in [y^{- 1}, x^{- 2}]$ .

Facts & Assumptions

Given: A finite family $F$ with property $(*)$ and leaf-reducible, parameters $0 < x \leq y \leq c$ , and a $c y^{3}$ -restricted $\overline{F}$ -free graph $G$ .

[L1]

The five-outcome lemma provides constants $c_{1}, c_{2}, c_{3} > 0$ and $c_{4}, c_{5} \geq 4$ for $y^{3}$ -restricted graphs (Property (*) and leaf reducibility yield five comb outcomes in a restricted graph).

[L2]

If every induced subgraph $F$ of $G$ with $∣ F ∣ \geq c ∣ G ∣$ has disjoint sets $X, Y$ with $∣ X ∣ \geq y^{c_{4}} ∣ F ∣$ , $∣ Y ∣ \geq (1 - c_{5} y) ∣ F ∣$ , and $Y$ $x$ -sparse or complete to $X$ , then $G$ has an $x$ -sparse or complete blockade of length at least $y^{- 1}$ and width at least $y^{c_{4} + 2} ∣ G ∣$ (Large sparse-pair hypotheses yield an $x$ -sparse or complete blockade).

[L3]

If a graph is $c y^{3}$ -restricted and $F$ is an induced subgraph with $∣ F ∣ \geq c ∣ G ∣$ , then $F$ is $y^{3}$ -restricted ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

Proof

Proof technique: either every large induced subgraph satisfies the large pair hypothesis of [L2], or choose a counterexample $F$ and apply the five-outcome lemma inside it.

1.1

Let $c_{1}, c_{2}, c_{3} > 0$ and $c_{4}, c_{5} \geq 4$ be the constants from [L1], and put $c : = 2^{- 4 c_{5}}$ .

L1choose

2.1

If $∣ G ∣ \leq y^{- (c_{4} + 2)}$ , then $y^{c_{4} + 2} ∣ G ∣ \leq 1$ . Any single vertex spans an induced subgraph that is $0$ -restricted, hence $2 y^{4}$ -restricted, so outcome 2 holds. Therefore we may assume $∣ G ∣ \geq y^{- (c_{4} + 2)}$ .

step 1.1givenalgebracases

2.2

[assume-case universal-pair] Suppose that every induced subgraph $F$ of $G$ with $∣ F ∣ \geq c ∣ G ∣$ has disjoint sets $X, Y$ with $∣ X ∣ \geq y^{c_{4}} ∣ F ∣$ , $∣ Y ∣ \geq (1 - c_{5} y) ∣ F ∣$ , and $Y$ $x$ -sparse or complete to $X$ . Then [L2] gives outcome 1.

step 1.1L2

2.3

[assume-case obstruction] Assume instead that there is an induced subgraph $F$ of $G$ with $∣ F ∣ \geq c ∣ G ∣$ for which no such pair $X, Y$ exists. By [L3], the graph $F$ is $y^{3}$ -restricted, so [L1] applies to $F$ . Because the first outcome of [L1] fails for this specific $F$ , one of the remaining four outcomes of [L1] holds inside $F$ .

step 1.1L1L3

3.1

If [L1] gives a $2 y^{4}$ -restricted induced subgraph of $F$ with at least $y^{c_{4}} ∣ F ∣$ vertices, then that subgraph has at least $y^{c_{4}} c ∣ G ∣ = y^{c_{4} + 1} ∣ G ∣ \geq y^{c_{4} + 2} ∣ G ∣$ vertices because $y \leq c < 1$ . Hence outcome 2 holds in $G$ .

step 2.3L1algebra

3.2

If [L1] gives a clique or stable set of size at least $(x^{9} ∣ F ∣)^{c_{1}}$ , then $(x^{9} ∣ F ∣)^{c_{1}} \geq (x^{9} \cdot c ∣ G ∣)^{c_{1}} \geq (x^{9} \cdot x ∣ G ∣)^{c_{1}} = (x^{10} ∣ G ∣)^{c_{1}},$ because $x \leq y \leq c$ . So outcome 3 holds.

step 2.3L1algebra

3.3

If [L1] gives a complete or anticomplete $(k, ∣ F ∣ / k^{c_{2} + 6 / c_{3}})$ -blockade with $k \geq y^{- c_{3}}$ , then $\frac{∣ F ∣}{k^{c_{2} + 6 / c_{3}}} \geq \frac{c ∣ G ∣}{k^{c_{2} + 6 / c_{3}}} \geq \frac{y ∣ G ∣}{k^{c_{2} + 6 / c_{3}}} \geq \frac{∣ G ∣}{k^{c_{2} + 7 / c_{3}}},$ because $k \geq y^{- c_{3}}$ implies $k^{1 / c_{3}} \geq y^{- 1}$ . Hence outcome 4 holds.

step 2.3L1algebra

3.4

If [L1] gives a pure $(ℓ, ∣ F ∣ / ℓ^{8})$ -blockade with $ℓ \in [y^{- 1}, x^{- 2}]$ , then $\frac{∣ F ∣}{ℓ^{8}} \geq \frac{c ∣ G ∣}{ℓ^{8}} \geq \frac{y ∣ G ∣}{ℓ^{8}} \geq \frac{∣ G ∣}{ℓ^{9}},$ again because $ℓ \geq y^{- 1}$ . Thus outcome 5 holds.

step 2.3L1algebra

4.1

The exhaustive alternatives 2.1 and 2.2, together with steps 3.1-3.4, show that one of the five stated outcomes always holds.

step 2.2step 2.3step 3.1step 3.2step 3.3step 3.4cases-exhaustive∎

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

Under failure of the global outcomes, a large y^(10/3)-restricted induced subgraph forces a y^(11/3)-restricted induced subgraph

Statement

Let $F$ have property $(*)$ and be leaf-reducible, and let $c_{1}, c_{2}, c_{3} > 0$ , $c_{4}, c_{5} \geq 4$ , and $c : = 2^{- 4 c_{5}}$ be the constants from Property (*) and leaf reducibility yield a long x-sparse or complete blockade, or a better outcome. Fix $x \in (0, c^{10}]$ , and let $G$ be a $c^{10}$ -restricted $\overline{F}$ -free graph for which none of the following holds:

$G$ has an $x$ -restricted induced subgraph with at least $x^{22 c_{4}} ∣ G ∣$ vertices;
$G$ has a clique or stable set of size at least $(x^{30 c_{4}} ∣ G ∣)^{c_{1}}$ ;
$G$ has a complete or anticomplete $(k, ∣ G ∣ / k^{c_{2} + 27 c_{4} / c_{3}})$ -blockade for some real $k \geq 2$ ;
$G$ has a pure or $x$ -sparse $(ℓ, ∣ G ∣ / ℓ^{29 c_{4}})$ -blockade for some real $ℓ \in [c^{- 1}, x^{- 2}]$ .

Then for every $y \in [x, c^{3}]$ and every $y^{10 / 3}$ -restricted induced subgraph $F$ of $G$ with $∣ F ∣ \geq y^{10 (c_{4} + 2)} ∣ G ∣$ , there exists a $y^{11 / 3}$ -restricted induced subgraph of $F$ with at least $y^{c_{4} + 2} ∣ F ∣$ vertices.

Facts & Assumptions

Given: The data and failure hypotheses in the Statement, together with a parameter $y \in [x, c^{3}]$ and an induced subgraph $F$ of $G$ that is $y^{10 / 3}$ -restricted and satisfies $∣ F ∣ \geq y^{10 (c_{4} + 2)} ∣ G ∣$ .

[L1]

The previous lemma says that every $c y^{3}$ -restricted $\overline{F}$ -free graph satisfies one of five outcomes: a long $x$ -sparse or complete blockade, a $2 y^{4}$ -restricted induced subgraph, a clique or stable set, a complete or anticomplete blockade, or a pure blockade (Property (*) and leaf reducibility yield a long x-sparse or complete blockade, or a better outcome).

[L2]

If a set is $η$ -restricted, then it is also $η^{'}$ -restricted for every $η^{'} \geq η$ ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

Proof

technique · apply the previous lemma to $F$ with parameter $y$ and show that every outcome except the deeper restricted-set outcome contradicts one of the assumed global failures

1.1

Because $y \leq c^{3}$ , one has $y^{10 / 3} = y^{3} y^{1 / 3} \leq c y^{3}$ . Thus [L2] upgrades the hypothesis that $F$ is $y^{10 / 3}$ -restricted to the statement that $F$ is $c y^{3}$ -restricted.

givenL2algebra

2.1

Apply [L1] to the graph $F$ with the original parameter $x$ and the current parameter $y$ . One of the five outcomes of [L1] holds for $F$ .

step 1.1L1

3.1

Suppose the first outcome of [L1] holds for $F$ : there is an $x$ -sparse or complete blockade in $F$ of length at least $y^{- 1}$ and width at least $y^{c_{4} + 2} ∣ F ∣$ . Since $y^{- 1} \in [c^{- 1}, x^{- 1}] \subseteq [c^{- 1}, x^{- 2}]$ and $y^{c_{4} + 2} ∣ F ∣ \geq y^{11 (c_{4} + 2)} ∣ G ∣ \geq y^{29 c_{4}} ∣ G ∣,$ this produces the forbidden global outcome 4.

step 2.1algebra

3.2

Suppose the second outcome of [L1] holds for $F$ . Because $2 y^{4} \leq y^{11 / 3}$ for $0 < y < 1$ , the resulting induced subgraph is already the desired $y^{11 / 3}$ -restricted induced subgraph of size at least $y^{c_{4} + 2} ∣ F ∣$ .

step 2.1algebra

3.3

Suppose the third outcome of [L1] holds for $F$ . Then $(x^{10} ∣ F ∣)^{c_{1}} \geq (x^{10} \cdot y^{10 (c_{4} + 2)} ∣ G ∣)^{c_{1}} \geq (x^{10 c_{4} + 30} ∣ G ∣)^{c_{1}} \geq (x^{30 c_{4}} ∣ G ∣)^{c_{1}},$ because $y \geq x$ and $c_{4} \geq 4$ . This contradicts the failure of global outcome 2.

step 2.1algebra

3.4

Suppose the fourth outcome of [L1] holds for $F$ : there is a complete or anticomplete $(k, ∣ F ∣ / k^{c_{2} + 7 / c_{3}})$ -blockade with $k \geq y^{- c_{3}}$ . If $k \geq 2$ , then $\frac{∣ F ∣}{k^{c_{2} + 7 / c_{3}}} \geq \frac{y^{10 (c_{4} + 2)} ∣ G ∣}{k^{c_{2} + 7 / c_{3}}} \geq \frac{∣ G ∣}{k^{c_{2} + 7 / c_{3} + 10 (c_{4} + 2) / c_{3}}} \geq \frac{∣ G ∣}{k^{c_{2} + 27 c_{4} / c_{3}}},$ so global outcome 3 holds, a contradiction. If instead $1 < k < 2$ , then the blockade has at least two blocks, and $\frac{∣ F ∣}{k^{c_{2} + 7 / c_{3}}} \geq \frac{∣ F ∣}{2^{c_{2} + 7 / c_{3}}} \geq \frac{∣ G ∣}{2^{c_{2} + 7 / c_{3} + 10 (c_{4} + 2) / c_{3}}} \geq \frac{∣ G ∣}{2^{c_{2} + 27 c_{4} / c_{3}}},$ because $∣ F ∣ \geq y^{10 (c_{4} + 2)} ∣ G ∣$ , the inequality $y^{- c_{3}} \leq k < 2$ implies $y^{10 (c_{4} + 2)} \geq 2^{- 10 (c_{4} + 2) / c_{3}}$ , and $7 + 10 (c_{4} + 2) \leq 27 c_{4}$ for $c_{4} \geq 4$ . Thus $G$ has a complete or anticomplete $(2, ∣ G ∣ / 2^{c_{2} + 27 c_{4} / c_{3}})$ -blockade, again contradicting the failure of global outcome 3.

step 2.1algebra

3.5

Suppose the fifth outcome of [L1] holds for $F$ : there is a pure $(ℓ, ∣ F ∣ / ℓ^{9})$ -blockade with $ℓ \in [y^{- 1}, x^{- 2}]$ . Then $\frac{∣ F ∣}{ℓ^{9}} \geq \frac{y^{10 (c_{4} + 2)} ∣ G ∣}{ℓ^{9}} \geq \frac{∣ G ∣}{ℓ^{29 c_{4}}},$ because $ℓ \geq y^{- 1}$ . This again gives the forbidden global outcome 4.

step 2.1algebra

4.1

The first, third, fourth, and fifth cases are impossible under the standing global failure hypotheses. Therefore the second case, recorded in step 3.2, must hold, which is exactly the desired conclusion.

step 3.1step 3.2step 3.3step 3.4step 3.5∎

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-05Open item page →

Constant-scale restricted property (*) yields a restricted subgraph, a polynomial clique or stable set, or two blockade alternatives

Statement

Suppose that $F$ has property $(*)$ and is leaf-reducible. Then there exist constants $c_{1}, c_{2}, c_{3} > 0$ , $c_{4}, c_{5} \geq 4$ , and $c : = 2^{- 4 c_{5}}$ such that for every $x \in (0, c^{10}]$ and every $c^{10}$ -restricted $\overline{F}$ -free graph $G$ , at least one of the following holds:

$G$ has an $x$ -restricted induced subgraph with at least $x^{22 c_{4}} ∣ G ∣$ vertices;
$G$ has a clique or stable set of size at least $(x^{30 c_{4}} ∣ G ∣)^{c_{1}}$ ;
$G$ has a complete or anticomplete $(k, ∣ G ∣ / k^{c_{2} + 27 c_{4} / c_{3}})$ -blockade for some real $k \geq 2$ ;
$G$ has a pure or $x$ -sparse $(ℓ, ∣ G ∣ / ℓ^{29 c_{4}})$ -blockade for some real $ℓ \in [c^{- 1}, x^{- 2}]$ .

Facts & Assumptions

Given: A finite family $F$ with property $(*)$ and leaf-reducible, an $x \in (0, c^{10}]$ , and a $c^{10}$ -restricted $\overline{F}$ -free graph $G$ .

[L1]

The previous claim says that, under the failure of outcomes 2-4, every $y^{10 / 3}$ -restricted induced subgraph of sufficiently large relative size has a deeper $y^{11 / 3}$ -restricted induced subgraph (Under failure of the global outcomes, a large y^(10/3)-restricted induced subgraph forces a y^(11/3)-restricted induced subgraph).

[L2]

If a graph has a $c^{10}$ -restricted induced subgraph of size at least $(c^{10})^{3 (c_{4} + 2)} ∣ G ∣$ and every $λ$ -restricted induced subgraph of size at least $λ^{3 (c_{4} + 2)} ∣ G ∣$ contains a $λ^{11 / 10}$ -restricted induced subgraph of size at least $λ^{3 (c_{4} + 2) / 10}$ times as many vertices, then the graph has an $x^{10 / 3}$ -restricted induced subgraph with at least $x^{11 (c_{4} + 2)} ∣ G ∣$ vertices (Iterated restricted sparsification reaches the target scale).

[L3]

If a set is $x^{10 / 3}$ -restricted, then it is $x$ -restricted ( $c$ -sparse, $c$ -dense and $c$ -restricted vertex sets).

Proof

Proof technique: if outcomes 2-4 fail, verify the hypotheses of the iterative restricted-sparsification lemma with $b_{1} = \frac{11}{10}$ , $b_{2} = 3 (c_{4} + 2)$ , and $b_{3} = \frac{3 (c_{4} + 2)}{10}$ .

1.1

Let $c_{1}, c_{2}, c_{3} > 0$ , $c_{4}, c_{5} \geq 4$ , and $c : = 2^{- 4 c_{5}}$ be the constants from Under failure of the global outcomes, a large y^(10/3)-restricted induced subgraph forces a y^(11/3)-restricted induced subgraph, and set $b_{1} : = 11 / 10, b_{2} : = 3 (c_{4} + 2), b_{3} : = 3 (c_{4} + 2) / 10.$

L1choose

1.2

Suppose outcomes 2, 3, and 4 all fail. We will show that outcome 1 then holds.

givenassume-contra

2.1

Hypothesis 1 of [L2] is immediate: the graph $G$ itself is $c^{10}$ -restricted and has size $∣ G ∣ \geq (c^{10})^{b_{2}} ∣ G ∣$ because $b_{2} > 0$ and $c^{10} < 1$ .

step 1.1L2givenalgebra

2.2

Let $λ \in [x^{10 / 3}, c^{10}]$ and let $F$ be a $λ$ -restricted induced subgraph of $G$ with $∣ F ∣ \geq λ^{b_{2}} ∣ G ∣$ . Write $λ = y^{10 / 3}$ , so $y = λ^{3 / 10} \in [x, c^{3}]$ . Then $∣ F ∣ \geq y^{10 (c_{4} + 2)} ∣ G ∣$ . Since outcomes 2-4 fail globally, [L1] applied with this $y$ gives a $y^{11 / 3} = λ^{11 / 10}$ -restricted induced subgraph of $F$ with at least $y^{c_{4} + 2} ∣ F ∣ = λ^{b_{3}} ∣ F ∣$ vertices.

step 1.1step 1.2L1L2algebra

2.3

The exponent condition for [L2] holds because $b_{1} b_{2} = \frac{11}{10} \cdot 3 (c_{4} + 2) = \frac{33 (c_{4} + 2)}{10} \geq \frac{30 (c_{4} + 2)}{10} = b_{2} + b_{3} .$

step 1.1L2algebra

3.1

Therefore [L2] yields an $x^{10 / 3}$ -restricted induced subgraph $S \subseteq G$ with at least $(x^{10 / 3})^{b_{1} b_{2}} ∣ G ∣ = x^{11 (c_{4} + 2)} ∣ G ∣$ vertices. Since $c_{4} \geq 4$ , the exponent satisfies $11 (c_{4} + 2) \leq 22 c_{4}$ , so $∣ S ∣ \geq x^{22 c_{4}} ∣ G ∣$ . By [L3], the subgraph $S$ is $x$ -restricted. Hence outcome 1 holds.

step 2.1step 2.2step 2.3L2L3algebra

4.1

Outcome 1 follows whenever outcomes 2-4 fail. Hence at least one of the four stated outcomes always holds.

step 1.2step 3.1discharge-contradiction∎

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

Rödl initialization removes the constant-scale restriction in the property (*) four-outcome theorem

Statement

Suppose that $F$ has property $(*)$ and is leaf-reducible. Then there exist constants $c_{1} > 0$ , $c_{4} \geq 4$ , and $d \geq 58 c_{4}$ such that for every $x \in (0, 2^{- d})$ and every $\overline{F}$ -free graph $G$ with $∣ G ∣ \geq x^{- d}$ , at least one of the following holds:

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

Facts & Assumptions

Given: A finite family $F$ with property $(*)$ and leaf-reducible, a parameter $x \in (0, 2^{- d})$ , and an $\overline{F}$ -free graph $G$ with $∣ G ∣ \geq x^{- d}$ .

[L1]

The constant-scale four-outcome theorem gives constants $c_{1}, c_{2}, c_{3} > 0$ , $c_{4}, c_{5} \geq 4$ , and $c : = 2^{- 4 c_{5}}$ such that every $c^{10}$ -restricted $\overline{F}$ -free graph satisfies one of the four outcomes on the current page (Constant-scale restricted property (*) yields a restricted subgraph, a polynomial clique or stable set, or two blockade alternatives).

[L2]

For $ξ : = c^{10}$ , every $\overline{F}$ -free graph has a $ξ$ -restricted induced subgraph of size at least $δ ∣ G ∣$ for some $δ > 0$ (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 · apply Rödl at the fixed scale $\xi=c^{10}$, then transfer each outcome of the constant-scale theorem back to $G$ by choosing $d$ large enough

1.1

Let $c_{1}, c_{2}, c_{3} > 0$ , $c_{4}, c_{5} \geq 4$ , and $c : = 2^{- 4 c_{5}}$ be the constants from [L1], and set $ξ : = c^{10}$ . Let $δ > 0$ be the constant from [L2] for the family $\overline{F}$ and the parameter $ξ$ .

L1L2choose

2.1

Choose $d$ so large that $d \geq 58 c_{4}, 2^{- d} < c^{10}, δ \geq 2^{116 c_{4} - d}, δ \geq 2^{c_{2} + 27 c_{4} / c_{3} - d} .$

step 1.1choose

3.1

By [L2], the graph $G$ has a $ξ$ -restricted induced subgraph $F \subseteq G$ with $∣ F ∣ \geq δ ∣ G ∣$ . Since $x < 2^{- d} < ξ$ , the parameter $x$ lies in the range allowed by [L1], so [L1] applies to $F$ .

step 2.1L1L2

4.1

If [L1] gives an $x$ -restricted induced subgraph of $F$ with at least $x^{22 c_{4}} ∣ F ∣$ vertices, then $x^{22 c_{4}} ∣ F ∣ \geq x^{22 c_{4}} δ ∣ G ∣ \geq x^{22 c_{4}} 2^{58 c_{4} - d} ∣ G ∣ \geq x^{23 c_{4}} ∣ G ∣,$ because $x < 2^{- d}$ implies $x^{c_{4}} \leq 2^{58 c_{4} - d}$ . Thus outcome 1 holds.

step 2.1step 3.1L1algebra

4.2

If [L1] gives a clique or stable set of size at least $(x^{30 c_{4}} ∣ F ∣)^{c_{1}}$ , then the same estimate yields $(x^{30 c_{4}} ∣ F ∣)^{c_{1}} \geq (x^{31 c_{4}} ∣ G ∣)^{c_{1}}$ , so outcome 3 holds.

step 2.1step 3.1L1algebra

4.3

If [L1] gives a complete or anticomplete $(k, ∣ F ∣ / k^{c_{2} + 27 c_{4} / c_{3}})$ -blockade with $k \geq 2$ , let $j : = ⌈ k ⌉$ . Its actual length is integral and at least $k$ , hence at least $j$ , while $\frac{∣ F ∣}{k^{c_{2} + 27 c_{4} / c_{3}}} \geq \frac{δ ∣ G ∣}{k^{c_{2} + 27 c_{4} / c_{3}}} \geq \frac{∣ G ∣}{k^{d}} \geq \frac{∣ G ∣}{j^{d}} .$ Thus the same blocks form a complete or anticomplete $(j, ∣ G ∣ / j^{d})$ -blockade. If $j \geq x^{- 1}$ this is outcome 4; if $j < x^{- 1}$ , then the integer $j \in [2, x^{- 1}]$ gives outcome 2.

step 2.1step 3.1L1algebrachoosecases

4.4

If [L1] gives a pure or $x$ -sparse $(ℓ, ∣ F ∣ / ℓ^{29 c_{4}})$ -blockade with $ℓ \in [c^{- 1}, x^{- 2}]$ , set $k : = ⌊ \sqrt{ℓ} ⌋ .$ Then $k$ is an integer in $[2, x^{- 1}]$ , because $ℓ \geq c^{- 1} \geq 2^{4}$ and $\sqrt{ℓ} \leq x^{- 1}$ . The blockade has length at least $ℓ \geq k$ , and $ℓ < (k + 1)^{2} \leq 4 k^{2}$ , so $\frac{∣ F ∣}{ℓ^{29 c_{4}}} \geq \frac{∣ F ∣}{(4 k^{2})^{29 c_{4}}} = \frac{∣ F ∣}{2^{58 c_{4}} k^{58 c_{4}}} \geq \frac{δ ∣ G ∣}{2^{58 c_{4}} k^{58 c_{4}}} \geq \frac{∣ G ∣}{k^{d}},$ because $k \geq 2$ and step 2.1 gives $δ \geq 2^{116 c_{4} - d}$ . Hence outcome 2 holds.

step 2.1step 3.1L1algebrachoose

5.1

The four branches 4.1-4.4 exhaust the conclusion of [L1], so one of the stated outcomes always holds for $G$ .

step 3.1step 4.1step 4.2step 4.3step 4.4cases-exhaustive∎

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

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.1

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

givenL1algebra

2.1

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

step 1.1L1

3.1

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.

step 2.1algebra

3.2

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.

step 2.1algebra

3.3

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.

step 2.1L3algebra

4.1

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.

step 3.1step 3.2step 3.3∎

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-05Open item page →

Property (*) and leaf reducibility imply generalized niceness

Statement

Let $F$ be a finite family of graphs. If $F$ has property $(*)$ and $F$ is leaf-reducible, then $F$ is generalized nice.

Facts & Assumptions

Given: A finite family $F$ with property $(*)$ and leaf-reducible.

[L1]

There exist constants $c_{1}^{'} > 0$ , $c_{4}^{'} \geq 4$ , and $d \geq 58 c_{4}^{'}$ such that, for every $x \in (0, 2^{- d})$ , every $\overline{F}$ -free graph of size at least $x^{- d}$ satisfies the four-outcome theorem with parameter $x$ (Rödl initialization removes the constant-scale restriction in the property (*) four-outcome theorem).

[L2]

Under the failure of the clique/stable-set, complete-or-anticomplete blockade, and restricted-set outcomes, every induced subgraph of size at least $ϵ^{d} ∣ G ∣$ has a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some integer $k \in [2, x^{- 1}]$ when $x = ϵ^{5 d}$ , provided $∣ G ∣ \geq ϵ^{- 10 d^{2}}$ (Large induced subgraphs in the property (*) four-outcome theorem contain a pure or x-sparse polynomial blockade).

[L3]

If every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ has a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some $k \in [2, x^{- 1}]$ , where $x = ϵ^{5 d}$ and $∣ G ∣ \geq ϵ^{- 10 d^{2}}$ , then $G$ has an $(ϵ^{- 1}, ϵ^{10 d^{2}} ∣ G ∣)$ -blockade whose distinct block pairs are pairwise complete or weakly $ϵ^{d}$ -sparse (Local pure or $x$ -sparse blockades yield a nice blockade).

[L4]

The definition of generalized niceness is the four-outcome schema in Generalized nice finite graph families.

Proof

technique · choose the source exponents, assume the last three generalized-nice outcomes fail, and then force the first outcome by the local pure-or-sparse blockade theorem

1.1

Let $c_{1}^{'} > 0$ , $c_{4}^{'} \geq 4$ , and $d \geq 58 c_{4}^{'}$ be the constants from [L1]. Set $c_{1} : = 10 d^{2}, c_{2} : = d, c_{3} : = 156 c_{4}^{'} d, c_{4} : = c_{1}^{'}, c_{5} : = 2 d, c_{6} : = 5 d, c_{7} : = 5 d, c_{8} : = 116 c_{4}^{'} d .$ Then $c_{1} \geq 3$ , $c_{2} \geq 8$ , $c_{6} \geq 1$ , and $c_{7} \geq 4$ .

L1choosealgebra

2.1

Let $G$ be an $\overline{F}$ -free graph and let $ϵ \in (0, \frac{1}{2})$ . If outcome 2, 3, or 4 of [L4] already holds for these constants, there is nothing left to prove. So assume for contradiction that all three fail, and write $x : = ϵ^{5 d}$ .

step 1.1L4assume-contra

3.1

If $∣ G ∣ < ϵ^{- 1}$ , then $ϵ^{c_{3}} ∣ G ∣ \leq ϵ^{c_{3} - 1} \leq 1,$ because $c_{3} > 1$ . Any vertex of $G$ therefore gives a clique or stable set of size at least $(ϵ^{c_{3}} ∣ G ∣)^{c_{4}}$ , so outcome 2 of [L4] holds. Hence we may assume that $∣ G ∣ \geq ϵ^{- 1}$ .

step 1.1step 2.1L4algebracases

4.1

If $∣ G ∣ \leq ϵ^{- 10 d^{2}}$ , then choose $⌈ ϵ^{- 1} ⌉$ distinct vertices of $G$ and make them singleton blocks. Step 3.1 makes this possible, and each singleton has size $1 \geq ϵ^{10 d^{2}} ∣ G ∣ = ϵ^{c_{1}} ∣ G ∣ .$ Every pair of singleton blocks is either complete or anticomplete, hence either complete or weakly $ϵ^{d}$ -sparse. Thus outcome 1 of [L4] holds. Therefore we may assume that $∣ G ∣ \geq ϵ^{- 10 d^{2}}$ .

step 1.1step 3.1L4choosealgebracases

5.1

Under steps 2.1 and 4.1, [L2] applies to every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ .

step 2.1step 4.1L2

6.1

If an induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ contained 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 ∣ = ϵ^{c_{3}} ∣ G ∣,$ so outcome 2 would hold, contrary to step 2.1. Likewise, if such an $F$ contained a complete or anticomplete $(k, ∣ F ∣ / k^{d})$ -blockade with $k \geq x^{- 1}$ , then $\frac{∣ F ∣}{k^{d}} \geq \frac{ϵ^{d} ∣ G ∣}{k^{d}} \geq \frac{∣ G ∣}{k^{2 d}},$ so outcome 3 would hold, again contrary to step 2.1. Therefore [L2] really does give the pure-or- $x$ -sparse blockade alternative on every such $F$ .

step 2.1step 5.1L2algebra

7.1

By steps 4.1 and 6.1, the hypotheses of [L3] are satisfied with the parameter $d$ and $x = ϵ^{5 d}$ : the graph $G$ has order at least $ϵ^{- 10 d^{2}}$ , and every induced subgraph $F$ with $∣ F ∣ \geq ϵ^{d} ∣ G ∣$ has a pure or $x$ -sparse $(k, ∣ F ∣ / k^{d})$ -blockade for some integer $k \in [2, x^{- 1}]$ . Hence $G$ has an $(ϵ^{- 1}, ϵ^{10 d^{2}} ∣ G ∣)$ -blockade whose distinct block pairs are either complete or weakly $ϵ^{d}$ -sparse. This is exactly outcome 1 of [L4], because $c_{1} = 10 d^{2}$ and $c_{2} = d$ .

step 1.1step 4.1step 5.1step 6.1L3L4

8.1

Outcome 1 follows whenever outcomes 2, 3, and 4 fail, and step 1.1 records the remaining lower-bound requirements on the constants. Therefore the constants from step 1.1 satisfy Definition [L4], so $F$ is generalized nice.

step 1.1step 2.1step 7.1L4discharge-contradiction∎

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-05Open item page →

A four-tooth comb with a special vertex realizes the trigger configuration for property (*)

Example

Let $G$ have vertices

v, a_{1}, a_{2}, a_{3}, a_{4}, b_{i, j} (i, j \in [4])

with edges exactly $a_{i} b_{i, j}$ and $v b_{i, j}$ for $i, j \in [4]$ . Put

B_{i} : = {b_{i, 1}, b_{i, 2}, b_{i, 3}, b_{i, 4}}

for each $i$ .

Facts & Assumptions

Given: The graph and the blocks displayed in the Example.

[L1]

The item Combs in a graph characterizes an $(ℓ, w)$ -comb by the blockade conditions and the adjacency pattern of the teeth.

[L2]

If a finite family $F$ has property $(*)$ and $G$ is $\overline{F}$ -free, then an $(ℓ, w)$ -comb with $ℓ, w \geq 4$ together with a vertex outside the comb that is complete to the blocks and anticomplete to the teeth is the antecedent of the three-outcome implication in Property (*) for a finite graph family.

Verification

technique · direct

1.1

The four sets $B_{1}, B_{2}, B_{3}, B_{4}$ are pairwise disjoint and each has $4$ vertices, so $(B_{1}, B_{2}, B_{3}, B_{4})$ is a $(4, 4)$ -blockade.

givenL1

2.1

Each tooth $a_{i}$ is adjacent to every vertex of $B_{i}$ and to no vertex of $B_{j}$ for $j \neq i$ , and the teeth $a_{1}, a_{2}, a_{3}, a_{4}$ are distinct and lie outside the blocks. Hence $((a_{i}, B_{i}) : i \in [4])$ is a $(4, 4)$ -comb by [L1].

step 1.1L1

3.1

The vertex $v$ lies outside the comb, is adjacent to every vertex in $⋃_{i = 1}^{4} B_{i}$ , and is nonadjacent to every $a_{i}$ . Since this comb has $ℓ = w = 4$ , the pair consisting of the comb and $v$ realizes the geometric trigger configuration occurring in [L2]. No assertion that an unspecified family has property $(*)$ is being made.

step 2.1L2∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

The third outcome of property (*) gives a pure four-blockade

Example

Assume the trigger hypothesis of property $(*)$ holds for a comb of length $ℓ = 4$ and width $w$ . If the third outcome of property $(*)$ occurs, the resulting blockade is pure with width $w / ℓ^{2}$ .

Facts & Assumptions

Given: A special-vertex comb with $ℓ = 4$ and width $w$ .

[L1]

The third branch in Property (*) for a finite graph family gives a pure $(ℓ, w / ℓ^{2})$ -blockade.

Verification

technique · direct

1.1

Applying [L1] with $ℓ = 4$ yields a pure blockade whose width is $\frac{w}{ℓ^{2}} = \frac{w}{16} .$

L1algebra

2.1

Since [L1] names the blockade pure rather than complete or anticomplete, this branch keeps exactly the distinction used later on the A page: every pair of blocks is pure, but no stronger global uniformity is asserted.

step 1.1L1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

A numerical square-root rescaling identity

Example

As a standalone numerical illustration, take

c_{4} : = 4, d : = 232 = 58 c_{4}, ℓ : = 256, k : = \sqrt{ℓ} = 16,

and assume $∣ F ∣ \geq ∣ G ∣$ .

Facts & Assumptions

Given: The numerical choices in the Example.

[A1]

The sample values satisfy the numerical relation $d = 58 c_{4}$ . They are not asserted to be the existential constants supplied by the source lemma.

Verification

technique · direct arithmetic

1.1

Since $k = \sqrt{ℓ}$ , one has $ℓ^{29 c_{4}} = (k^{2})^{29 c_{4}} = k^{58 c_{4}} = k^{d} .$

A1algebra

2.1

Therefore $\frac{∣ F ∣}{ℓ^{29 c_{4}}} = \frac{∣ F ∣}{k^{d}} \geq \frac{∣ G ∣}{k^{d}},$ using the assumption $∣ F ∣ \geq ∣ G ∣$ .

step 1.1algebra

3.1

This standalone calculation isolates the square-root renormalization: after replacing $ℓ$ by $k = \sqrt{ℓ}$ , the width bound takes exactly the target form $∣ G ∣ / k^{d}$ when the numerical relation $d = 58 c_{4}$ holds.

step 2.1∎

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-05Open item page →

The epsilon^(5d) substitution in Claim 4.5.1 and Lemma 4.5

Example

Take

ϵ : = \frac{1}{4}, c_{4}^{'} : = 4, d : = 232 = 58 c_{4}^{'}, x : = ϵ^{5 d} .

Then the four exponent comparisons in the final property-(*) reduction become explicit.

Facts & Assumptions

Given: The displayed values of $ϵ$ , $d$ , $c_{4}^{'}$ , and $x$ .

[A1]

Since $ϵ = \frac{1}{4} < \frac{1}{2}$ , the powers of $ϵ$ decrease as their exponents increase.

Verification

technique · direct arithmetic

1.1

The defining substitution gives $x = ϵ^{5 d} = 2^{- 10 d} < 2^{- d} .$ Together with $d = 58 c_{4}^{'}$ , this verifies the two parameter inequalities required before applying the Rödl-initialized theorem; its separate graph-order hypothesis must also be checked in any application.

A1algebra

1.2

For the restricted-set branch, $x^{23 c_{4}^{'}} ϵ^{d} = ϵ^{115 c_{4}^{'} d + d} \geq ϵ^{116 c_{4}^{'} d},$ because $115 c_{4}^{'} + 1 \leq 116 c_{4}^{'}$ when $c_{4}^{'} = 4$ .

A1algebra

1.3

For the clique-or-stable-set branch, $x^{31 c_{4}^{'}} ϵ^{d} = ϵ^{155 c_{4}^{'} d + d} \geq ϵ^{156 c_{4}^{'} d},$ because $155 c_{4}^{'} + 1 \leq 156 c_{4}^{'}$ .

A1algebra

2.1

If $k \geq x^{- 1}$ , then $ϵ^{d} = x^{1 / 5} \geq k^{- 1 / 5},$ so $\frac{ϵ^{d}}{k^{d}} \geq \frac{1}{k^{2 d}} .$ This is exactly the comparison used to turn the complete-or-anticomplete blockade branch into the generalized-nice blockade outcome.

step 1.1A1algebra

3.1

These computations are the concrete numerical version of the four exponent transfers behind the local blockade claim and the final proof of generalized niceness.

step 1.2step 1.3step 2.1∎

Property (*) and Comb Outcomes

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Property (*) for a finite graph family

Definition

Property (*) and leaf reducibility yield five comb outcomes in a restricted graph

Statement

Facts & Assumptions

Proof

Property (*) and leaf reducibility yield a long x-sparse or complete blockade, or a better outcome

Statement

Facts & Assumptions

Proof

Under failure of the global outcomes, a large y^(10/3)-restricted induced subgraph forces a y^(11/3)-restricted induced subgraph

Statement

Facts & Assumptions

Proof

Constant-scale restricted property (*) yields a restricted subgraph, a polynomial clique or stable set, or two blockade alternatives

Statement

Facts & Assumptions

Proof

Rödl initialization removes the constant-scale restriction in the property (*) four-outcome theorem

Statement

Facts & Assumptions

Proof

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

Statement

Facts & Assumptions

Proof

Property (*) and leaf reducibility imply generalized niceness

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

A four-tooth comb with a special vertex realizes the trigger configuration for property (*)

Example

Facts & Assumptions

Verification

The third outcome of property (*) gives a pure four-blockade

Example

Facts & Assumptions

Verification

A numerical square-root rescaling identity

Example

Facts & Assumptions

Verification

The epsilon^(5d) substitution in Claim 4.5.1 and Lemma 4.5

Example

Facts & Assumptions

Verification

Sources