2.7 KiB
2.7 KiB
title, created, updated, type, tags, sources, authors, venue, year
| title | created | updated | type | tags | sources | authors | venue | year | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| An exponential improvement for Ramsey lower bounds | 2026-06-29 | 2026-06-29 | paper |
|
|
|
arXiv:2507.12926v2 | 2026 |
An Exponential Improvement for Ramsey Lower Bounds
arXiv: 2507.12926v2, math.CO, April 2026
一句话
78 年来首次对 Erdős (1947) 的 Ramsey 数下界做出指数级改进，通过引入 random-sphere-graph 模型，将经典概率方法从离散随机图推广到连续几何测度空间。
核心结果
对任意常数 C > 1，存在 ε = ε(C) > 0，使得对充分大的 ℓ：
r(ℓ, Cℓ) ≥ (M_C + ε)^ℓ
其中 M_C = p_C^{-1/2}，p_C ∈ (0, 1/2) 是方程 C = log p_C / log(1-p_C) 的唯一解。
推论：对任意 δ ∈ (0, 1/2)，当 δ ≤ ℓ/k ≤ 1-δ 时：
r(ℓ, k) ≥ (1 + 2c_δ)^ℓ · (M_{k/ℓ})^ℓ ≥ (1 + c_δ)^ℓ · Er(ℓ, k)
（Er 为 Erdős 1947 年得到的下界）
方法论创新
随机球面图 G_{k,p}(n)
不再使用经典的 Erdős-Rényi random-graph-theory，而是在 k 维单位球面 S^k 上均匀采样 n 个点，以概率 p 连边。这是几何测度与概率方法的首次深度融合。
完美序列 (Perfect Sequences)
引入了组合新概念 —— perfect-sequences，作为刻画球面上点的邻接结构的核心工具。证明了完美序列能"捕获"问题在随机球面图下的本质行为（Section 7）。
技术路线
- 定义随机球面图模型（Section 2）
- 将主定理归约为核心技术定理 3.1（Section 3）
- 引入完美序列概念（Section 5）
- 估计完美序列的概率行为（Sections 6-8）
- 组合所有估计完成证明（Section 9）
- 几乎对角情形的改进：r(ℓ, ℓ+f(ℓ)) ≥ e^{Ω(f(ℓ)²/ℓ)} · Er(ℓ, ℓ+f(ℓ))，其中 √ℓ ≪ f(ℓ) ≪ ℓ
历史意义
| 年份 | 贡献 | 方法 |
|---|---|---|
| 1947 | Erdős 下界 | 概率方法 |
| 1975 | Spencer 常数因子改进 | [[lovasz-local-lemma |
| 2026 | 本文：指数级改进 | 随机球面图 + 完美序列 |