Erdős #78 — constructive proof that $R(k)>C^k$

Statement

Let $R(k)$ be the Ramsey number for $K_k$: the minimal $n$ such that every $2$-colouring of the edges of $K_n$ contains a monochromatic copy of $K_k$. Give a constructive proof that $R(k) > C^k$ for some constant $C>1$ — i.e. an explicit (efficiently computable), infinite family of $2$-colourings / graphs witnessing an exponential lower bound, as opposed to Erdős's non-constructive probabilistic argument. (erdosproblems.com/78, statement verbatim.)

Equivalently (as stated on the source page): construct, for infinitely many $n$, an explicit graph on $n$ vertices with no clique and no independent set of size $\geq c\log n$, for some constant $c>0$.

Facts

- Prize \$100; status open; erdosproblems.com explicitly states "This is open, and cannot be resolved with a finite computation" (fetched 2026-07-02, page last edited 23 January 2026). - Falsifiable: no — this asks for an infinite explicit family with a proved asymptotic property; no finite computation, however large, can establish "for all $k$" behaviour of an infinite construction. - Origin: Erdős, across [Er69b], [Er71], [Er88], [Er93,p.337], [Er95], [Er97c]; also Vaughan's problem list [Va99,3.49]. Listed as #4 in the "Ramsey Theory" section of the graphs problem collection (the immediately preceding problem in that same section, #3, is the value of $\lim R(k)^{1/k}$ — Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$). - Erdős's own bound is non-constructive: a simple probabilistic (random-colouring) argument gives $R(k) \gg k2^{k/2}$ — exponentially strong, but produces no explicit witnessing graph, only an existence proof. This problem asks specifically for an *explicit/algorithmic* construction matching (any) exponential rate, not for improving the exponent itself. - Progress is measured on the reformulated version: explicit $n$-vertex graphs with no clique/independent-set $\geq f(n)$, and how small $f(n)$ can be made explicitly (the probabilistic proof gives $f(n)=O(\log n)$ non-constructively; the target for this problem is any explicit construction with $f(n) = O(\log n)$, which lets one recover $R(k) > C^k$ for a constant $C>1$ by inverting $n \leftrightarrow k$): - Frankl–Wilson, *Intersection theorems with geometric consequences*, Combinatorica 1 (1981) 357–368 — an early major explicit (algebraic/finite-geometry, set-intersection-modulo-a-prime) construction beating trivial bounds; cited as background history by Cohen [Co15]'s introduction (exact quantitative bound not independently re-derived in this search — flagged as unverified-in-detail). - Barak, Rao, Shaltiel, Wigderson, *2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl–Wilson construction*, Annals of Math. 176 (2012) 1483–1543 (journal version of STOC 2006) — explicit construction achieving $K = 2^{2^{(\log\log n)^{1-\alpha}}}$-Ramsey graphs for a small universal $\alpha>0$ (bound as stated in the introduction of [Co15], arXiv:1506.04428, read directly). - Cohen, *Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs*, arXiv:1506.04428 (2015) — improves this to $K = 2^{(\log\log n)^{C}}$-Ramsey graphs for a universal constant $C$, by resolving the construction of two-source dispersers for polylogarithmic min-entropy (abstract read directly). - Li, *Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More*, arXiv:2303.06802 (FOCS 2023) — this is [Li23b] on erdosproblems.com. Current best: explicit $K$-Ramsey graphs on $N$ vertices with $K = (\log N)^{O(1)}$ (abstract read directly), via the first asymptotically-optimal ($O(\log n)$-entropy) explicit two-source / seeded non-malleable extractors. - Gap remaining: the target is $K = O(\log N)$ (to recover $R(k)>C^k$ exactly); Li's $K=(\log N)^{O(1)}$ is polylogarithmic, i.e. still a power away from the needed single-log bound. No paper found in this search (WebSearch sweep through mid-2026) closes this remaining gap — the problem is genuinely still open as of the page's last edit (23 Jan 2026). - Related problems: Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ — the *value* of $\lim R(k)^{1/k}$ (upper-bound side has had a major 2023–2024 breakthrough, CGMS23 et al., see that page); this problem (#78) is the *constructive/algorithmic* analogue of the *lower*-bound side. Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — refining the polynomial factor of Erdős's non-constructive lower bound $R(k) \gg k2^{k/2}$ (a different axis: sharper existence bound, still non-constructive).

Literature state

Not resolved — genuinely open, confirmed both by erdosproblems.com's explicit "OPEN" tag (last edited 23 Jan 2026) and by this search finding no construction beyond Li's 2023 polylog bound. This is a *very actively worked* open problem in theoretical computer science / pseudorandomness, not a neglected one:

