ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-04

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.

A numeric run of the Lemma 3.3 exponent choice

Example

Suppose the three-outcome constants for a generalized nice, leaf-reducible, wonderful family satisfy

$c_{3} = c_{4} = 4, c = \frac{1}{4}, x = 2^{- 10} .$

Then the exponent choices in the final restricted-sparsification step become

$b_{1} = \frac{c_{4}}{2} = 2, b_{2} = \frac{4 c_{3}}{c_{4}} = 4, b_{3} = c_{3} = 4,$

$b_{1} b_{2} = 8 = b_{2} + b_{3} .$

Let $G$ be a $c^{2}$ -restricted $\overline{F}$ -free graph satisfying the two global failure hypotheses of the helper lemma. If $c y \in [x, c^{2}]$ , then the helper asks for a $c y$ -restricted induced subgraph $F$ of size at least $(c y)^{4} ∣ G ∣$ and returns a $(c y)^{2}$ -restricted induced subgraph of size at least $(c y)^{4} ∣ F ∣$ . The iterative lemma then yields an $x$ -restricted induced subgraph of size at least $x^{8} ∣ G ∣$ .

Facts & Assumptions

Given: The numerical choices $c_{3} = c_{4} = 4$ , $c = \frac{1}{4}$ , and $x = 2^{- 10}$ , and a graph $G$ satisfying the conditional hypotheses in the Example.

[L1]

The helper claim uses the substitutions $b_{1} = c_{4} / 2$ , $b_{2} = 4 c_{3} / c_{4}$ , and $b_{3} = c_{3}$ (A large cy-restricted subgraph in the three-outcome theorem forces a smaller-scale restricted subgraph).

[L2]

The iterative restricted-sparsification lemma concludes with an $x$ -restricted induced subgraph of size at least $x^{b_{1} b_{2}} ∣ G ∣$ (Iterated restricted sparsification reaches the target scale).

[L3]

The final generalized-niceness lemma is obtained by exactly this choice of $b_{1}, b_{2}, b_{3}$ (Constant-scale restricted generalized niceness yields an x-scale restricted subgraph, a polynomial clique or stable set, or a blockade).

Verification

technique · direct arithmetic

1.1

Substituting the given values into [L1] gives $b_{1} = 2$ , $b_{2} = 4$ , and $b_{3} = 4$ . Therefore $b_{1} b_{2} = 8 = b_{2} + b_{3}$ , so the numerical inequality required by the iterative lemma holds exactly.

L1givenalgebra

2.1

The graph $G$ itself supplies the starting $c^{2}$ -restricted subgraph required by [L2], because $∣ G ∣ \geq (c^{2})^{b_{2}} ∣ G ∣$ . For every $λ \in [x, c^{2}]$ , write $λ = c y$ . The helper [L1], under the two global failure hypotheses in the Given data, sends each $λ$ -restricted $F$ with $∣ F ∣ \geq λ^{b_{2}} ∣ G ∣ = λ^{4} ∣ G ∣$ to a $λ^{b_{1}}$ -restricted subgraph of size at least $λ^{b_{3}} ∣ F ∣ = λ^{4} ∣ F ∣$ . Thus both hypotheses of [L2] hold with starting constant $c^{2}$ , and it gives an $x$ -restricted induced subgraph of size at least $x^{b_{1} b_{2}} ∣ G ∣ = x^{8} ∣ G ∣$ .

step 1.1L1L2givenalgebra

3.1

This is exactly the numerical exponent pattern used again in [L3].

step 2.1L3∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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, Erdos-Hajnal beyond the five-vertex path, Claim 3.3.1 and Lemma 3.3 (standard reference, not scraped)