按年被提到
20232023 · 3 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:2303.09521 · math.CO

An exponential improvement for diagonal Ramsey

对角 Ramsey 数的指数级改进
Marcelo Campos, Simon Griffiths, Robert Morris, Julian Sahasrabudhe · 2023

对角 Ramsey 数上界首次指数级改进,R(k) ≤ (4−ε)^k。

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2023-03-17 · 最近 2023-12-11
3不同的人
3活跃月份
3讨论串
34被引(OpenAlex)

Ramsey 数 R(k) 是使完全图 K_n 的任意红蓝边着色必含单色 K_k 的最小 n。论文证明 R(k) ≤ (4−ε)^k 对某个常数 ε>0 成立。这是自 1935 年 Erdős 与 Szekeres 给出上界以来的第一个指数级改进。

HN 为什么提它

评论者强调它把自 1935 年以来一直未动的 4^k 上界改进到了 (4−ε)^k。

其他难度 5 / 5约 360 分钟经得起时间
读之前最好知道
1Ramsey 理论(Ramsey theory)
2图论基础(完全图、边着色)
3概率方法与渐近分析
4Erdős–Szekeres 上界

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用OJFord · 2023-12

“The main proof is an improvement to the 4^k bound (standing since 1935) to (4-eps)^k for some epsilon.”

说明主要证明是把自 1935 年的 4^k 上界改进为 (4-eps)^k
A Big Small Leap Forward in Graph Theory原评论 ↗
被提交为 story · 2 次