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.

✓ 3 results · all verified · 2 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 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

From Generalized Niceness to Erdős-Hajnal — Examples

1 · Prerequisites

2 · Summary

These examples isolate the two concrete mechanisms used on the A page: the parameter choices in the final Erdős-Hajnal deduction, and the two ways a large restricted or blocked configuration immediately produces a polynomial clique or stable set.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

The Lemma 3.5 parameter choice at the next power of two above the source threshold

Example

Consider the special case in which the constant supplied by the source lemma happens to be $c_{1} = 1$ . Then $q = 42$ and the threshold is $m = 2^{42}$ . Let $∣ G ∣ : = 2^{43}$ , and define

x : = ∣ G ∣^{- 1 / 3} = 2^{- 43 / 3}, ϵ : = x^{1 / 7} = 2^{- 43 / 21} .

Then the size thresholds in the source Erdős-Hajnal reduction are

∣ F ∣_{\min} : = ϵ^{2} ∣ G ∣, ∣ S ∣_{\min} : = ϵ^{3} ∣ G ∣ .

Facts & Assumptions

Given: The numerical choices displayed in the Example.

[A1]

Conditionally on the displayed value $c_{1} = 1$ , one has $∣ G ∣ = 2^{43} > 2^{42} = m$ , and $2^{43}$ is the first power of two strictly above the corresponding source threshold. The example does not assert that the existential constant $c_{1}$ can be freely chosen.

Verification

technique · direct arithmetic

1.1

Since $x = 2^{- 43 / 3}$ , one has $ϵ = x^{1 / 7} = 2^{- 43 / 21} > 2^{- 43 / 3} = x .$ Also $ϵ = 2^{- 43 / 21} < 2^{- 2} = \frac{1}{4},$ because $43 / 21 > 2$ . Thus $x < ϵ \leq \frac{1}{4}$ .

A1algebra

2.1

The first threshold is $∣ F ∣_{\min} = ϵ^{2} ∣ G ∣ = 2^{- 86 / 21} \cdot 2^{43} = 2^{817 / 21},$ while $ϵ^{- 1} = 2^{43 / 21} .$ Since $817 / 21 > 43 / 21$ , one gets $∣ F ∣_{\min} > ϵ^{- 1}$ .

step 1.1algebra

2.2

The second threshold is $∣ S ∣_{\min} = ϵ^{3} ∣ G ∣ = 2^{- 129 / 21} \cdot 2^{43} = 2^{774 / 21} .$ Again $774 / 21 > 43 / 21$ , so $∣ S ∣_{\min} > ϵ^{- 1}$ .

step 1.1algebra

3.1

Therefore, in the special case $c_{1} = 1$ , this concrete instance satisfies all of the numerical inequalities used in the source Erdős-Hajnal reduction at the next power-of-two graph order above the threshold.

step 2.1step 2.2∎

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

A complete four-blockade gives a four-vertex clique

Example

Let $B = (B_{1}, B_{2}, B_{3}, B_{4})$ be a complete four-blockade in a graph $G$ , and choose vertices $v_{i} \in B_{i}$ for $i = 1, 2, 3, 4$ .

Facts & Assumptions

Given: The complete blockade $B$ and the chosen vertices $v_{i} \in B_{i}$ .

[L1]

Distinct blocks of a complete blockade are pairwise complete (Complete, anticomplete, pure, weakly sparse, and $x$ -sparse blockades).

Verification

technique · direct

1.1

Because each block of a blockade is nonempty, the four choices $v_{i} \in B_{i}$ are legitimate.

givenchoose

2.1

If $i \neq j$ , then $B_{i}$ is complete to $B_{j}$ by [L1], so the chosen vertices $v_{i}$ and $v_{j}$ are adjacent.

step 1.1L1

3.1

Therefore every pair among $v_{1}, v_{2}, v_{3}, v_{4}$ is adjacent, so these four vertices form a clique.

step 2.1∎

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

A large epsilon-restricted induced subgraph gives a polynomial clique or stable set

Example

Let $ϵ : = \frac{1}{4}$ and let $S$ be an $ϵ$ -restricted induced subgraph on $16$ vertices. Take an ambient graph order $∣ G ∣ : = 2^{84}$ , so that $∣ G ∣^{1 / 42} = 4$ .

Facts & Assumptions

Given: The data in the Example.

[L1]

An $ϵ$ -restricted set is $ϵ$ -sparse in one of $G$ and $\overline{G}$ , and complementation swaps cliques with stable sets ( $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)$ ).

[L2]

For a nonempty $ϵ$ -sparse graph $H$ ,

χ (H) \leq ϵ ∣ H ∣ + 1, ∣ H ∣ \leq χ (H) α (H)

(The greedy colouring bound $χ (G) \leq Δ (G) + 1$ for every nonnull finite graph, The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ ).

Verification

technique · direct

1.1

By [L1], after taking complements if necessary we may assume that $S$ is $ϵ$ -sparse.

2.1

Applying [L2] to the $16$ -vertex graph $G [S]$ gives $α (G [S]) \geq \frac{16}{ϵ \cdot 16 + 1} = \frac{16}{5} > 3.$ Since $α (G [S])$ is an integer, $α (G [S]) \geq 4$ .

step 1.1L2algebra

3.1

Because $∣ G ∣ = 2^{84}$ , one has $∣ G ∣^{1 / 42} = 2^{2} = 4$ . Therefore the stable set from step 2.1 already has the same size as the final polynomial bound used in the A-page reduction. If the sparse side had arisen in the complement instead, [L1] would turn the same calculation into a clique of size $4$ in the original graph.

step 2.1L1algebra∎

From Generalized Niceness to Erdős-Hajnal — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The Lemma 3.5 parameter choice at the next power of two above the source threshold

Example

Facts & Assumptions

Verification

A complete four-blockade gives a four-vertex clique

Example

Facts & Assumptions

Verification

A large epsilon-restricted induced subgraph gives a polynomial clique or stable set

Example

Facts & Assumptions

Verification

Sources