Classical and Log-Log Erdős–Hajnal Bounds

1 · Prerequisites

2 · Summary

Homogeneous sets, sparse induced subgraphs, greedy colouring, the product bound $∣ V ∣ \leq χ α$ , complementation, and base- $2$ logarithms are the ingredients behind the quantitative Erdős–Hajnal estimates. The page uses them in one fixed order: a density theorem isolates a large induced subgraph with few edges or few nonedges, trimming turns low density into bounded degree, colouring extracts a large stable set, and the complement turns the same argument into a clique bound.

The page then records two source-cited quantitative density inputs, one on the classical $\sqrt{\log_{2} n}$ scale and one on the improved $\sqrt{\log_{2} n \log_{2} \log_{2} n}$ scale, and proves from them the corresponding homogeneous-set lower bounds for $H$ -free graphs. A final corollary compares the two exponents and shows that the log-log scale eventually dominates every fixed classical scale.

3 · Logical flowchart

4 · Definitions, theorems and proofs

RemarkRemark: AI-adaptedProof: Not supplied‡ sources checked 2026-08-26‡ not proved hereOpen item page →

‡ Recorded, not proved here. This statement is included so the library can refer to it honestly, with a citation to the literature. It is not proved anywhere in this library: the track that would prove it has not been developed here yet.

Fox–Sudakov: a quantitative density form of Rödl's theorem

Statement

For every finite graph $H$ there exists a constant $C_{H} > 0$ such that for every real $x$ with $0 < x < 1 / 2$ and every finite $H$ -free graph $G$ , there is a vertex set $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2}} ∣ V (G) ∣$ such that one of the induced graphs $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges.

Remarks

This page uses only that $H$ -free specialization and keeps the source's base-2 logarithm convention. A local proof belongs to the quantitative induced-density track rather than to this page, so the result is recorded here and cited by Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n}}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26‡ rests on unproved materialOpen item page →

‡ Rests on 1 statement not proved in this library. Every dependency marked ‡ below is recorded with a citation but is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n}}$

Statement

Let $H$ be a finite graph. Then there exists a constant $c_{H} > 0$ such that every nonnull finite $H$ -free graph $G$ with $n : = ∣ V (G) ∣ \geq 2$ satisfies $hom (G) \geq 2^{c_{H} \sqrt{\log_{2} n}} .$ Equivalently, $G$ has a clique or a stable set of size at least $2^{c_{H} \sqrt{\log_{2} n}}$ .

Facts & Assumptions

Given: A finite graph $H$ , a nonnull finite $H$ -free graph $G$ , and $n : = ∣ V (G) ∣ \geq 2$ .

[L1]

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

‡ [L2]

Fox-Sudakov quantitative density: there exists $C_{H} > 0$ such that for every real $x$ with $0 < x < 1 / 2$ there is $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2}} n$ and one of $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges (Fox–Sudakov: a quantitative density form of Rödl's theorem ‡).

[L3]

If a nonempty vertex set $X$ satisfies $d_{G} (X, X) \leq c$ , then some $X^{'} \subseteq X$ has $∣ X^{'} ∣ \geq ∣ X ∣ / 2$ and is $4 c$ -sparse (A set of self-density at most $c$ has a subset of at least half its size that is $4 c$ -sparse).

[L4]

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

[L5]

Every nonnull finite graph $F$ satisfies $χ (F) \leq Δ (F) + 1$ (The greedy colouring bound $χ (G) \leq Δ (G) + 1$ for every nonnull finite graph).

[L6]

Every finite graph $F$ satisfies $∣ V (F) ∣ \leq χ (F) α (F)$ (The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ ).

[L7]

A vertex set is a clique in $G$ if and only if it is a stable set in $\overline{G}$ (Complementation swaps cliques with stable sets, so $ω (\overline{G}) = α (G)$ ).

[L8]

For nonempty $X$ , the self-density is $d_{G} (X, X) = 2 ∣ E (G [X]) ∣ / ∣ X ∣^{2}$ (Edge counts and densities between nonempty vertex sets).

Proof

technique · direct

1.1

By [L2], choose a constant $C_{H} > 0$ . Write $L : = \log_{2} n$ and set $x : = 2^{- \sqrt{L / (2 C_{H})}}$ . Since $n \geq 2$ , one has $L > 0$ , so $0 < x < 1 / 2$ .

‡ L2choose

2.1

Because $\log_{2} (1 / x) = \sqrt{L / (2 C_{H})}$ , [L2] gives a set $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2}} n = 2^{- L / 2} n = \sqrt{n}$ , and one of $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges. For that chosen graph $F$ on vertex set $S$ , [L8] gives $d_{F} (S, S) = 2 ∣ E (F) ∣ / ∣ S ∣^{2} \leq 2 x (\binom{∣ S ∣}{2}) / ∣ S ∣^{2} = x (∣ S ∣ - 1) / ∣ S ∣ \leq x$ .

