走进科学
90年后，我们得出拉姆齐数R(n)的更精确上界
昨天，在剑桥大学有一场关于拉姆齐理论的讲座。很多人事先就听说，有很大的进展。所以菲尔兹奖得主陶哲轩和高尔斯同时到场旁听。
主讲人是剑桥的Julian Sahasrabudhe，研究合著者包括Marcelo Campos，Simon Griffiths和Rob Morris。
高尔斯今天在推特上评价说，上一次在剑桥听到这么精彩的讲座，还是安德鲁·怀尔斯(证明费马大定理)那次。陶哲轩则称，自己一直在考虑这个问题，但是没想到有如此精妙的解决方案。
拉姆齐理论(Ramsey's theorem)有一个特别有名的具体例子：随意找6个人，其中存在3个人互相认识或存在3个人彼此都不认识，这两种情况必居其一。
一般情况借助图论的语言则是说，对于顶点数目足够多的完全图(就是任意两个顶点之间存在一条边)，用红蓝两种颜色随意给边染色，则其中存在蓝色n阶完全子图或存在红色m阶子图，这两种情况必居其一时，原图的顶点数最少是多少？
一般这个数字用R(n，m)表示。
著名数学家保罗·爱多士曾经开玩笑说：“如果外星人入侵，要求人类计算出R(5，5)，否则就消灭人类。那我们可以集全球之力，给他们答案。如果外星人要求计算R(6，6)，那我们还是直接和外星人拼命好了。”
其实R(6，6)本身并不大，正是爱多士与合作者塞克尔斯计算出R(k，k)有个上界4^k。大家不妨思考一下，为何上限不超过4^6，我们却不能通过暴力穷举来确定，而要选择血拼外星人呢？
系统地求解拉姆齐数R(n，m)，所有组合领域内的相关学者都试图解决这一问题，我认为它可以说是极值组合学中的前二或前三的开放问题之一，或者就是排名第一的问题之一。
但90年过去，我们对此未能再改进分毫。这里有特殊的说法，给R(k，k)开k次方，我们想知道随着k增长，它的上确界是否可以小于4，甚至是否存在极限。否则，其实还是有人给出更小的上界的。
直到昨天，我们知道存在正数ε(=1/2^7)，R(k，k) ＜ (4 − ε)^k。
论文：https://arxiv.org/pdf/2303.09521v1.pdf
@1周 ago
不是存在正整数ε
是正 常 数
@1周 ago
没看懂
@1周 ago
剑桥大学近日举行了一场充满乐趣和学术价值的希腊式决斗，由两位数学大师陶哲轩和高尔斯参与。这场比赛并不是普通的摔跤比赛，而是充满了古典雅致和学术意义的对决。
在比赛开始前，两位数学大师浑身涂抹橄榄油，配备着古希腊的服饰，进入湖心亭的比赛场地。英国体育协会书记和英国伦敦小学全体三年级学生都出席了比赛。
陶哲轩和高尔斯两位数学大师使用了古代摔跤的格斗技法，展开了一场激烈的角逐。他们的动作轻盈，技术高超，将古典摔跤的精髓发挥到了极致。
此次比赛的目的是用武道的巅峰对决启发数学界拉姆齐理论的进一步研究。陶哲轩和高尔斯两位数学大师的比赛不仅充满了乐趣，更为数学界提供了一种新的思路和方法。
比赛结束后，两位数学大师互相致意，向来宾和观众们致谢。此次比赛展示了数学家们的非凡才华和富有创意的思维，向世界展示了数学界的多样性和魅力。
这场比赛既充满了幽默和趣味，也启发了学术界的进一步研究，展现出了数学家们的多才多艺和不拘一格的思维方式。相信这场比赛将为数学界带来更多的启示和新思路。
@1周 ago
所以说目前的成果是缩小了上界，但不多。
@1周 ago
因为计算量太大。
比如R(6,6)，上界是4^6=4096。
简单来说，只要作出4096个点，然后各点之间两两作线段，就能满足Ramsey条件。——但这题问的是“最少几个点”。
所以就要从4096减下去，比如4095（穷举法肯定只能一个个来嘛）。
那么，4095个点，一共有几条线段？答案是C(4095,2)=8,382,465。
这八百万条线段，分别涂成红蓝色，一共有多少种涂法？（当然这里可以用对称性简化。）
虽然，只要找出“4095的某一种涂法满足Ramsey条件”，就可以开始计算下一种情况（4094），但别忘了，题目问的是“至少”。
——也即，我们迟早必须遍历某个确定点数的每一种可能性，得出“是的，该情况下的所有涂法均无法满足Ramsey条件”这一结论，才能说“我们找到最小值了！”（+1就行）。
就结果看，就算从宇宙大爆炸开始计算4095，调动人类现有的全部算力，一直算到今天为止，恐怕连4000都算不到。
@1周 ago
此外，一般而言，数学家们不仅要算出某几个特定的解（数值解），还是要算出Ramsey问题的通项公式（解析解，如果它存在的话）。
所以穷举法吃力不讨好，哼哧哼哧算半天，大伙搞不好已经用夹逼原理给通项整出来了。
额外说一句，其实组合数学的内容（Ramsey问题属于这个分支），很大部分都仅限理论推演，人类目前的科学水平暂时还找不到它们的用途。
比如这个Ramsey问题，原理特别简单（容斥原理，中学内容），构造特别复杂，是那种“望山跑死马”的计算量，而且还不知道“到底什么东西会有这么复杂的构造”。
但是吧，就像算量子场必须要泛函分析，很难说会不会从组合数学发展出一支新的物理分支。
（所以你也不能说这玩意肯定没用，傅里叶1807年搓出傅里叶变换，1895年才有了试验性的电磁波通讯设备。）
@1周 ago
假装看懂了
@1周 ago
很久以前就知道一个说法，Ramsey理论用最常见的比喻来解释，那就是“林子大了什么鸟都有”（指要么必定存在n个鸟互相认识，要么必定存在m个鸟互相不认识）
另外大名鼎鼎的 Erdős 被译成了 爱多士……其实百科用的都是 埃尔德什 这个译名（[ɛrdøːʃ]）
@1周 ago
没明白，“随意找6个人”没有限定的吗
比方说10个人里有1对当地有名的夫妻，4个路人，4个名人
夫妻互相认识，认识4个名人，不认识其他人
每个路人都认识4个名人，但不认识其他路人，还认识当地有名的夫妻
4个名人之间互相认识，但不认识其他人
你选到夫妻和2个路人，2个名人
互不相识的只有2路人，第3人无论选谁路人都认识
互相认识的只有名人和夫妻之间，第3人无论选谁都不会互相认识
没有3个互不相识的人，也没有3个互相认识的人