MathLabs

解法:格拉德科夫–帕克–齐明给出的上下铺猜想显式反例(2024年)

第 3/8 步:障碍:没有任何图小零件能精确复制一条超边
通俗地说

接下来显而易见的做法是,试着把霍勒姆超图中每条三角形超边替换成一小簇普通的边——一个“小零件”(gadget)——使其在普通键渗流下的行为与一条超边完全一致:要么把三个连接点全部连通,要么一个都不连通,并且以恰当的概率发生,绝不会只连通其中两个。

但结果表明这在原理上是不可能的。普通的边是一条一条地失效或存活的,因此任何小零件都必然存在某些中间状态,使得三个连接点中恰好两个被连通,而第三个被切断——这是真正的超边(要么全连,要么全不连)永远不会产生的结果。无论小零件的设计多么巧妙,都无法彻底堵住这个漏洞。

∄ graph gadget exactly simulating a single 3-hyperedge under bond percolation\nexists \ \text{graph gadget exactly simulating a single 3-hyperedge under bond percolation}
详细分析

在维尔曼与齐夫(Wierman and Ziff,2011年)提出的WZ超图渗流模型中,一条超边 e={a,b,c}e = \{a,b,c\} 会解析为五种结果之一,各自带有自己的概率:三者全部连通(pabcp_{abc})、无一连通(pa∣b∣cp_{a|b|c})、只有 bb 与 cc 连通而 aa 被切断(pa∣bcp_{a|bc}),或 aa 恰好与 b,cb, c 之一连通而另一个被切断(pab∣cp_{ab|c} 或 pac∣bp_{ac|b})。在普通超图渗流下,一条真正的 33-一致超边只要 aa 是该超边的横截顶点,就总有 pa∣bc=0p_{a|bc} = 0(横截顶点要么与另外两个都连通,要么都不连通,绝不会只连通其中一个)。

格拉德科夫与齐明(2024年,在 Gladkov, Pak & Zimin 2024年论文中引用为 GZ24,定理1.5)证明了:这种精确的结果分布——特别是 pa∣bc=0p_{a|bc} = 0 与另外四个概率精确匹配真实超边的情形——无论小零件内部的边及其各自的保留概率如何选取,都不可能被任何有限的图小零件在普通键渗流下精确复现。直观地说:普通的边是一条一条独立失效的,因此在任何小零件内部,总会存在某种边失效的序列,最终恰好切断 a,b,ca, b, c 三者中的一个而让另外两个保持连通,从而给出 pa∣bc>0p_{a|bc} > 0——这一点完全无法避免。

这正是霍勒姆的超图反例尽管令人瞩目,却无法通过朴素替换立即转化为图反例的原因:pa∣bcp_{a|bc} 上的这一偏差意味着任何这样的替换都会引入少量恰恰是真正超边所禁止的“错误类型”连通事件。下一步将说明这一障碍是可以被绕过的,而不是被彻底消除的。

本步骤用到的知识
常见错误. 似乎只要在小零件中使用越来越多的边,或把概率调得越来越精细,最终就能在极限下把 pa∣bcp_{a|bc} 压到恰好为零;但格拉德科夫与齐明的定理彻底排除了这种可能——没有任何有限的图小零件能精确达到 pa∣bc=0p_{a|bc} = 0,因此这种偏差无论多小,原则上都无法避免,只能加以控制,而不能彻底消除。