on the lower bound of Ramsey number

Overview

Ma, Shen, and Xie proved the first exponential improvement over the classical Erdős lower bound for comparable Ramsey numbers $R(\ell ,C\ell )$, using a random graph whose vertices are random points on a high-dimensional sphere (Ma, Shen & Xie, 2026). Hunter, Milojević, and Sudakov later gave a cleaner Gaussian random graph proof of the same phenomenon, with sharper quantitative control (Hunter, Milojević & Sudakov, 2026). The central idea is that a geometric random graph has weak but useful edge correlations: red cliques become less likely than in an independent-edge model, while the blue-clique penalty can be compensated by a small shift in the edge density.

🏷️ The Classical Baseline

The Ramsey number $R(\ell ,k)$ is the smallest $n$ such that every red-blue coloring of the complete graph $K_n$ contains either a red $K_{\ell }$ or a blue $K_k$. In the notation $R(\ell ,C\ell )$ below, we suppress the harmless integer-rounding of $C\ell$. The Erdős-Szekeres induction gives the upper bound

$$R(\ell ,k)\le \left(\genfrac{}{}{0ex}{}{\ell +k-2}{\ell -1}\right),$$

and hence $R(\ell ,\ell )\le 4^{\ell }$ up to polynomial factors (Erdős & Szekeres, 1935). The lower bound, in the comparable regime $k=C\ell$, begins with Erdős’s 1947 random coloring argument (Erdős, 1947).

Color each edge red with probability $p$ and blue with probability $1-p$, independently. The expected number of red $K_{\ell }$‘s and blue $K_{C\ell }$‘s is bounded by

$$\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)p^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}+\left(\genfrac{}{}{0ex}{}{n}{C\ell }\right)(1-p{)}^{\left(\genfrac{}{}{0ex}{}{C\ell }{2}\right)}.$$

If this is less than $1$, then some coloring avoids both forbidden cliques. Optimizing the two terms gives the parameter $p_C\in (0,1/2)$ determined by

$$C=\frac{\log p_C}{\log (1-p_C)}.$$

Equivalently, $p_C=(1-p_C{)}^C$. The exponential base in the classical lower bound is

$$M_C:=p_C^{-1/2}=(1-p_C{)}^{-C/2},$$

so Erdős’s method gives, up to polynomial factors,

$$R(\ell ,C\ell )\gtrsim M_C^{\ell }.$$

Spencer’s Local Lemma refinement improves only the constant factor in front of this bound, not the exponential base (Spencer, 1975). The new papers change the base itself.

Ma-Shen-Xie exponential improvement

For every fixed $C>1$, there are constants $\epsilon (C)>0$ and ${\ell }_0(C)$ such that, for all $\ell \ge {\ell }_0(C)$,

$$R(\ell ,C\ell )\ge (M_C+\epsilon (C){)}^{\ell }.$$

This is the first exponential improvement over the Erdős lower bound in the comparable regime $k=C\ell$ (Ma, Shen & Xie, 2026). The paper appeared online in Inventiones Mathematicae on May 4, 2026.

🏷️ Why a Geometric Model Helps

In the independent random coloring, the probabilities of monochromatic cliques are exactly

$$P_{\mathrm{red},r}^{\mathrm{ER}}=p^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)},P_{\mathrm{blue},r}^{\mathrm{ER}}=(1-p{)}^{\left(\genfrac{}{}{0ex}{}{r}{2}\right)}.$$

This independence is too rigid. The random sphere graph deliberately introduces a weak geometric dependence between adjacent edges. If two points are both far from a third point, then they are slightly more likely to be close to each other. In the coloring convention of Ma-Shen-Xie, this makes red triangles less likely and blue triangles more likely:

$$P_{\mathrm{red},3}<p^3,P_{\mathrm{blue},3}>(1-p{)}^3.$$

At first this sounds like a tradeoff rather than a gain. The key point is that the red saving and the blue loss have different coefficients. After choosing $p$ slightly larger than $p_C$, the blue clique probability is pushed back down, while enough of the red saving remains to improve both union-bound terms simultaneously.

🏷️ Random Sphere Graphs

Fix a dimension $k$ and a parameter $p\in (0,1/2]$. Let $x_1,\dots ,x_n$ be independent uniform points on the unit sphere $S^k$. Choose $c_{k,p}$ so that, for a fixed unit vector $e$,

