TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 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 \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]

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]

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

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

Matija Bucić, Tung Nguyen, Alex Scott, and Paul Seymour, Induced subgraph density. I. A loglog step towards Erdős-Hajnal, Theorem 1.3 (standard reference, not scraped)

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