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

1. 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
2. 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
3. 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.