Maximum chromatic number of $K_k$-free graphs: is $f_k(n)\gg n^{1-1/(k-1)}$ up to logs? (Erdős #920)
Statement
Let $f_k(n)$ be the maximum possible chromatic number of a graph on $n$ vertices which contains no $K_k$ (no clique on $k$ vertices). Is it true that, for $k\geq 4$, $$f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}$$ for some constant $c_k>0$?
Acceptance. FULLY RESOLVES: a proof that for every $k\geq 5$ (the cases $k=3,4$ being settled, per the background) there is a constant $c_k>0$ with $f_k(n)\gg n^{1-1/(k-1)}/(\log n)^{c_k}$; OR a refutation — a proof that for some $k\geq 4$ one has $f_k(n)\ll n^{1-1/(k-1)-\delta}$ for some fixed $\delta>0$. Machine-checkable (Lean/Coq) proof preferred, else a complete written proof. ADVANCES: (a) for any single $k\geq 5$, a lower bound on $f_k(n)$ with polynomial exponent strictly larger than the $1-\frac{1}{k-2}$ stated in the background, with proof; (b) an upper bound of strictly smaller order than the Graver–Yackel bound stated in the background, with proof; (c) the full conjecture for the single case $k=5$; (d) equivalently-phrased new bounds on $R(k,m)$ for fixed $k\geq 5$ that improve the $f_k$ frontier, with the translation made explicit. Deliver the proof file.
Background
Posed by Erdős [Er69b]; listed as open on erdosproblems.com/920 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'; page last edited 28 May 2026). This is the chromatic form of the off-diagonal Ramsey problem: bounds on $f_k$ translate into bounds on the Ramsey numbers $R(k,m)$ and vice versa. Graver and Yackel [GrYa68] proved the upper bound $f_k(n)\ll (n\log\log n/\log n)^{1-\frac{1}{k-1}}$, so a positive answer would pin down $f_k$ to within logarithmic factors. The case $k=3$ is known: $f_3(n)\asymp (n/\log n)^{1/2}$ (see erdosproblems.com/1104). The case $k=4$ is now settled affirmatively: the Mattheus–Verstraëte lower bound $R(4,m)\gg m^3/(\log m)^4$ (2023; see erdosproblems.com/166) yields $f_4(n)\gg n^{2/3}/(\log n)^{4/3}$, which is the conjectured shape with $c_4=4/3$. For $k\geq 5$ the question is open: the best known lower bound, via the bounds recorded at Erdős #986 (erdosproblems.com/986), is $f_k(n)\gg n^{1-\frac{1}{k-2}}/(\log n)^{c_k}$ — exponent $1-\frac{1}{k-2}$, strictly short of the conjectured $1-\frac{1}{k-1}$ — and a positive answer to Erdős #986 would imply a positive answer here. The statement is formalised in Lean in google-deepmind/formal-conjectures (ErdosProblems/920.lean). The attacker's tool: pseudorandom algebraic/geometric constructions in the Mattheus–Verstraëte style (finite-geometry graphs such as generalized quadrangles, combined with random sparsification and container/local-lemma analysis); this is proof-shaped work with no finite-witness shortcut.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #920 (T. F. Bloom) | website |
| REF-02 | S. Mattheus, J. Verstraëte — The asymptotics of r(4,t) (settles the k=4 case) | arxiv |
| REF-03 | Formalised statement of Erdős #920 (Lean, google-deepmind/formal-conjectures) | website |
| REF-04 | Erdős Problem #166 (T. F. Bloom) — R(4,m), source of the k=4 resolution | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.