$$\mathbb{P}\left(⟨x,e⟩\le -\frac{c_{k,p}}{\sqrt{k}}\right)=p.$$

The complete graph on $x_1,\dots ,x_n$ is colored by

$$x_i{x}_j\text{ is red}⟺⟨x_i,x_j⟩\le -\frac{c_{k,p}}{\sqrt{k}},$$

and blue otherwise. Each individual edge is red with probability $p$, but edges sharing vertices are not independent.

Let $P_{\mathrm{red},r}$ be the probability that $r$ sampled points form a red clique, and let $P_{\mathrm{blue},r}$ be the probability that they form a blue clique. The whole Ramsey construction reduces to estimating

$$P_{\mathrm{red},\ell },P_{\mathrm{blue},C\ell }$$

accurately enough to run the same first-moment argument as in the Erdős proof.

🏷️ The Main Estimate

The dimension is chosen in the intermediate regime

$$k=D^2{\ell }^2,$$

where $D=D(C)$ is a large constant. If $k$ were much larger, random points on $S^k$ would become almost orthogonal and the model would collapse back to an Erdős-Rényi random graph. If $k$ were much smaller, the blue-clique correlations would become too strong. The scale $k\asymp {\ell }^2$ keeps the geometric correction visible but controllable.

The technical theorem behind Ma-Shen-Xie says that one can choose $p\in (p_C,1/2)$ so that

$$P_{\mathrm{red},\ell }\le {\left(p_C-{\epsilon }_0\frac{\ell }{\sqrt{k}}\right)}^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)},$$

and

$$P_{\mathrm{blue},C\ell }\le {\left(1-p_C-{\epsilon }_0\frac{\ell }{\sqrt{k}}\right)}^{\left(\genfrac{}{}{0ex}{}{C\ell }{2}\right)}.$$

Since $\ell /\sqrt{k}=1/D$, these are genuine base improvements. Taking $n=(M_C+\epsilon {)}^{\ell }$ and applying the union bound to red $K_{\ell }$‘s and blue $K_{C\ell }$‘s gives a coloring with neither clique.

The proof is built from an incremental decomposition. For example,

$$P_{\mathrm{red},\ell }={\kappa }_1{\kappa }_2\cdots {\kappa }_{\ell -1},{\kappa }_r=\frac{P_{\mathrm{red},r+1}}{P_{\mathrm{red},r}}.$$

Conditioning on a red $r$-clique, ${\kappa }_r$ is the expected measure of the common red neighborhood of the first $r$ points. The corresponding blue quantities are handled similarly. The estimates have the schematic form

$$\frac{{\kappa }_{r+1}}{{\kappa }_r}\lesssim p-\frac{a}{p^2}\frac{r}{\sqrt{k}},\frac{{\bar{\kappa }}_{r+1}}{{\bar{\kappa }}_r}\lesssim 1-p+\frac{a}{(1-p{)}^2}\frac{r}{\sqrt{k}},$$

where $a>0$ depends on the threshold. The inequality

$$\frac{1}{p_C^2}>\frac{C}{(1-p_C{)}^2}$$

is the bookkeeping reason that the red saving dominates the blue loss after balancing the two clique sizes.

Proof mechanism: perfect sequences

The difficult part is that the points in a conditioned red or blue clique are not independent. Ma-Shen-Xie introduce “perfect sequences,” meaning sequences whose new point has very small projection onto the span of the earlier points. Random sequences are overwhelmingly perfect at the scale used in the proof, while non-perfect sequences can be charged to an exponentially small exceptional set. On perfect sequences, the common-neighborhood measures can be controlled through orthogonal projections, leading to the second-order estimates above.

🏷️ Gaussian Random Graphs

Hunter, Milojević, and Sudakov give a shorter proof by replacing the sphere with a Gaussian product measure (Hunter, Milojević & Sudakov, 2026). Let

$$x_1,\dots ,x_n\sim N\left(0,\frac{1}{d}{I}_d\right)$$

independently. Let $c_p>0$ satisfy $\mathbb{P}(Z\le -c_p)=p$ for $Z\sim N(0,1)$. Define a graph $G(n,d,p)$ by putting a blue edge between $i$ and $j$ when

$$⟨x_i,x_j⟩\ge -\frac{c_p}{\sqrt{d}},$$

