PropositionStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-16

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 hereditary class has the Erdős–Hajnal property exactly when its complementary class does, with the same constants

Statement

Let $C$ be a hereditary graph class and let $\overline{C}$ be its complement class. Then $C$ has the Erdős–Hajnal property if and only if $\overline{C}$ does. More precisely, the two classes have exactly the same Erdős–Hajnal constants. Consequently a graph $H$ and its complement $\overline{H}$ have the same Erdős–Hajnal constants.

Facts & Assumptions

Given: A hereditary graph class $C$ .

[L1]

An exponent $ϵ > 0$ is an Erdős–Hajnal constant for a hereditary class when every nonempty member $G$ satisfies $hom (G) \geq ∣ V (G) ∣^{ϵ}$ (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).

[L2]

The complement class is $\overline{C} = {G : \overline{G} \in C}$ (The complement of a graph class).

[L3]

If $C$ is hereditary, then $\overline{C}$ is hereditary (Complementation preserves hereditary classes and complements their minimal forbidden bases).

[L4]

Complementation exchanges cliques and stable sets, so $ω (\overline{G}) = α (G)$ and $α (\overline{G}) = ω (G)$ (Complementation swaps cliques with stable sets, so $ω (\overline{G}) = α (G)$ ).

[L5]

A graph $G$ is $H$ -free if and only if $\overline{G}$ is $\overline{H}$ -free ( $G$ is $H$ -free if and only if $\overline{G}$ is $\overline{H}$ -free).

Proof

technique · direct

1.1L3L4

By [L3], both classes in the statement are hereditary, and [L4] gives $hom (\overline{G}) = hom (G)$ for every $G$ .

2.1step 1.1L1L2

Let $ϵ$ be a constant for $C$ and let $F \in \overline{C}$ be nonempty. Then $\overline{F} \in C$ by [L2], while $∣ V (\overline{F}) ∣ = ∣ V (F) ∣$ and $hom (\overline{F}) = hom (F)$ by step 1.1, so [L1] gives $hom (F) \geq ∣ V (F) ∣^{ϵ}$ .

3.1step 2.1L2

Thus every constant of $C$ is a constant of $\overline{C}$ ; applying the same argument to $\overline{C}$ and using $\overline{\overline{G}} = G$ gives the reverse inclusion of constant sets.

4.1step 3.1L5∎

By [L5], complementation bijects the $H$ -free class with the $\overline{H}$ -free class, so step 3.1 gives the fixed-pattern consequence.

Depends on

Used by

Dependency tree · two levels

14 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

Erdos-Hajnal properties in graphs and hypergraphs, introduction (standard reference, not scraped)