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

For every $t \geq 1$ , the class of $K_{t}$ -free graphs has the Erdős–Hajnal property

Statement

For every positive integer $t$ , the hereditary class of $K_{t}$ -free finite graphs has the Erdős–Hajnal property.

Facts & Assumptions

Given: A positive integer $t$ and the class $C_{t}$ of $K_{t}$ -free finite graphs.

[L1]

For a graph $G$ , $hom (G) = \max {ω (G), α (G)}$ (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[L2]

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

[L3]

A graph is $K_{t}$ -free when it has no induced copy of $K_{t}$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention), and the class of graphs free of any fixed family is hereditary (Every class defined by forbidden induced subgraphs is hereditary).

[L4]

The graph $K_{t}$ has every pair of its $t$ vertices as an edge, while an empty graph has no edges (Empty and complete graphs, complete bipartite graphs, and the convention that $P_{n}$ and $C_{n}$ have $n$ vertices).

[L5]

For positive $a, b$ , every graph on at least $(\binom{a + b - 2}{a - 1})$ vertices contains an $a$ -clique or a $b$ -vertex stable set (Finite graph Ramsey theorem: $(\binom{s + t - 2}{s - 1}) \to (s, t)^{2}$ for all positive $s, t$ ).

[L6]

The binomial coefficient $(\binom{m}{r})$ counts the $r$ -subsets of an $m$ -set (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L7]

For $x > 0$ and real $u$ , $x^{u} = \exp (u \log x)$ (Real powers for positive bases, with the zero-base positive-exponent convention).

[L8]

The logarithm is strictly increasing, maps $1$ to $0$ , and obeys the product and quotient laws (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[L9]

The exponential is strictly increasing (The exponential function is strictly increasing).

Proof

technique · direct

1.1L1L2L3L4

By [L3], $C_{t}$ is hereditary. If $t = 1$ , it has no nonempty member, so any positive exponent works in [L2]; if $t = 2$ , every member is empty by [L3] and [L4], so $hom (G) = ∣ V (G) ∣$ and exponent $1$ works.

1.2givenL7L8L9algebra

Assume $t \geq 3$ . For all sufficiently large integers $n$ , the integer $s = ⌊ \frac{1}{2} n^{1 / (t - 1)} ⌋$ satisfies $s \geq t - 2$ , $s \geq n^{1 / t}$ , and $s \geq 1$ ; these assertions follow from [L7], [L8], and [L9] because $n^{1 / (t - 1)} / n^{1 / t} = n^{1 / (t (t - 1))}$ tends to infinity.

2.1step 1.2L6algebra

For such $n$ , $t + s - 2 \leq 2 s$ , and hence $(\binom{t + s - 2}{t - 1}) \leq (t + s - 2)^{t - 1} \leq (2 s)^{t - 1} \leq n$ ; the first inequality counts ordered choices containing every $(t - 1)$ -subset.

3.1step 1.2step 2.1L1L3L5

If $G \in C_{t}$ has sufficiently large order $n$ , [L5] with parameters $(t, s)$ and step 2.1 give a $t$ -clique or an $s$ -vertex stable set; the first is forbidden, so $hom (G) \geq α (G) \geq s \geq n^{1 / t}$ .

4.1step 3.1L7L8L9choose

Choose an integer threshold $N \geq 2$ beyond which step 3.1 applies, and choose $0 < ϵ \leq 1 / t$ so small that $N^{ϵ} \leq 2$ . Such an $ϵ$ exists by [L7], [L8], and [L9].

5.1step 3.1step 4.1L1L2L4algebra∎

If $G \in C_{t}$ has $n \geq N$ , then $hom (G) \geq n^{1 / t} \geq n^{ϵ}$ ; if $2 \leq n < N$ , an edge gives a two-vertex clique and a nonedge gives a two-vertex stable set, so $hom (G) \geq 2 \geq n^{ϵ}$ ; and if $n = 1$ , both sides equal $1$ . Thus $ϵ$ is an Erdős–Hajnal constant for $C_{t}$ .

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

M. Chudnovsky, The Erdos-Hajnal Conjecture: A Survey, sec. 2 (standard reference, not scraped)

For every t≥1t≥1, the class of KtKt​-free graphs has the Erdős–Hajnal property