我校组合数学团队实现拉姆齐数下界的指数级改进
发布时间:
近日，中国科学技术大学数学科学学院马杰教授、清华大学丘成桐数学科学中心博士研究生申武杰，以及中国科大数学科学学院研究生谢晟捷三人合作，在拉姆齐数下界研究方面取得重要突破。研究团队通过引入“随机球面图”模型，证明了对于任意常数 C > 1 和充分大的 l，拉姆齐数 r(l, Cl) 的下界实现了自1947年埃尔德什经典结果以来的首次指数级改进。相关成果5月4日在线发表于国际数学知名期刊《数学新进展》（Inventiones Mathematicae）。
拉姆齐数是图论中最具挑战性的研究对象之一，度量了完全图中避免出现单色团块的最大规模。1947年，埃尔德什开创性地使用概率方法证明了拉姆齐数的指数下界，但此后78年间，针对两参数同阶增长的情形，其下界指数底数始终未能获得改进。
马杰教授团队的工作打破了这一长期停滞。他们创造性地构建了“随机球面图”模型，将图的顶点对应为高维球面上的随机点，并根据其内积是否低于某个阈值来决定边是红色还是蓝色。该模型的关键优势在于天然引入了几何依赖性：在随机球面图中，三个顶点形成红色三角形的概率严格小于 p^3，而蓝色三角形的概率则严格大于 (1-p)^3，这与经典埃尔德什-雷尼随机图模型（边独立着色）形成了本质区别。团队通过精密的高维几何与概率分析，发现当球的维度 k 与参数 l 满足平方关系 k 约等于 l^2 时，可以找到一个介于 p_C 与 1/2 之间的红色边概率 p，使得红团 K_l 和蓝团 K_{Cl} 的概率同时被压制。最终，通过标准概率方法，他们证明了存在不含单色 K_l 或 K_{Cl} 的 n 阶完全图，其中 n = (M_C + epsilon)^l，而 M_C = p_C^{-1/2} 正是埃尔德什下界中的底数。这意味着新的下界底数在 M_C 基础上获得了一个与 C 相关的常数增量 epsilon(C) > 0，实现了指数层面的实质性推进。
本论文通讯作者马杰教授，系中国科学技术大学数学科学学院讲席教授、博士生导师。其于2016年获得国家优秀青年科学基金资助，2021年获得国家杰出青年科学基金资助。目前担任《组合理论杂志B辑》（Journal of Combinatorial Theory, Series B）与《组合数学》（Combinatorica）编委，并任《SIAM离散数学杂志》副主编。第三作者谢晟捷同学，系中国科学技术大学数学科学学院三年级博士研究生，本科毕业于中国科学技术大学少年班学院，师从马杰教授，并已在《组合理论杂志B辑》等权威期刊发表学术论文。
上述工作得到国家重点研发计划（2023YFA1010201）、国家自然科学基金（12125106）及量子科学与技术创新重大项目（2021ZD0302902）的资助。
论文链接：https://doi.org/10.1007/s00222-026-01421-9
（数学科学学院、科研部）
本文链接：http://knowith.com/news-3-5770.html我校组合数学团队实现拉姆齐数下界的指数级改进
声明：本网页内容由互联网博主自发贡献，不代表本站观点，本站不承担任何法律责任。天上不会到馅饼，请大家谨防诈骗！若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。
