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

第 5/8 步：构造图小零件

G_n

:一条长路径扮演超边的角色

上一步下一步

通俗地说

格拉德科夫、帕克与齐明实际使用的小零件出人意料地简单: 这里 $p$ 是这个带权小零件中关闭边的参数(当 $p=1/2$ 时就是普通键渗流)。一条由 $n$ 条边组成的单一长路径,把顶点 $a$ 连接到一条链 $v_1, v_2, \dots, v_n$ ,再加上一条从 $a$ 直接通向远端 $v_n$ 的边。记 $b := v_1$ 、 $c := v_n$ ;随着 $n$ 增大,通过整条链绕行成为 $a$ 到达 $c$ 极其不可靠的方式,因此几乎所有时候要么由那条直连边负责连通,要么根本不连通——这正是超边所需要的“全有或全无”行为,只留下一个趋于零的小概率会出现图小零件无法完全避免的那种“错误”的部分连通。

通过一个递推关系式做一个简短的计算,就能确定 $a$ 与 $v_n$ 最终经由这个小零件连通的精确概率,并表明当 $n$ 足够大时,WZ 模型的全部五个概率都能满足稳健超边引理所要求的不等式。

\Pr_p(a \leftrightarrow v_n) = \frac{1 - p^{2n}}{1+p} \quad \text{on the path gadget } G_n

详细分析

对 $n \ge 3$ 与 $0 < p < 1$ ,在 $n+1$ 个顶点上定义带权图 $G_n$ :一条由 $n$ 条边组成的路径 $a = v_0, v_1, \dots, v_n$ ,再加上一条直接连接 $a$ 与 $v_n$ 的额外边;记 $b := v_1$ 、 $c := v_n$ 为两个“外部”连接点(Gladkov, Pak & Zimin 2024年,引理4.1)。由于 $G_n$ 是一个简单的带权图,普通键渗流可以直接作用于它,从而绕开了第3步的不可能性——它并不试图成为精确的超边,而只是在 $n$ 足够大时成为一个近似的超边。

一个简短的递推计算(2024年,第5节,引理5.1)表明,对包含直连边的完整小零件,若 $p$ 是边被关闭的参数,则 $\Pr_p(a \leftrightarrow v_n) = \tfrac{1 - p^{2n}}{1+p}$ ,当 $n$ 增大时它以指数速度趋近于 $\tfrac{1}{1+p}$ ;结合对 $G_n$ 其余 WZ 模型概率(把 $p_{abc}, p_{a|bc}, p_{ab|c}, p_{ac|b}, p_{a|b|c}$ 与 $p$ 及 $n$ 联系起来)的进一步精确计算,作者们直接验证了:在 $p = \tfrac12$ 时,一旦 $n \ge 3 \cdot 401 + 1 = 1204$ ,稳健超边引理所需的不等式 $400\, p_{a|bc} \le p_{abc}\, p_{a|b|c} - p_{ab|c}^2$ 就成立。

在这个具体取值 $n = 1204$ 下,小零件 $G_n$ 拥有 $1205$ 个顶点与 $2407$ 条边,是平面的,并且恰好满足上一步稳健超边引理所要求的条件。只需要这一个小零件的六份独立副本,就足以替换霍勒姆超图的六条超边,下一步将把它们组装成最终的反例。

本步骤用到的知识

图、度与路径事件与概率