诸平
困扰了科学家将近一个世纪的数学难题,两位数学家终于解决了 精选
2024-4-14 20:59
阅读:4315

困扰了科学家将近一个世纪的数学难题,两位数学家终于解决了

诸平

Pencils-Math-777x518.jpg

Fig. 1 Jacques Verstraete and Sam Mattheus, researchers at the University of California, San Diego, have made a significant breakthrough in Ramsey theory by solving the r(4,t) problem, a challenge that has eluded mathematicians for decades.

Ramsey-Numbers-Graph.jpg

Fig. 2 Ramsey problems, such as r(4,5) are simple to state, but as shown in this graph, the possible solutions are nearly endless, making them very difficult to solve. Credit: Jacques Verstraete

FanRon2.gif

Fig. 3 Fan Chung and Ron Graham. Erdös on graphs: his legacy of unsolved problems. A. K. Peters, Ltd, January 1998. pp. 142. Published online by Cambridge University Press:  01 August 2016 

据美国加州大学圣地亚哥分校(University of California - San Diego简称UCSD, San Diego, La Jolla, CA, USA2024411日提供的消息,加州大学圣地亚哥分校(UCSD)的数学家与比利时布鲁塞尔自由大学(Vrije Universiteit Brussel, Brussels, Belgium) 的数学家合作,发现了拉姆齐数(Ramsey numbers)背后的秘密。这个数学难题困扰了科学家将近一个世纪,两位数学家终于解决了它(This Math Problem Stumped Scientists for Almost a Century – Two Mathematicians Have Finally Solved It)。

我们都有过这样的经历:盯着数学题看,题目似乎不可能解决。如果找到一个问题的解决方案需要花费将近一个世纪的时间呢?对于涉猎拉姆齐理论(Ramsey theory)的数学家来说,情况就是如此。事实上,自20世纪30年代以来,在解决拉姆齐问题(Ramsey problems)方面几乎没有取得任何进展。

现在,UCSD的研究人员雅克·佛斯特拉(Jacques Verstraete)和萨姆·马特乌斯(Sam Mattheus)已经找到了r(4, t)的答案,这个长期存在的拉姆齐问题困扰了数学界几十年。

拉姆齐问题到底是什么?(What was Ramsey’s problem, anyway?

用数学术语来说,图就是一系列的点和点之间的线。拉姆齐理论认为,如果图足够大,你一定能在图中找到某种顺序,要么是一组点之间没有线,要么是一组点之间有所有可能的线,这些集合被称为“团”(“cliques”)。它被写成r(s, t),其中s是有直线的点,t是没有直线的点。

对于我们这些不研究图论的人来说,最著名的拉姆齐问题r(3, 3)有时被称为关于“朋友和陌生人的定理”(“the theorem on friends and strangers”),并通过一个聚会来解释:在一个6人的小组中,你会发现至少有3个人彼此都认识,或者3个人彼此都不认识。故r(3, 3)的答案是6

雅克·佛斯特拉说:“这是一个自然的事实,一个绝对的真理。不管情况如何,也不管你选择哪6个人,你会发现3个人都彼此认识,或者3个人都互不认识。你也许能找到更多,但你可以保证至少有3个人在一个或另一个团内。”

数学家发现r(3, 3) = 6之后发生了什么?自然,他们想知道r(4, 4) r(5, 5)r(4, t)其中不连接的点的数量是可变的。r(4, 4)的解是18,它是用保罗·埃德斯(Paul Erdös)和乔治·塞凯赖什(George Szekeres)在20世纪30年代创造的一个定理证明的。目前,r(5, 5)仍然是未知的。

好的问题会反击(A good problem fights back

为什么这么简单的陈述就这么难解决?事实证明,它比看起来要复杂得多。假设你知道r(5, 5)的解在40-50之间。如果你从45个点开始,就会有超过10234个图形需要考虑!

雅克·佛斯特拉解释说:“因为这些数字是出了名的难以找到,数学家们寻找的是估计。这就是萨姆·马特乌斯和我在最近的工作中所取得的成就。我们如何找到拉姆齐数的最佳估计,而不是确切的答案? ”相关研究结果于202435日已经在《数学年鉴》(Annals of Mathematics)杂志网站发表——Sam Mattheus, Jacques Verstraete. The asymptotics of r(4,t). Annals of Mathematics, 2024,198(2): 819-941. DOI: 10.4007/annals.2024.199.2.8. Published online: 5 March 2024. https://annals.math.princeton.edu/2024/199-2/p08

数学专业的学生很早就学会了拉姆齐问题,所以r(4, t)在雅克·佛斯特拉的大部分职业生涯中一直是他关注的对象。事实上,他第一次看到这个问题是在《埃德斯在图上的问题和传奇》(Erdös on Graphs: His Legacy of Unsolved Problems)一书中,此书由加州大学圣地亚哥分校的两位教授,金芳蓉(英文名:Fan Chung Graham学术论文所用的英文名:Fan Chung)和已故的葛立恒(Ron Graham / Ronald Lewis Graham31 October 1935 - 6 July 2020 )合著的(Fig. 3)。这个问题是来自保罗·埃德斯的一个猜想,他们将为第一个能解决这个问题的人支付250美元($250)的奖金。

雅克·佛斯特拉说:“很多人都认为r(4, t)是一个90多年来一直存在的开放性问题。但这并不是我研究的重点。每个人都知道这很难,每个人都试图弄清楚,所以除非你有一个新的想法,否则你不可能取得任何进展。”

大约4年前,雅克·佛斯特拉和美国伊利诺斯大学芝加哥分校(University of Illinois-Chicago)的数学家杜茹瓦·穆巴里(Dhruv Mubayi)一起研究另一个拉姆齐问题。他们一起发现,伪随机图(pseudorandom graphs)可以推进这些老问题的现有知识。

1937年,保罗·埃德斯发现使用随机图可以给出拉姆齐问题很好的下界。雅克·佛斯特拉和杜茹瓦·穆巴里发现,从伪随机图中抽样通常比随机图给出更好的拉姆齐数边界。这些可能答案的上限和下限收紧了他们可以做出的估计范围。换句话说,他们越来越接近真相了。

2019年,令数学界高兴的是,雅克·佛斯特拉和杜茹瓦·穆巴里使用伪随机图来求解r(3, t)。然而,雅克·佛斯特拉努力构建一个可以帮助求解r(4, t)的伪随机图。

他开始涉足组合学(combinatorics)之外的不同数学领域,包括有限几何(finite geometry)、代数(algebra)和概率论(probability)。最终,他与萨姆·马特乌斯合作,萨姆·马特乌斯是他小组里的博士后学者,他具有有限几何方面的背景知识。

雅克·佛斯特拉说:“事实证明,我们需要的伪随机图可以在有限几何中找到。萨姆·马特乌斯是一个理想之人来帮助我们建立我们所需要的。”

一旦他们有了伪随机图,他们仍然需要解决一些数学问题。这花了将近一年的时间,但最终,他们意识到他们有了一个解决方案:r(4, t)接近于t的三次函数。如果你想要一个聚会,总是有4个人彼此都认识,或者t个人彼此都不认识,你需要大约t3人在场。这里需要说明,因为,记住,这是一个估计,而不是一个确切的答案。但是t3已非常接近确切的答案了。

这些发现目前正在接受《数学年鉴》(Annals of Mathematics)的审查。

雅克·佛斯特拉说:“我们确实花了好几年才解决这个问题。有很多次我们被困住了,想知道我们到底能不能解决这个问题。但是一个人不应该放弃,不管需要多长时间。”

雅克·佛斯特拉强调毅力的重要性,这也是他经常提醒学生的一点。“如果你发现这个问题很难,你被卡住了,那就意味着这是一个好问题。金芳蓉说,好的问题会反击。你不能指望它自己就会显露出来。

雅克·佛斯特拉知道这种顽强的决心会得到很好的回报:“我接到金芳蓉的电话,说她欠我250美元。”

上述介绍,仅供参考。欲了解更多信息,敬请注意浏览原文或者相关报道

Abstract

For integers s,t ≥ 2, the Ramsey number r(s, t) denotes the minimum n such that every n-vertex graph contains a clique of order s or an independent set of order t. In this paper we prove

r(4, t) = Ω{t3 / (log4 t)}$    as t →∞,

which determines r(4, t) up to a factor of order log2 t, and solves a  conjecture of Erdős.

360截图20240414202046640.jpg

转载本文请联系原作者获取授权,同时请注明本文来自诸平科学网博客。

链接地址:https://wap.sciencenet.cn/blog-212210-1429663.html?mobile=1

收藏

分享到:

当前推荐数:7
推荐到博客首页
网友评论0 条评论
确定删除指定的回复吗?
确定删除本博文吗?