TheoremStatement: Literature-sourcedProof: AI-adaptedverified 2026-09-26 (gpt-6-sol)

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.

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

Depends on

Used by

Dependency tree · two levels

36 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, The Erdős-Hajnal Conjecture: A Survey, sec. 1 (standard reference, not scraped)
Matija Bucić, Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. I. A loglog step towards Erdős-Hajnal, Theorem 1.2 (standard reference, not scraped)

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