on the lower bound of Ramsey number

Note

This short note is to discuss the idea of arXiv:2507.12926. It updates the lower bound of the non-diagonal Ramsey number (in fact very far from diagonal).

Ramsey Number

The Ramsey Number $R(l,k)$ denotes the smallest size $n$ of red-blue colored complete graph $K_n$ that always contains either a red clique $K_l$ or a blue $K_k$.

The upper bound of $R(l,k)$ was made by Erdős and Szekeres through induction

$$R(l,k)\le R(l-1,k)+R(l,k-1).$$

Basically, if we choose a node $x$, and the rest of nodes are grouped depending on the edge connected to $x$, then we only need to look at the two groups, either the red group has at least $R(l-1,k)$ nodes or the blue group has at least $R(l,k-1)$ nodes, then proved. This simple proof makes an upper estimate of $R(k,k)\ll 4^k/\sqrt{k}$. The proof is not constructive.

For the lower bound, it will depend on a construction such that the numbers of red or blue cliques do not meet the bound.

Random Sphere Graph

In the paper arXiv:2507.12926, it introduces a graph placed on the high dimensional sphere $S^n$, the each node is connected to nearby nodes with blue edges and far nodes with red, when the points are sampled uniformly on the sphere, the probably space is $S^n\times S^n\cdots \times S^n$, and a clique means the points are far from each other, or the intersection of far regions has nonzero measure.

Let $P_r(l)$ be the probability of appearance of a red clique and $P_b(k)$ for a blue clique on this random sphere graph of size $N$ in $n$ dimensions. Then the lower bound of $R(l,k)$ can be found if:

$$P_r(l)+P_b(k)<1$$

It means there exists a configuration of points on the random sphere graph making both not happen.

The key idea will be estimating $P_r(l)$ and $P_b(k)$, with a well-chosen dimension $n$. Because if $n$ is too high, almost all points are very far from each other, the distance is meaningless, the whole graph loses its geometric information and degenerates to the traditional graph $G(N,p)$.

Estimate the Probabilities

Notes

Links