- The problem is exactly equivalent (as erdosproblems.com's own remarks note) to explicitly constructing $n$-vertex graphs with clique number and independence number both $o(n^{1/2})$ — first achieved non-explicitly by Erdős 1947, and the frontier of *explicit* constructions has moved from Frankl–Wilson (1981, algebraic) → Barak–Rao–Shaltiel–Wigderson (2006/2012, two-source dispersers, first to beat Frankl–Wilson) → Cohen (2015, arXiv:1506.04428, polylog-entropy two-source dispersers) → Li (2023, arXiv:2303.06802, FOCS 2023), the current record, giving $K=(\log N)^{O(1)}$-Ramsey graphs via asymptotically-optimal two-source/non-malleable extractors. - This chain of results is a textbook case of the equivalence between explicit two-source extractors/dispersers and explicit Ramsey graphs: an explicit two-source extractor (or even just a disperser) for sufficiently low min-entropy sources on $\{0,1\}^n \times \{0,1\}^n$ directly yields an explicit $2^n$-vertex Ramsey graph with clique/independent-set bound governed by the entropy threshold the extractor handles. Pushing the entropy threshold down to $O(\log n)$ (currently at $(\log n)^{O(1)}$, i.e. Li's result) is *precisely* what would resolve Erdős #78. - No AI-system attempt on this specific problem was found (not checked against the github.com/teorth/erdosproblems "AI contributions" wiki in this pass — flagged as a gap to close in a follow-up search). - Conclusion: open, with the gap between best known ($(\log n)^{O(1)}$) and target ($O(\log n)$) being an active, named, and highly technical target in the pseudorandomness/extractor literature — this is not a problem where a quick derivation is plausible; it sits at the frontier of a mature research program (correlation breakers, non-malleable extractors, "extractor recipes") led by Xin Li and collaborators over roughly two decades.

Attack surface

- Mode: derivation+formalization (not finite-search: falsifiability is explicitly "not finite" — any candidate must be an infinite explicit family with a general proof, not a computation over small cases; also not pure literature-resolution, since genuinely unsolved). - Concrete first experiment: this is not amenable to a CP-SAT/computational-search-style first experiment in the way many other Erdős problems are, because the object needed is an *infinite explicit family* with an asymptotic guarantee, not a witness at one size. The only computationally-flavoured foothold: (1) implement Li's 2023 construction (arXiv:2303.06802) concretely for moderate $n$ and empirically measure the actual clique/independent-set size achieved vs. the $(\log n)^{O(1)}$ asymptotic bound, to build intuition for where the slack in the proof is; (2) survey whether any of Li's non-malleable-extractor / correlation-breaker machinery has a "last mile" component (analogous to how each historical improvement — BRSW→Cohen→Li — closed a specific technical gap) that a focused literature dive could identify as the next incremental target. - Oracle: any candidate resolution must be checked by the normal mathematical/CS-theory route (peer review or, ambitiously, formalization of the extractor construction and its entropy-loss analysis in Lean/Isabelle) — there is no finite computational oracle for the general claim, though a specific proposed explicit construction can be spot-checked computationally on small-to-moderate $n$ before attempting a full asymptotic proof. - Feasibility: famous-and-hard — this is a live frontier problem in explicit pseudorandom-object construction (two-source extractors/dispersers), not a target plausibly closable by us in the near term. It is the kind of problem where the last major advance (Li 2023, FOCS) came from resolving a specific technical bottleneck (asymptotically-optimal non-malleable extractors) that itself took the field roughly a decade to reach. Realistic near-term value for us is literature-tracking (this page) plus possibly a narrow computational/expository sub-task (item 1 above), not attempting the open gap directly.

Related

- Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$ — value of $\lim_{k\to\infty}R(k)^{1/k}$; the *upper*-bound side of diagonal Ramsey asymptotics has seen a major 2023–2024 breakthrough (CGMS23 and follow-ups), while this problem (#78) is the *constructive lower*-bound analogue, still stuck behind a "polylog vs log" gap. Both are in the same "Ramsey Theory" section (#3 and #4) of the graphs problem collection. - Erdős #1029 — polynomial-factor lower bound $R(k)/(k2^{k/2})\\to\\infty$ — $R(k)/(k2^{k/2})\to\infty$: sharpening the *non-constructive* probabilistic lower bound's polynomial factor; a different axis from #78's demand for an *explicit* construction. - concept/two-source-extractors — the core pseudorandomness object; explicit two-source extractors for near-optimal min-entropy directly yield explicit Ramsey graphs, the mechanism behind every advance in this problem's history. - concept/two-source-dispersers — the weaker (one-sided) relative of extractors used by BRSW (2012) and Cohen (2015); sufficient for Ramsey-graph constructions and technically easier than full extractors. - concept/non-malleable-extractors — the key technical tool in Li's 2023 breakthrough (arXiv:2303.06802), building on a line of "non-malleable extractor" work Li himself developed since ~2012. - concept/correlation-breakers — the combinatorial primitive underlying modern non-malleable-extractor constructions (Li and collaborators), the proximate technique behind closing successive entropy gaps in this line of work. - concept/extractor-ramsey-graph-equivalence — the folklore TCS equivalence: an explicit disperser/extractor for two independent weak sources on $\{0,1\}^n$ gives an explicit $2^n$-vertex Ramsey graph, and vice versa; the structural reason progress on #78 tracks progress in randomness-extraction theory. - concept/frankl-wilson-polynomial-method — the earliest major explicit (finite-geometry / set-intersection mod $p$) construction in this line, Frankl–Wilson 1981, later beaten by extractor-based methods (BRSW 2012). - concept/probabilistic-method — Erdős's original 1947 non-constructive argument giving $R(k)\gg k2^{k/2}$, i.e. exactly the existence result this problem asks to make constructive (same concept as cited on Erdős #77 — value of $\\lim_{k\\to\\infty}R(k)^{1/k}$).