Constructive exponential lower bound for Ramsey numbers: explicit graphs forcing $R(k)>C^k$ (Erdős #78)
Statement
Let $R(k)$ be the diagonal Ramsey number (the least $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic $K_k$). Give a constructive (explicit, deterministic) proof that $R(k)>C^k$ for some constant $C>1$. Equivalently: for each $n$, explicitly construct a graph on $n$ vertices containing no clique and no independent set of size $\geq c\log n$ for some absolute constant $c>0$ (a 'Ramsey graph'). The existence of such graphs is classical via the probabilistic method; the open challenge is an explicit construction.
Acceptance. FULLY RESOLVES: an explicit, deterministic construction — together with a complete proof — of a family of graphs on $n$ vertices whose largest clique and largest independent set are both $O(\log n)$; equivalently, a constructive proof that $R(k)>C^k$ for some fixed constant $C>1$. A machine-checkable proof (Lean/Coq) of the construction's Ramsey bound is preferred; otherwise a complete written proof. ADVANCES (each independently checkable): an explicit construction whose maximum clique/independent set is provably smaller, as a function of $n$, than the best stated in the background (currently $(\log n)^{C}$, Li [Li23b]) — with a complete proof of the improved bound — or a constructive improvement of the best explicit lower bound on $R(k)$ itself. Deliver the construction (with an efficient generating procedure) plus the proof of its clique/independence bound.
Background
Posed by Erdős [Er69b], [Er71], [Er88], [Er93, p.337], [Er95], [Er97c]; listed as open on erdosproblems.com/78 (fetched 2026-07-13, status 'open', tagged 'graph theory | ramsey theory'), with an Erdős prize of \$100. Erdős's probabilistic argument gives the existence bound $R(k)\gg k2^{k/2}$ without producing any explicit graph; a constructive match needs an explicit family whose clique and independence numbers are both $O(\log n)$. Progress on explicit Ramsey graphs: Erdős [Er69b] first asked even for an explicit construction with largest clique/independent set $o(n^{1/2})$, which is now known; Cohen [Co15] constructed explicit graphs on $n$ vertices with no clique or independent set of size $\geq 2^{(\log\log n)^{C}}$; and Li [Li23b] recently improved this to $\geq(\log n)^{C}$ for some constant $C>0$. Reaching the target $O(\log n)$ — equivalently a constructive $R(k)>C^k$ with a fixed base $C>1$ — remains open. The problem sits at the heart of the explicit-construction / pseudorandomness program in theoretical computer science (two-source and affine extractors, dispersers). Attacker's tool: explicit algebraic / character-sum and extractor-based constructions, with computer verification of the clique and independence numbers of candidate families on small $n$ to guide and sanity-check a claimed asymptotic construction.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #78 (T. F. Bloom) | website |
| REF-02 | OEIS A059442 — array of Ramsey numbers R(n,k) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.