Erdős’s Classic Ramsey Lower Bound Gets First Exponential Boost After 80 Years

In 1947 Paul Erdős introduced the probabilistic method, showing that certain graphs must exist by arguing that a random coloring has non‑zero probability of avoiding a forbidden monochromatic clique. This revolutionary technique proved lower bounds for Ramsey numbers without constructing explicit examples.

Ramsey numbers measure how large a graph must be to guarantee a monochromatic clique of a given size under any two‑color edge coloring. Classic examples are R(3)=6 and R(3,4)=9. Computing exact values is notoriously hard, and for most parameters only coarse bounds are known.

For eight decades the lower bounds derived from Erdős’s method barely improved; for instance, Erdős proved R(1000) > 2^500, and the best subsequent result raised this only to about 2^501. Similar stagnation occurred for many non‑diagonal Ramsey numbers.

In the spring of 2024 graduate student Wujie Shen (Tsinghua University), together with Jie Ma and Shengjie Xie, proposed a new random‑coloring model that incorporates geometry. They place each vertex independently at a random point on the surface of a high‑dimensional sphere. After all vertices are placed, an edge is colored red if the Euclidean distance between its endpoints exceeds a fixed threshold (probability < ½); otherwise it is colored blue.

This geometric scheme reduces the chance of forming a large red monochromatic clique because creating such a clique would require many pairs of vertices to be far apart, which is unlikely on a sphere of limited volume. However, the trade‑off is an increased likelihood of blue cliques, a point highlighted by David Conlon and Benny Sudakov.

Through a year of intensive calculation (about 40 pages of dense analysis), the authors proved a sharper exponential lower bound for near‑diagonal Ramsey numbers R(3, l). Their result improves the growth rate from the previous bound (shown as an image in the original article) to a new bound (also shown as an image), representing the first improvement on this problem in roughly 50 years.

The breakthrough sparked further work. In December 2025 Sudakov and two students simplified the geometric model and pushed the lower bound even higher. Subsequent researchers have adapted the technique to three‑color Ramsey numbers, demonstrating the method’s versatility.

Overall, the geometric random‑graph approach revitalizes the probabilistic method, providing a fresh tool for tackling longstanding questions in discrete mathematics and combinatorial graph theory.