Explicit Ramsey graphs

A random graph on $n$ vertices has, with high probability, no clique and no independent set larger than about $2\log_2 n$ . Erdős asked for a construction, rather than a probabilistic existence proof, of graphs that are nearly as good: no homogeneous set of size $c\log n$ . In theoretical computer science, explicit Ramsey graphs are closely tied to randomness extractors.

Problem

Call a graph on $n$ vertices $t$ -Ramsey if it contains no clique and no independent set of size $t$ . Give an explicit construction of $t$ -Ramsey graphs on $n$ vertices with $t\le c\log n$ for some constant $c>0$ , for infinitely many $n$ ; equivalently, a constructive proof that the diagonal Ramsey number satisfies $R(k)>C^k$ for some $C>1$ .

"Explicit" is understood in the strong sense used in the modern literature: there is an algorithm that, given two vertices, decides whether they are adjacent in time polynomial in $\log n$ .

Erdős offered $100 for this problem.

Background

Erdős proved in 1947 that $R(k)>2^{k/2}$ by showing that a random colouring works, one of the first uses of the probabilistic method, and asked for a construction that achieves an exponential bound. Derandomising his argument by the method of conditional expectations gives a deterministic algorithm with running time $2^{O(k^2)}$ , as noted on the problem's forum, but this does not yield graphs whose edges can be computed quickly. Recent progress has come from the construction of two-source dispersers and extractors.

What is known

Erdős's 1969 variant. He also asked for an explicit graph whose largest clique and independent set have size $o(n^{1/2})$ ; this is now known.
Cohen (2016) constructed explicit graphs with no clique or independent set of size $2^{(\log\log n)^C}$ for a constant $C$ .
Li (2023) improved this to $(\log n)^{C}$ for a constant $C$ , via two-source extractors for asymptotically optimal entropy. The remaining gap to the random bound is a polynomial in $\log n$ .

What would count as progress

An explicit family of graphs with no homogeneous set of size $(\log n)^{C}$ for a smaller constant $C$ than in Li's construction, with the adjacency algorithm given as code.
An explicit construction achieving $c\log n$ , which would solve the problem.
For moderate $n$ , explicit graphs whose largest homogeneous sets can be certified by computer and compare well with random graphs, as evidence for a candidate construction.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294. doi:10.1090/S0002-9904-1947-08785-1
G. Cohen, Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs, in Proc. 48th ACM Symposium on Theory of Computing (2016), 278–284. doi:10.1145/2897518.2897530
X. Li, Two source extractors for asymptotically optimal entropy, and (many) more, in Proc. 64th IEEE Symposium on Foundations of Computer Science (2023), 1271–1281. doi:10.1109/FOCS57990.2023.00075

Source

Imported from Erdős Problems 78, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.