TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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 $n \geq 16$ there is an $n$ -vertex graph with $hom (G) < 3 \log_{2} n$

Statement

For every integer $n \geq 16$ , there exists an $n$ -vertex graph $G$ such that $hom (G) < 3 \log_{2} n .$

Facts & Assumptions

Given: An integer $n \geq 16$ and $k = ⌈ 3 \log_{2} n ⌉$ .

[L1]

The homogeneous number of a graph is the larger of its clique and stable-set numbers (Homogeneous vertex sets and the homogeneous number $hom (G) = \max {ω (G), α (G)}$ ).

[L2]

In $G (n, 1 / 2)$ , all possible edges are independent Bernoulli variables on the labelled vertex set $[n]$ (The Erdős-Rényi finite random graph $G (n, p)$ ).

[L3]

Prescribing $r$ present edges and $s$ absent edges in $G (n, p)$ has probability $p^{r} (1 - p)^{s}$ (A prescribed set of present and absent edges in $G (n, p)$ has product probability).

[L4]

Expectations of a finite family of random variables add without an independence hypothesis (Expectation is linear for every finite family of random variables, without any independence hypothesis).

[L5]

If a nonnegative integer-valued random variable on a finite probability space has expectation below $1$ , some outcome makes it $0$ (The first-moment method for avoiding or forcing a finite count of bad events).

[L6]

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

[L7]

For $b > 0$ with $b \neq 1$ and $x > 0$ , $\log_{b} x : = \log x / \log b$ (The logarithm to a positive base other than one).

[L8]

$\log : (0, \infty) \to R$ is strictly increasing, and for $x, y > 0$ satisfies $\log (x y) = \log x + \log y$ , $\log (1 / x) = - \log x$ , and $\log 1 = 0$ (Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

Proof

technique · constructive

1.1L7L8algebra

By [L8], $\log 2 > \log 1 = 0$ , so [L7] makes $\log_{2} = \log / \log 2$ strictly increasing with $\log_{2} 1 = 0$ . Applying $\log (x y) = \log x + \log y$ to the factors of an integer power, and $\log (1 / x) = - \log x$ for a negative exponent, gives $\log_{2} (2^{m}) = m$ for every integer $m$ and $\log_{2} (x^{j}) = j \log_{2} x$ for every $x > 0$ and every positive integer $j$ .

2.1givenstep 1.1algebra

Since $n \geq 16 = 2^{4}$ , step 1.1 gives $L : = \log_{2} n \geq 4$ , and $k = ⌈ 3 L ⌉$ satisfies $k \geq 3 L \geq 12$ .

3.1step 2.1L2L3L6

In $G (n, 1 / 2)$ let $X$ count the $k$ -subsets that induce a clique or a stable set. For a fixed $k$ -subset these two disjoint events each prescribe all $(\binom{k}{2})$ pairs, so [L2] and [L3] give probability $2 \cdot 2^{- (\binom{k}{2})}$ .

4.1step 3.1L4L6algebra

By [L4] and [L6], $E X = 2 (\binom{n}{k}) 2^{- k (k - 1) / 2} \leq 2 n^{k} 2^{- k (k - 1) / 2}$ .

5.1step 1.1step 2.1step 4.1algebra

By step 1.1 the base-two logarithm of that last bound is $1 + k L - k (k - 1) / 2 = 1 + k (L - (k - 1) / 2) \leq 1 + 3 L (1 - L) / 2 < 0$ , where the first inequality uses $k \geq 3 L$ and $L \geq 4$ , which make $L - (k - 1) / 2 \leq (1 - L) / 2 < 0$ . Since $\log_{2}$ is strictly increasing with $\log_{2} 1 = 0$ , the bound itself is below $1$ , so $E X < 1$ .

6.1step 3.1step 5.1L1L5constructdischarge-construct∎

By [L5], choose an outcome graph $G$ with $X = 0$ . It has no homogeneous $k$ -subset, and any homogeneous set of order at least $k$ would contain one, so $hom (G) \leq k - 1 < 3 L = 3 \log_{2} n$ .

Depends on

Used by

Dependency tree · two levels

34 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

A. Chernikov, MATH 223M notes, sec. 3.1 (standard reference, not scraped)

For every n≥16n≥16 there is an nn-vertex graph with hom⁡(G)<3log⁡2nhom(G)<3log2​n