TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-28

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 Erdos-Hajnal property is equivalent to the large-cograph, large-perfect, and kappa formulations

Statement

Let $H$ be a finite family of finite graphs. The following are equivalent.

$H$ has the Erdos-Hajnal property.
There exists $τ > 0$ such that every nonempty $H$ -free graph contains an induced cograph with at least $∣ V (G) ∣^{τ}$ vertices.
There exists $τ > 0$ such that every nonempty $H$ -free graph contains an induced perfect graph with at least $∣ V (G) ∣^{τ}$ vertices.
There exists $τ > 0$ such that every nonempty $H$ -free graph satisfies $κ (G) \geq ∣ V (G) ∣^{τ}$ .

Facts & Assumptions

Given: A finite family $H$ of finite graphs.

[L1]

Clause 1 means exactly that some $τ > 0$ makes every nonempty $H$ -free graph $G$ satisfy $hom (G) \geq ∣ V (G) ∣^{τ}$ (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)}$ , $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L2]

Every cograph is perfect (Every cograph is perfect).

[L3]

Every perfect graph $J$ has a clique or stable set of size at least $∣ V (J) ∣^{1 / 2}$ (Every perfect graph has a clique or stable set of size at least the square root of its order).

[L4]

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

[L5]

On positive reals, the map $x \mapsto x^{1 / 2}$ is increasing, because $1 / 2$ is a positive rational and the real power at exponent $1 / 2$ agrees with the rational power (Monotonicity of $r \mapsto a^{r}$ and of $a \mapsto a^{r}$ , The exponential definition of real powers agrees with the existing rational powers).

[F1]

If $S \subseteq V (G)$ is homogeneous, then $G [S]$ is a cograph: when $S$ is a clique, build $G [S]$ by repeatedly taking complete connections of singletons; when $S$ is a stable set, build it by repeatedly taking disjoint unions of singletons (Cographs by the singleton, disjoint-union, and complete-connection recursion, Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ , Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F2]

If $J$ is an induced subgraph of $G$ , then every clique or stable set in $J$ is also a clique or stable set in $G$ (Subgraphs, induced subgraphs and spanning subgraphs, Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

[F3]

For every nonempty graph $G$ , $hom (G) \leq κ (G) \leq hom (G)^{2}$ because $α (G), ω (G) \geq 1$ and both are at most $hom (G)$ (The parameter kappa(G)=alpha(G)omega(G), Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ , Cliques, stable sets, the clique number $ω (G)$ and stability number $α (G)$ ).

Proof

technique · direct equivalence cycle with exponent rescaling

1.1L1F1choose

Assume clause 1. By [L1], choose $τ > 0$ such that every nonempty $H$ -free graph $G$ satisfies $hom (G) \geq ∣ V (G) ∣^{τ}$ . For such a graph, choose a homogeneous set $S$ with $∣ S ∣ = hom (G)$ . Then [F1] shows that $G [S]$ is a cograph on at least $∣ V (G) ∣^{τ}$ vertices. Hence clause 2 holds with the same exponent $τ$ .

1.2L2

Assume clause 2 with exponent $τ > 0$ . Every cograph is perfect by [L2], so the same induced subgraph witnesses clause 3 with the same exponent.

1.3L3L4L5F2choose

Assume clause 3 with exponent $τ > 0$ , and let $G$ be a nonempty $H$ -free graph. Choose an induced perfect subgraph $J$ of $G$ with $∣ V (J) ∣ \geq ∣ V (G) ∣^{τ}$ . By [L3], the graph $J$ has a clique or stable set of size at least $∣ V (J) ∣^{1 / 2}$ . Since $∣ V (J) ∣ \geq ∣ V (G) ∣^{τ} > 0$ , [L5] gives $∣ V (J) ∣^{1 / 2} \geq (∣ V (G) ∣^{τ})^{1 / 2} = ∣ V (G) ∣^{τ / 2}$ , where the equality is [L4]. Then [F2] turns that clique or stable set into one in $G$ . Therefore clause 1 holds, with exponent $τ / 2$ .

1.4L1F3L4L5

For a nonempty graph $G$ , [F3] gives $hom (G) \leq κ (G) \leq hom (G)^{2}$ . Therefore clause 1 implies clause 4 with the same exponent. Conversely, if clause 4 holds with exponent $τ$ , then $hom (G)^{2} \geq κ (G) \geq ∣ V (G) ∣^{τ} > 0$ , so [L5] gives $hom (G) \geq (∣ V (G) ∣^{τ})^{1 / 2} = ∣ V (G) ∣^{τ / 2}$ . Hence clause 4 implies clause 1.

2.1step 1.1step 1.2step 1.3

The implications in steps 1.1, 1.2, and 1.3 prove $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 1$ .

3.1step 2.1step 1.4∎

Step 2.1 gives the forward implication chain from clause 1 to clause 3 and back, while step 1.4 proves the equivalence of clauses 1 and 4. Therefore all four formulations are equivalent.

Depends on

Used by

Dependency tree · two levels

43 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

Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdos-Hajnal for graphs with no 5-hole, Introduction (standard reference, not scraped)