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.

✓ 2 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full by a delegated reviewing agent on the owner's instruction; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

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 two density bounds proved earlier on quantitative-induced-density-and-the-loglog-step supply the classical $\sqrt{\log_{2} n}$ and improved $\sqrt{\log_{2} n \log_{2} \log_{2} n}$ scales. This page derives 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

TheoremStatement: Literature-sourcedProof: AI-adaptedverified 2026-09-26 (gpt-6-sol)Open item page →

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]

For nonempty $H$ , the proved quantitative induced-density corollary supplies $C_{H} > 0$ such that every $H$ -free $G$ and every $0 < x < 1 / 2$ have a nonempty $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2}} n$ and at most $x (\binom{∣ S ∣}{2})$ edges in $G [S]$ or $\overline{G} [S]$ (Fox sudakov quantitative induced density bound).

[L9]

A graph is $H$ -free if it has no induced copy of $H$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[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.1L2L9choose

If $H$ is null, every graph has the empty induced copy, so no graph in the stated range is $H$ -free and the assertion is vacuous. Hence assume $H$ is nonempty. By [L2], choose $C_{H} > 0$ . Write $L : = \log_{2} n$ and set $x : = 2^{- \sqrt{L / (2 C_{H})}}$ . Choose $N_{0}$ so large that $L > 2 C_{H}$ whenever $n \geq N_{0}$ . For these $n$ one has $0 < x < 1 / 2$ , as required to apply [L2]. The finitely many smaller $n$ are handled after the large- $n$ argument.

2.1step 1.1L2L8algebra

For $n \geq N_{0}$ , 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$ .

3.1step 2.1L3L4L5L6

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)$ .

3.2step 2.1L3L4L5L6L7

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]$ .

4.1step 3.1step 3.2step 2.1L1

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$ .

5.1step 4.1step 1.1choosealgebra

Because $x \sqrt{n} = 2^{L / 2 - \sqrt{L / (2 C_{H})}}$ , choose $N_{H} \geq N_{0}$ 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}$ .

6.1step 5.1L1choosealgebra

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}^{'}$ . For the finitely many integers $2 \leq n < N_{H}^{'}$ , every graph on at least two vertices has either an adjacent pair or a nonadjacent pair, so $hom (G) \geq 2$ . Shrink $c_{H} > 0$ if necessary so that $2^{c_{H} \sqrt{\log_{2} n}} \leq 2$ for each of these $n$ .

7.1step 6.1L1∎

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}}$ .

TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-09-26 (gpt-6-sol)Open item page →

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

Statement

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]

For nonempty $H$ , the proved quantitative induced-density theorem supplies $C_{H} > 0$ such that every $H$ -free $G$ and every $0 < x < 1 / 2$ have a nonempty $S \subseteq V (G)$ with $∣ S ∣ \geq 2^{- C_{H} (\log_{2} (1 / x))^{2} / \log_{2} \log_{2} (1 / x)} n$ and at most $x (\binom{∣ S ∣}{2})$ edges in $G [S]$ or $\overline{G} [S]$ (Loglog quantitative induced density bound).

[L9]

A graph is $H$ -free if it has no induced copy of $H$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L3]

[L4]

[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.1L1L2L9choose

If $H$ is null, every graph has the empty induced copy, so the stated $H$ -free case is vacuous. Hence assume $H$ nonempty and choose $C_{H} > 0$ from [L2]. Every graph on at least two vertices has an adjacent or nonadjacent pair, so $hom (G) \geq 2$ ; this handles finitely many small $n$ after shrinking the final positive constant (and the target is $1$ at $n = 2$ ). For the large- $n$ argument assume $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$ once $n$ is sufficiently large.

2.1step 1.1L2L8algebra

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$ .

3.1step 2.1L3L4L5L6

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)$ .

3.2step 2.1L3L4L5L6L7

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]$ .

4.1step 3.1step 3.2step 2.1L1

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$ .

5.1step 4.1step 1.1choosealgebra

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}$ .

6.1step 1.1step 5.1L1choosealgebra

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}}$ . For each of the finitely many smaller integers $n \geq 3$ , the pair argument of step 1.1 gives $hom (G) \geq 2$ ; shrink $c_{H} > 0$ so that $2^{c_{H} \sqrt{\log_{2} n \log_{2} \log_{2} n}} \leq 2$ for all of them. At $n = 2$ the displayed target is $1$ .

7.1step 6.1L1∎

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}}$ .

CorollaryStatement: AI-generatedProof: AI-generatedprecheck passaudited 2026-08-26Open item page →

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.1L1algebra

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}$ .

2.1step 1.1choose

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$ .

3.1step 1.1step 2.1algebra

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.

4.1step 3.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}}$ .

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

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

Statement

Facts & Assumptions

Proof

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}}$