@ 2022.05.02 , 20:47

阈值猜想 这6页论文是今年第一季度数学领域里最重要的成果

考虑若干个数学意义上的,我们给每个点标号。就像是中学时代为三角形的顶点编号ABC一样,只不过这里为了叙述方便,我们使用数字123456……

现在,我们挑出两个点,如1和点2,然后投掷一枚硬币:如果投出了字,则在点1和点2之间连上一条线;否则,就不动它们。然后,我们再对点1和点3,点2和点3,点1和点4,……重复上面的过程。

亦即,每两个点,它们之间有50%的几率存在一条连线。这些点和线构成的图,就是一个随机图。这里生成线的几率是50%,但显然,我们也可以50%换成任意的几率p。

随机图既是图论里的理论研究对象,也是和大数据、复杂系统相关的应用数学领域。

比如说,把一个城市里的居民看做是一个个的点。当城市居民足够多的时候,不妨合理假设每两个居民相遇的几率都是固定的,此时如果某个居民携带某种空气媒介传播的病毒,则所有和他密接的人员,就相当于从他(代表他的点)和其他人之间生成一条连线。这就构成了某种传染病溯源的随机图。

实际上,我们可以通过计算知道,当生成概率p足够大的时候,图就会很大概率出现某些结构。如成为树、欧拉图、汉密尔顿图。但针对每个结构,p其实并不好算。

2006年,数学家Jeff Kahn 和 Gil Kalai 提出了一个猜想,他们发现可以用相对简单的方法估算以一定几率呈现特定结构时的p值。这就是Kahn-Kalai猜想,它解释了随机系统中的某种内在规律,是随机图理论中的核心问题之一。

比如说,对于N个点图,可以借助复杂计算得知,若生成概率小于log(N)/N,则图里不大可能出现汉密尔顿圈。但如果应用Kahn-Kalai猜想,则我们可以直接知道,那个阈值概率必定介于1/N和log(N)/N之间——虽然有失准确,但计算简单。

普遍性使该猜想显得如此令人难以置信。一方面,它会立即简化组合学方面的研究。另一方面,大量看似无关的问题,都可以借助这一猜想来回答。

当然,意料之中的,猜想很难。过去15年里,没有人想到它能够被证明,而且证明过程还很“简单”。


今年3月最后一天上传至arxiv的6页论文A Proof of the Kahn-Kalai Conjecture 是2022年第一季度最重要的数学成果。

之前没人想到随机图领域里的中心问题之一的 Kahn-Kalai Conjecture 能够被证明,而且能够有如此简单的证明(巧妙应用了覆盖理论,工具基本都是现成的。有点像当年布朗基用现成的工具证明了比伯巴赫猜想。唯一区别在于,证明比伯巴赫猜想是单叶几何函数论这一数学分支存在的意义,所以完成证明基本相当于单叶几何函数论的告别演出。而Kahn-Kalai Conjecture,也叫随机图阈值猜想,更像是拉开复杂系统里随机结构研究的大幕。)

特别是在组合和图论领域里,一套行之有效的理论工具,往往不在于理论多么高深,而是要找对切入点,就像是钥匙对应锁孔一样。而一旦开了锁,那后续的一批成果就手到擒来了。目测起码有两位数的艰难结果随着这一证明瓜熟蒂落。

看采访,两位作者一开始自己都没有抱期望,本来就是想零敲碎打写一篇多少有进展的论文,结果赶论文一个不眠之夜竟然直接通关。两位作者一位还是在读博士,另一位也不过是斯坦福的助教,但有不小概率预定8年后的菲尔兹奖了。看照片都是亚洲人,一位看名字Huy Tuan Pham,是越南裔。另一位Jinyoung Park不知道是不是华人或韩国二代移民。

支付宝打赏 [x]
您的大名: 打赏金额:
赞一个 (19)