and color missing edges red. Since $\Vert x_i\Vert$ is highly concentrated near $1$, this model is close in spirit to the sphere graph. The advantage is that Gaussian coordinates are independent, so the projection calculations become much cleaner.

Their key estimate makes the triangle-correction heuristic explicit. Put

$$a=\frac{e^{-c_p^2/2}}{\sqrt{2\pi }},d=D^2{\ell }^2.$$

Then, up to lower-order errors,

$$P_{\mathrm{red},\ell }\le p^{\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}\exp \left(-\left(\genfrac{}{}{0ex}{}{\ell }{3}\right)\frac{a^3}{p^3\sqrt{d}}\right),$$

while

$$P_{\mathrm{blue},C\ell }\le (1-p{)}^{\left(\genfrac{}{}{0ex}{}{C\ell }{2}\right)}\exp \left(\left(\genfrac{}{}{0ex}{}{C\ell }{3}\right)\frac{a^3}{(1-p{)}^3\sqrt{d}}\right).$$

The negative exponent for red cliques is the gain; the positive exponent for blue cliques is the cost. The same balancing inequality as above shows that the gain wins after moving $p$ slightly above $p_C$.

Quantitative improvement from the Gaussian proof

Besides simplifying the proof, the Gaussian model gives better constants. For sufficiently large $C$, Hunter-Milojević-Sudakov show that the base can be multiplied by $e^{1/24}$:

$$R(\ell ,C\ell )\ge {\left(e^{1/24}{M}_C\right)}^{\ell }$$

for all sufficiently large $\ell$. Near the diagonal regime $C\downarrow 1$, their proof gives the same qualitative behavior as Ma-Shen-Xie, with improvement of order $\Omega ((C-1{)}^2)$.

🏷️ Comparison

Paper	Model	Main role	Technical bottleneck
Ma-Shen-Xie (Ma, Shen & Xie, 2026)	Uniform points on $S^k$	First exponential improvement over Erdős’s lower bound	Controlling conditioned spherical projections via perfect sequences
Hunter-Milojević-Sudakov (Hunter, Milojević & Sudakov, 2026)	Gaussian vectors in ${\mathbb{R}}^d$	Simpler proof and better quantitative constants	Bounding clique and independent-set probabilities using product Gaussian structure

Both papers prove that the Erdős random coloring is not optimal in the exponential base for $R(\ell ,C\ell )$ when $C>1$ is fixed. The improvement is not obtained by an explicit deterministic construction. It is still a probabilistic construction, but with correlated edges tuned so that one forbidden color receives a stronger suppression than the other color pays back.

🏷️ What to Remember

This is a comparable-parameter result, not the fixed-$\ell$ off-diagonal regime of $R(3,k)$. The surprise is that the classical independent random graph had resisted exponential-base improvement for almost eighty years, while a very mild geometric correlation breaks the barrier.

The Gaussian version also clarifies the mechanism: the relevant correction is already visible at the triangle level. Red triangles are suppressed by a factor roughly $1-a^3/(p^3\sqrt{d})$, blue triangles are enhanced by a factor roughly $1+a^3/((1-p{)}^3\sqrt{d})$, and the Ramsey optimization point $p_C$ makes the former effect stronger after the final density shift.

🔗 See Also

• on new lower bounds of R(3, k) --- This is the fixed-triangle off-diagonal regime; it also uses structured randomness to beat a long-standing random-process barrier, but the asymptotic scale is $k^2/\log k$ rather than $M_C^{\ell }$.
• on sum-product in finite fields via entropy --- Both notes use hidden geometric or algebraic dependence to improve a naive independent-random heuristic.
• on the sum-product conjecture’s falsity --- Another example where a structured high-dimensional construction defeats a natural expansion heuristic.

📚 References

🐻  Erdős, P. 1947. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society 53, 292–294.

🐻  Erdős, P. & Szekeres, G. 1935. A combinatorial problem in geometry. Compositio Mathematica 2, 463–470.

🐻  Hunter, Z., Milojević, A. & Sudakov, B. 2026. Gaussian random graphs and Ramsey numbers.

🐻  Ma, J., Shen, W. & Xie, S. 2026. An exponential improvement for Ramsey lower bounds. Inventiones Mathematicae.

🐻  Spencer, J. 1975. Ramsey’s theorem—A new lower bound. Journal of Combinatorial Theory, Series A 18(1), 108–115.