数学预印本理论阅读 1 分钟

随机网络在一个固定的密度上不再可着色

取一个图——由连线连接起来的点——和一盒颜色。用q种颜色进行的正常着色,就是给每个点涂上q种颜色之一,使两个相连的点永远不同色。连线少时,这很容易。连线多了,就变得不可能。

现在随机地构造这个图:n个点,每一对点以一个很小的概率独立地连线,使得每个点平均有d个邻居。随着d增大,随机图从“几乎必然可以用q种颜色着色”变成“几乎必然不可以”。转变究竟发生在哪里?对于从三种起的任意固定颜色数q,这个问题正是剑桥大学Gaia Carenini一篇新论文的主题。

一个可能摆动的开关

在参考文献所列的一篇1999年的论文中,Achlioptas和Friedgut证明了这一转变是尖锐的:对每个规模n,都存在一个临界平均度 d_q(n),略低于它时,图几乎必然可着色;略高于它时,几乎必然不可着色。转变发生的窗口缩小到零。

但这留下了一个漏洞。没有什么能阻止临界值本身随着图变大而振荡——对某一规模的图处在一个位置,对更大的图又稍稍挪到别处,始终稳定不下来。Achlioptas–Friedgut收敛猜想断言这种情况不会发生:对每个q,都存在唯一的常数 d_q,低于它,随机图可着色;高于它,则不可着色。

物理学家的预言

统计物理对其中发生的事情已有一幅图景。随着连线增加,有效着色会聚成一个个团簇(clusters):同一团簇内的着色彼此相似,而两个团簇在许多点上都不相同。接着,在一个称为凝聚的阶段,少数几个大团簇占据了全部着色中相当大的一部分——直到更晚的时候,着色的集合才变为空集。这种组织方式解释了为什么计数论证在阈值附近举步维艰。

对于颜色很多的情形,此前的工作已经把阈值框定在一个很窄的范围内:它大约介于 2q log q − log q − 2 log 2 与 2q log q − log q − 1 之间,随着q增大,间隙宽度为 2 log 2 − 1。但“窄”并不等于“固定”,而对于三种这样的少数颜色,问题仍未解决。

先攻克一个孪生问题

着色有一个孪生问题:可满足性,即为一组变量选择真或假的取值,使一串随机逻辑约束全部成立。在那里,人们同样知道存在尖锐阈值,却没有证明它会稳定下来。在论文引用的一份2026年的报告中,Carenini宣布证明了它确实会稳定下来,对三及以上的每一种约束长度都成立,方法是证明转变窗口非常窄。新论文把这一论证移植到了着色问题上。

冻结在一起的点对

证明通过一连串归约进行。一条一条地加入随机连线,令H为图不再可着色的时刻。如果H在不同的随机图之间变化不大——在约 n/(log n)² 条连线的窗口之内——那么阈值必然稳定下来。一个经典不等式把这一点转化为关于最后一个可着色图的问题:平均而言,它能经受住多少条新的随机连线?

关键概念在这里登场:冻结点对。当每一种有效着色都给两个点涂上相同的颜色时,这两个点就构成一个冻结点对。一条新连线恰好在连接这样一对点时才是致命的。单个点不可能被冻结在某一种特定颜色上,因为把颜色互相调换总能得到另一种有效着色;被强制的是两个点之间的关系。Carenini通过删除一条连线或整个点、观察重新出现的选择,追踪这些冻结类随连线增加而增长的过程。估计表明,最后一个可着色图撑不了多久,这足以把窗口收窄到能够证明该猜想的程度。

仍然未知的事

定理表明,对每个 q ≥ 3,阈值 d_q 都存在。它没有说明阈值在哪里:论文没有给出它的值,即使是三种颜色的情形也没有。这篇论文是一篇只有一位作者的预印本,尚未经过同行评审。文末有一段简短声明:其中没有任何数学论证是由大语言模型生成的。