After 80 Years, Chinese Researchers Achieve Exponential Improvement on Erdős’ Ramsey Lower Bounds

In 1947 Paul Erdős introduced the probabilistic method to prove the existence of graphs without certain monochromatic cliques, establishing the first lower bounds for Ramsey numbers such as R(3)=6 and R(3,4)=9. The method showed that a random coloring of all possible edge assignments yields a non‑zero chance of avoiding the forbidden structure.

For the next 80 years the lower bounds for diagonal Ramsey numbers improved only marginally; for example, Erdős proved R(1000) > 2^500 and later work raised this to roughly 2^501, while similar stagnation occurred for many non‑diagonal cases.

In spring 2024 graduate student Wujie Shen, inspired by a recent paper, proposed a new random model that places each vertex independently on the surface of a high‑dimensional sphere. After the placement, edges are colored red if the distance between the two vertices exceeds a fixed threshold (probability < ½) and blue otherwise.

This geometric approach reduces the probability of forming a large red monochromatic clique because creating such a clique would require many vertex pairs to be far apart, a configuration that is unlikely on a high‑dimensional sphere. However, it simultaneously increases the chance of blue cliques, a trade‑off highlighted by David Conlon.

Ma, Shen, and Xie proved that in high dimensions the lines from the vertices to the sphere’s centre are almost orthogonal, a property absent in low dimensions. This orthogonality limits the possible distances between vertices, thereby lowering the probability of a monochromatic clique. Their proof, spanning about 40 pages of dense calculations, culminates in an exponential improvement for near‑diagonal Ramsey numbers.

Their paper, titled An exponential improvement for Ramsey lower bounds (arXiv:2507.12926), shows that for cases where the forbidden blue clique is about twice the size of the red one, the previous bound

is improved to

. Although the numerical gain is tiny, it marks the first advancement on the near‑diagonal problem in half a century.

Subsequent work by Benny Sudakov and his students simplified the coloring model and pushed the bounds further, and other researchers have applied the technique to three‑color Ramsey numbers, demonstrating the method’s growing influence.

Overall, the new geometric variant of the probabilistic method revitalizes Erdős’ legacy, showing that incorporating high‑dimensional geometry can break long‑standing barriers in combinatorial mathematics.