Ramsey 数指数型下界的突破

hbghlyj

gilkalai.wordpress.com/2025/07/23/amazing-jie … -ramsey-lower-bounds
在组合数学中，Ramsey数 $R(\ell,k)$ 是衡量在两种颜色边着色下必现单色团的最小图规模，Erdős 于1947年首次通过概率方法给出指数型下界，Spencer 于1975年利用 Lovász 局部引理对该下界进行常数因子级别的提升。近期，Jie Ma、Wujie Shen 和 Shengjie Xie 在 arXiv 上发表新论文，首次实现了对 $R(\ell,C\ell)$ 下界的指数级改进，证明了对于任意常数 $C>1$，存在 $\varepsilon(C)>0$ 使得
$$
r(\ell,C\ell)\ge\bigl(p_C^{-1/2}+\varepsilon\bigr)^\ell,
$$
其中 $p_C\in(0,1/2)$ 是满足 $C=\frac{\log p_C}{\log(1-p_C)}$ 的唯一解。

hbghlyj

论文提出了一种基于高维球面几何随机模型的图着色方案：首先在 $d$ 维单位球面上随机选取 $n$ 个点，然后以距离阈值为准对点对连边进行红/蓝着色，以保证每条边被染成红色的概率正好为 $p_C$ 。这一模型与经典 Erdős–Rényi 二元随机图 $G(n,p)$ 相似，但引入了点间的几何依赖性，使得大规模单色团出现的概率显著降低。

作者深入分析了模型中维度 $d$ 的选取以及红色和蓝色团的大小估计，利用精细的概率与几何工具计算出当 $\ell\to\infty$ 时所需的阈值和下界系数。