step 1.1‡ L2L8algebra

3.1

If $F = G [S]$ , then [L3] gives $X \subseteq S$ with $∣ X ∣ \geq ∣ S ∣ / 2$ and $X$ $4 x$ -sparse in $G$ . By [L4] every vertex of $G [X]$ has degree at most $4 x ∣ X ∣$ , so [L5] gives $χ (G [X]) \leq 4 x ∣ X ∣ + 1$ , and then [L6] yields $α (G [X]) \geq ∣ X ∣ / (4 x ∣ X ∣ + 1)$ .

step 2.1L3L4L5L6

3.2

If $F = \overline{G} [S]$ , then [L3] gives $X \subseteq S$ with $∣ X ∣ \geq ∣ S ∣ / 2$ and $X$ $4 x$ -sparse in $\overline{G}$ . Applying [L4], [L5], and [L6] inside the complement shows that $\overline{G} [X]$ has a stable set of size at least $∣ X ∣ / (4 x ∣ X ∣ + 1)$ , and [L7] turns that stable set into a clique of the same size in $G [X]$ .

step 2.1L3L4L5L6L7

4.1

Steps 3.1 and 3.2 show that $G$ has a homogeneous set $Y$ with $∣ Y ∣ \geq ∣ X ∣ / (4 x ∣ X ∣ + 1)$ for some $X \subseteq S$ satisfying $∣ X ∣ \geq ∣ S ∣ / 2 \geq \sqrt{n} / 2$ .

step 3.1step 3.2step 2.1L1

5.1

Because $x \sqrt{n} = 2^{L / 2 - \sqrt{L / (2 C_{H})}}$ , choose $N_{H} \geq 2$ so that $x \sqrt{n} \geq 1$ whenever $n \geq N_{H}$ . For such $n$ , step 4.1 gives $4 x ∣ X ∣ \geq 2$ , hence $4 x ∣ X ∣ + 1 \leq 8 x ∣ X ∣$ , so $∣ Y ∣ \geq 1 / (8 x) = 2^{\sqrt{L / (2 C_{H})} - 3}$ .

step 4.1step 1.1choosealgebra

6.1

Set $c_{H} : = 1 / (4 \sqrt{2 C_{H}})$ . Choose $N_{H}^{'} \geq N_{H}$ so that $\sqrt{L / (2 C_{H})} - 3 \geq c_{H} \sqrt{L}$ whenever $n \geq N_{H}^{'}$ . Then step 5.1 gives $∣ Y ∣ \geq 2^{c_{H} \sqrt{L}}$ for all $n \geq N_{H}^{'}$ . Shrinking $c_{H}$ if necessary handles the finitely many integers $2 \leq n < N_{H}^{'}$ , because every nonnull graph has $hom (G) \geq 1$ .

step 5.1L1choosealgebra

7.1

Therefore every nonnull finite $H$ -free graph $G$ with $∣ V (G) ∣ = n \geq 2$ satisfies $hom (G) \geq 2^{c_{H} \sqrt{\log_{2} n}}$ .

step 6.1L1∎

RemarkRemark: AI-adaptedProof: Not supplied‡ sources checked 2026-08-26‡ not proved hereOpen item page →

‡ Recorded, not proved here. This statement is included so the library can refer to it honestly, with a citation to the literature. It is not proved anywhere in this library: the track that would prove it has not been developed here yet.

Bucić–Nguyen–Scott–Seymour: a log-log quantitative density theorem

Statement

For every finite graph $H$ there exists a constant $C_{H} > 0$ such that for every real $x$ with $0 < x < 1 / 2$ and every finite $H$ -free graph $G$ , there is a vertex set $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)} ∣ V (G) ∣$ such that one of the induced graphs $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges.

Remarks

Again the statement is recorded exactly in the paper's base-2 convention. The page uses it only as a source-cited input for Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-26‡ rests on unproved materialOpen item page →

‡ Rests on 1 statement not proved in this library. Every dependency marked ‡ below is recorded with a citation but is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$

Statement

Let $H$ be a finite graph. Then there exists a constant $c_{H} > 0$ such that every nonnull finite $H$ -free graph $G$ with $n : = ∣ V (G) ∣ \geq 2$ satisfies $hom (G) \geq 2^{c_{H} \sqrt{\log_{2} n \log_{2} \log_{2} n}} .$

