TheoremStatement: 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.

Leaf-reducible wonderful generalized nice finite families have the Erdős-Hajnal property

Statement

Let $F$ be a generalized nice, leaf-reducible, wonderful finite family. Then $F$ has the Erdős-Hajnal property.

Facts & Assumptions

Given: A generalized nice, leaf-reducible, wonderful finite family $F$ .

[L1]

There exist constants $c_{1} \geq 1$ and $c_{2} > 0$ such that every $\overline{F}$ -free graph satisfies the three-outcome lemma from Rödl initialization upgrades generalized niceness to a restricted set, a complete or anticomplete blockade, or a polynomial clique or stable set.

[L2]

For those constants, every induced subgraph $F$ of an $\overline{F}$ -free graph $G$ with $∣ F ∣ \geq ϵ^{2 c_{1}} ∣ G ∣$ has a complete or anticomplete $(k, ∣ F ∣ / k^{c_{1}})$ -blockade for some $k \in [2, ϵ^{- 1}]$ whenever $G$ has no clique or stable set of size $∣ G ∣^{c}$ , where $c : = \min {(42 c_{1}^{2})^{- 1}, c_{2} / 2} .$ (Large induced subgraphs without a polynomial clique or stable set force complete or anticomplete blockades)

[L3]

If every induced subgraph $F$ of $G$ with $∣ F ∣ \geq ϵ^{2 a} ∣ G ∣$ has a complete or anticomplete $(k, ∣ F ∣ / k^{a})$ -blockade for some $k \in [2, ϵ^{- 1}]$ , then $G$ has an $ϵ$ -restricted induced subgraph with at least $ϵ^{3 a} ∣ G ∣$ vertices (Complete or anticomplete blockade hypotheses force an $ϵ$ -restricted induced subgraph).

[L4]

A nonempty $ϵ$ -sparse graph $H$ satisfies $χ (H) \leq ϵ ∣ H ∣ + 1, ∣ H ∣ \leq χ (H) α (H),$ and the same statement with cliques instead of stable sets holds after taking complements (The greedy colouring bound $χ (G) \leq Δ (G) + 1$ for every nonnull finite graph, The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ , 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)$ ).

[L5]

If the complement class of a hereditary family has the Erdős-Hajnal property, then so does the family itself (A hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants, The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

Proof

technique · prove an Erdős-Hajnal exponent for the $\overline{\mathcal F}$-free class and then use complement invariance

1.1L1choosegiven

Let $c_{1} \geq 1$ and $c_{2} > 0$ be the constants from [L1], put $q : = 42 c_{1}^{2}, m : = 2^{q}, c : = \min {q^{- 1}, c_{2} / 2},$ and fix a nonempty $\overline{F}$ -free graph $G$ . We will prove that $G$ has a clique or stable set of size at least $∣ G ∣^{c}$ .

2.1step 1.1assume-contraalgebra

If $G$ already has such a clique or stable set, there is nothing to prove. So assume for contradiction that $G$ has no clique or stable set of size $∣ G ∣^{c}$ . Because $c \leq q^{- 1}$ , one has $m^{c} = (2^{q})^{c} \leq 2$ . Hence every nonempty graph with at most $m$ vertices already has a clique or stable set of size at least $∣ G ∣^{c}$ , so this forces $∣ G ∣ > m$ .

3.1step 2.1algebra

Define $x : = ∣ G ∣^{- 1 / (3 c_{1})}, ϵ : = x^{1 / (7 c_{1})} .$ Then $x \leq m^{- 1 / (3 c_{1})} = 2^{- 14 c_{1}}, ϵ \leq 2^{- 14 c_{1} / (7 c_{1})} = \frac{1}{4},$ so in particular $x < ϵ \leq \frac{1}{4}$ .

4.1step 2.1step 3.1L2L3

By [L2], 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 $k \in [2, ϵ^{- 1}]$ . Therefore [L3] applies with $a : = c_{1}$ and gives an $ϵ$ -restricted induced subgraph $S \subseteq G$ with $∣ S ∣ \geq ϵ^{3 c_{1}} ∣ G ∣$ .

5.1step 3.1step 4.1L4algebra

Since $ϵ = x^{1 / (7 c_{1})} = ∣ G ∣^{- 1 / (21 c_{1}^{2})}$ and $c_{1} \geq 1$ , one has $∣ S ∣ \geq ϵ^{3 c_{1}} ∣ G ∣ = ϵ^{- 21 c_{1}^{2} + 3 c_{1}} \geq ϵ^{- 1} .$ After taking complements if necessary, [L4] lets us assume that $S$ is $ϵ$ -sparse.

6.1step 5.1L4algebra

Applying [L4] to the graph $G [S]$ yields $α (G [S]) \geq \frac{∣ S ∣}{ϵ ∣ S ∣ + 1} = \frac{1}{ϵ + ∣ S ∣^{- 1}} \geq \frac{1}{2 ϵ} \geq ϵ^{- 1 / 2} = ∣ G ∣^{1 / (42 c_{1}^{2})} \geq ∣ G ∣^{c},$ because $c \leq (42 c_{1}^{2})^{- 1}$ . This contradicts step 2.1.

7.1step 1.1step 6.1L5discharge-contradiction∎

Therefore every nonempty $\overline{F}$ -free graph has a clique or stable set of size at least $∣ G ∣^{c}$ , so the complement class of $F$ has the Erdős-Hajnal property. By [L5], $F$ itself has the Erdős-Hajnal property.

Depends on

Used by

Dependency tree · two levels

41 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, Lemma 3.5 and Lemma 1.12 (standard reference, not scraped)
Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. VII. The five-vertex path, Theorem 7.4 (standard reference, not scraped)