on the lower bound of Ramsey number

Overview

This note discusses the construction and lower bound updates for non-diagonal Ramsey numbers, specifically focusing on the “random sphere graph” approach.

🏷️ 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 established 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. This simple proof makes an upper estimate of $R(k,k)\ll 4^k/\sqrt{k}$. The proof is non-constructive.

For the lower bound, it depends on constructions such that the numbers of red or blue cliques do not meet the bound.

🏷️ Random Sphere Graph

The approach introduced in arXiv:2507.12926 utilizes a graph placed on the high-dimensional sphere $S^n$. Each node is connected to nearby nodes with blue edges and far nodes with red. When points are sampled uniformly on the sphere, a clique corresponds to points that are mutually far from each other.

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$$

This condition implies there exists a configuration of points on the random sphere graph where neither clique type occurs. The key idea is estimating $P_r(l)$ and $P_b(k)$ with a well-chosen dimension $n$. If $n$ is too high, almost all points are very far from each other, causing the graph to lose its geometric information and degenerate to a traditional $G(N,p)$ random graph.

🏷️ Estimating the Probabilities

(Analysis of probability estimates)

🏷️ Notes

🔗 See Also

• on sum-product in finite fields via entropy --- Both explore the “geometry of information,” using geometric configurations (spheres vs. finite field incidences) to bound combinatorial expansion.

📚 References