CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (gpt-5.6-terra)audited 2026-08-26

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.

The polynomial Rödl property implies the Erdős–Hajnal property

Statement

Every finite family of graphs with the polynomial Rödl property has the Erdős–Hajnal property. More precisely, if $d \geq 1$ witnesses the polynomial Rödl property of $F$ , then

\frac{1}{2 d + 2}

is an Erdős–Hajnal constant for the class of $F$ -free graphs.

Facts & Assumptions

Given: A finite family $F$ of graphs and an exponent $d \geq 1$ witnessing its polynomial Rödl property.

[L1]

For every $ϵ \in (0, \frac{1}{2})$ and every nonempty $F$ -free graph $G$ , there is an $ϵ$ -restricted vertex set $X \subseteq V (G)$ with $∣ X ∣ \geq ϵ^{d} ∣ V (G) ∣$ (The polynomial Rödl property for a finite forbidden family, $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L2]

An exponent $c > 0$ is an Erdős–Hajnal constant exactly when every nonempty $F$ -free graph $G$ satisfies $hom (G) \geq ∣ V (G) ∣^{c}$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class, Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[L3]

If $X$ is $ϵ$ -sparse, then every vertex of $G [X]$ has degree at most $ϵ ∣ X ∣$ (A set is $c$ -sparse exactly when the maximum degree of the graph it induces is at most $c$ times its size).

[L4]

A nonnull graph satisfies $χ (H) \leq Δ (H) + 1$ , and every graph satisfies $∣ V (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)$ ).

[L5]

A set is $ϵ$ -dense in $G$ exactly when it is $ϵ$ -sparse in $\overline{G}$ , and stable sets in $\overline{G}$ are cliques in $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)$ ).

[L6]

For positive bases, $a^{r + s} = a^{r} a^{s}$ (The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).

Proof

technique · direct

1.1

Put $c : = 1 / (2 d + 2)$ , and let $G$ be a nonempty $F$ -free graph on $n$ vertices. We show that $hom (G) \geq n^{c}$ .

2.1

If $n = 1$ , then $hom (G) = 1 = n^{c}$ . If $2 \leq n < 2^{1 / c}$ , then any two vertices of $G$ are adjacent or nonadjacent, so $hom (G) \geq 2 > n^{c}$ . It therefore remains only to treat the case $n \geq 2^{1 / c} = 2^{2 d + 2}$ .

step 1.1L2algebra

2.2

Assume now that $n \geq 2^{2 d + 2}$ and set $ϵ : = n^{- 1 / (d + 1)} = n^{- 2 c}$ . Then $ϵ \in (0, \frac{1}{2})$ . By [L1], choose an $ϵ$ -restricted vertex set $X \subseteq V (G)$ with $∣ X ∣ \geq ϵ^{d} n = n^{1 - d / (d + 1)} = n^{1 / (d + 1)} = n^{2 c}$ .

step 1.1L1L6choose

3.1

Suppose first that $X$ is $ϵ$ -sparse. By [L3], the induced graph $G [X]$ has maximum degree at most $ϵ ∣ X ∣$ , so [L4] gives $χ (G [X]) \leq ϵ ∣ X ∣ + 1 \leq 2 ϵ ∣ X ∣$ because $ϵ ∣ X ∣ \geq ϵ n^{2 c} = 1$ . Applying the second inequality of [L4] to $G [X]$ yields $∣ X ∣ \leq χ (G [X]) α (G [X]) \leq 2 ϵ ∣ X ∣ α (G [X])$ , so $α (G [X]) \geq 1 / (2 ϵ) = n^{2 c} / 2 \geq n^{c}$ , the last inequality using $n^{c} \geq 2$ from step 2.1. Hence $hom (G) \geq n^{c}$ .

step 2.1step 2.2L3L4algebra

4.1

Suppose instead that $X$ is $ϵ$ -dense. Then [L5] makes $X$ $ϵ$ -sparse in $\overline{G}$ , so the same calculation as in step 3.1 applied to $\overline{G} [X]$ yields a stable set of size at least $n^{c}$ in $\overline{G} [X]$ . By [L5], that stable set is a clique of size at least $n^{c}$ in $G [X]$ , and again $hom (G) \geq n^{c}$ .

step 2.1step 2.2step 3.1L5

5.1

Step 2.1 handles $n < 2^{1 / c}$ , and steps 3.1 and 4.1 handle the large- $n$ case. Thus every nonempty $F$ -free graph $G$ satisfies $hom (G) \geq ∣ V (G) ∣^{c}$ , so [L2] shows that $c = 1 / (2 d + 2)$ is an Erdős–Hajnal constant.

step 2.1step 3.1step 4.1L2∎

Depends on

Used by

For a finite family, the Erdős–Hajnal property, the polynomial Rödl property, and virality are equivalent Theorem

Dependency tree · two levels

32 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

M. Bucić, J. Fox, and H. T. Pham, Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures, Theorem 4 (standard reference, not scraped)
T. H. Nguyen, Notes on Recent Work on the Erdős–Hajnal Conjecture, §1 (standard reference, not scraped)