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

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 large Y-part in a structural comb partition

Example

Assume $(F_{1}, F_{2}; H)$ satisfies the structural comb-partition hypothesis and $c = 1 / 2$ is an Erdős–Hajnal constant for both $F_{1}$ -free and $F_{2}$ -free graphs. Let $G$ be a finite $\overline{H}$ -free graph containing an $(ℓ, 16)$ -comb with $ℓ \geq 4$ , equipped with a structural partition. If one part has $∣ Y_{i} ∣ = 8$ , the large- $Y$ lemma supplies a clique or stable set in $G$ of size at least $16^{1 / 4} = 2$ .

Facts & Assumptions

Given: The families satisfying the structural comb-partition hypothesis, their common Erdős–Hajnal constant $c = 1 / 2$ , the finite $\overline{H}$ -free graph $G$ and its structurally partitioned $(ℓ, w)$ -comb with $ℓ \geq 4$ , $w = 16$ , and an index $i$ with $∣ Y_{i} ∣ = 8$ .

[F1]

Under the structural comb-partition hypothesis, with a common Erdős–Hajnal constant $c \in (0, 1]$ for the two forbidden families and a structurally partitioned $(ℓ, w)$ -comb with $ℓ, w \geq 4$ , a part with $∣ Y_{i} ∣ \geq w / 2$ yields a clique or stable set in $G$ of size at least $w^{c / 2}$ (A large Y-part in a structural comb partition yields the clique-or-stable-set outcome).

Verification

technique · direct calculation

1.1

The structural and common-constant hypotheses of [F1] are given. Also $c = 1 / 2 \in (0, 1]$ , $ℓ \geq 4$ , $w = 16 \geq 4$ , and $∣ Y_{i} ∣ = 8 = 16 / 2 = w / 2$ . Thus [F1] gives a clique or stable set in $G$ with at least $16^{(1 / 2) / 2}$ vertices.

givenF1

1.2

The displayed lower bound is $16^{(1 / 2) / 2} = 16^{1 / 4} = 2$ .

algebra

2.1

Hence, under the stated structural hypotheses, $G$ has a clique or stable set with at least two vertices, as asserted.

step 1.1step 1.2∎

Depends on

A large Y-part in a structural comb partition yields the clique-or-stable-set outcome

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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

Huang, Ju, and Zhou, Erdős–Hajnal beyond the five-vertex path, proof of Lemma 5.1 (standard reference, not scraped)