Facts & Assumptions

Given: A finite graph $H$ , a nonnull finite $H$ -free graph $G$ , and $n : = ∣ V (G) ∣ \geq 2$ .

[L1]

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

‡ [L2]

Bucić-Nguyen-Scott-Seymour quantitative density: there exists $C_{H} > 0$ such that for every real $x$ with $0 < x < 1 / 2$ there is $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)} n$ and one of $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges (Bucić–Nguyen–Scott–Seymour: a log-log quantitative density theorem ‡).

[L3]

If a nonempty vertex set $X$ satisfies $d_{G} (X, X) \leq c$ , then some $X^{'} \subseteq X$ has $∣ X^{'} ∣ \geq ∣ X ∣ / 2$ and is $4 c$ -sparse (A set of self-density at most $c$ has a subset of at least half its size that is $4 c$ -sparse).

[L4]

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

[L5]

Every nonnull finite graph $F$ satisfies $χ (F) \leq Δ (F) + 1$ (The greedy colouring bound $χ (G) \leq Δ (G) + 1$ for every nonnull finite graph).

[L6]

Every finite graph $F$ satisfies $∣ V (F) ∣ \leq χ (F) α (F)$ (The bounds $ω (G) \leq χ (G)$ and $∣ V (G) ∣ \leq χ (G) α (G)$ ).

[L7]

A vertex set is a clique in $G$ if and only if it is a stable set in $\overline{G}$ (Complementation swaps cliques with stable sets, so $ω (\overline{G}) = α (G)$ ).

[L8]

For nonempty $X$ , the self-density is $d_{G} (X, X) = 2 ∣ E (G [X]) ∣ / ∣ X ∣^{2}$ (Edge counts and densities between nonempty vertex sets).

Proof

technique · direct

1.1

By [L2], choose a constant $C_{H} > 0$ . Because every nonnull graph has $hom (G) \geq 1$ , it is enough to prove the bound for all sufficiently large $n$ ; assume from now on that $n$ is large enough that $L : = \log_{2} n \geq 4$ . Set $β : = 1 / (4 \sqrt{C_{H}})$ and $x : = 2^{- β \sqrt{L \log_{2} L}}$ . Then $0 < x < 1 / 2$ .

L1‡ L2choose

2.1

For large enough $L$ , the inequality $β \sqrt{L \log_{2} L} \geq \sqrt{L}$ holds, so $\log_{2} \log_{2} (1 / x) = \log_{2} (β \sqrt{L \log_{2} L}) \geq \frac{1}{2} \log_{2} L$ . Therefore $C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x) \leq 2 C_{H} β^{2} L = L / 8$ . Using [L2], obtain $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- L / 8} n = 2^{7 L / 8} \geq \sqrt{n}$ , and one of $G [S]$ and $\overline{G} [S]$ has at most $x (\binom{∣ S ∣}{2})$ edges. For that chosen graph $F$ on vertex set $S$ , [L8] gives $d_{F} (S, S) \leq 2 x (\binom{∣ S ∣}{2}) / ∣ S ∣^{2} = x (∣ S ∣ - 1) / ∣ S ∣ \leq x$ .

step 1.1‡ L2L8algebra

3.1

If $F = G [S]$ , then [L3] gives $X \subseteq S$ with $∣ X ∣ \geq ∣ S ∣ / 2$ and $X$ $4 x$ -sparse in $G$ . By [L4], [L5], and [L6], $α (G [X]) \geq ∣ X ∣ / (4 x ∣ X ∣ + 1)$ .

step 2.1L3L4L5L6

3.2

If $F = \overline{G} [S]$ , then the same argument inside the complement produces a stable set of $\overline{G} [X]$ of size at least $∣ X ∣ / (4 x ∣ X ∣ + 1)$ for some $X \subseteq S$ with $∣ X ∣ \geq ∣ S ∣ / 2$ , and [L7] turns it into a clique of $G [X]$ .

step 2.1L3L4L5L6L7

4.1

Steps 3.1 and 3.2 show that $G$ has a homogeneous set $Y$ with $∣ Y ∣ \geq ∣ X ∣ / (4 x ∣ X ∣ + 1)$ for some $X \subseteq S$ satisfying $∣ X ∣ \geq ∣ S ∣ / 2 \geq \sqrt{n} / 2$ .

step 3.1step 3.2step 2.1L1

5.1

Because $x \sqrt{n} = 2^{L / 2 - β \sqrt{L \log_{2} L}}$ , choose a threshold $N_{H} \geq 2$ so that $x \sqrt{n} \geq 1$ whenever $n \geq N_{H}$ . For those $n$ , step 4.1 gives $4 x ∣ X ∣ \geq 2$ , hence $4 x ∣ X ∣ + 1 \leq 8 x ∣ X ∣$ , and therefore $∣ Y ∣ \geq 1 / (8 x) = 2^{β \sqrt{L \log_{2} L} - 3}$ .

step 4.1step 1.1choosealgebra

6.1

Set $c_{H} : = β / 2$ . For all sufficiently large $n$ , the inequality $β \sqrt{L \log_{2} L} - 3 \geq c_{H} \sqrt{L \log_{2} L}$ holds, so step 5.1 gives $∣ Y ∣ \geq 2^{c_{H} \sqrt{L \log_{2} L}}$ . Shrinking $c_{H}$ if necessary handles the finitely many smaller values of $n$ .

step 5.1choosealgebra

7.1

Hence every nonnull finite $H$ -free graph $G$ with $∣ V (G) ∣ = n \geq 2$ satisfies $hom (G) \geq 2^{c_{H} \sqrt{\log_{2} n \log_{2} \log_{2} n}}$ .

step 6.1L1∎

CorollaryStatement: AI-generatedProof: AI-generatedprecheck passaudited 2026-08-26‡ rests on unproved material (inherited)Open item page →

‡ Rests on 2 statements not proved in this library, by way of the results it cites. This item cites no such statement directly; it depends on results that do. The unproved premises it inherits are ‡ Fox–Sudakov: a quantitative density form of Rödl's theorem and ‡ Bucić–Nguyen–Scott–Seymour: a log-log quantitative density theorem. Each is recorded with a citation to the literature and is not established here, because the track that would prove it has not yet been developed in this library. Everything else in this proof is proved here.

For fixed $H$ , the log-log scale eventually exceeds every classical scale $2^{c \sqrt{\log_{2} n}}$

Statement

Let $a, b > 0$ . Then there exists $N \geq 2$ such that for every integer $n \geq N$ , $2^{b \sqrt{\log_{2} n \log_{2} \log_{2} n}} \geq 2^{a \sqrt{\log_{2} n}} .$ In particular, for each fixed finite graph $H$ , the log-log lower bound of Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$ eventually exceeds every classical scale $2^{a \sqrt{\log_{2} n}}$ .

Facts & Assumptions

Given: Positive reals $a, b$ .

[L1]

For $n > 1$ , $\log_{2} n$ is defined (The logarithm to a positive base other than one).

Proof

technique · direct

1.1

For every integer $n > 2$ , one has $\sqrt{\log_{2} n \log_{2} \log_{2} n} = \sqrt{\log_{2} \log_{2} n} \sqrt{\log_{2} n}$ .

L1algebra

2.1

Choose $N \geq 4$ so that $b \sqrt{\log_{2} \log_{2} n} \geq a$ whenever $n \geq N$ . This is possible because $\log_{2} \log_{2} n$ tends to $+ \infty$ with $n$ .

step 1.1choose

3.1

For every $n \geq N$ , step 2.1 gives $b \sqrt{\log_{2} n \log_{2} \log_{2} n} \geq a \sqrt{\log_{2} n}$ , and exponentiating base $2$ preserves the inequality.

step 1.1step 2.1algebra

4.1

This proves the displayed eventual inequality, and the final sentence is its application with the constant supplied by Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$ .

step 3.1∎

5 · Examples, counterexamples and false statements

None yet.

Classical and Log-Log Erdős–Hajnal Bounds

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Fox–Sudakov: a quantitative density form of Rödl's theorem

Statement

Remarks

Every HH-free graph has a homogeneous set of size at least 2clog⁡2n2clog2​n​

Statement

Facts & Assumptions

Proof

Bucić–Nguyen–Scott–Seymour: a log-log quantitative density theorem

Statement

Remarks

Every HH-free graph has a homogeneous set of size at least 2clog⁡2n log⁡2log⁡2n2clog2​nlog2​log2​n​

Statement

Facts & Assumptions

Proof

For fixed HH, the log-log scale eventually exceeds every classical scale 2clog⁡2n2clog2​n​

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources

Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n}}$

Every $H$ -free graph has a homogeneous set of size at least $2^{c \sqrt{\log_{2} n \log_{2} \log_{2} n}}$

For fixed $H$ , the log-log scale eventually exceeds every classical scale $2^{c \sqrt{\log_{2} n}}$