MathLabs

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

第 6/8 步:组装具有 7,2227{,}222 个顶点的显式平面反例
通俗地说

现在把所有部分组装起来:取霍勒姆的 1010 顶点超图,只要哪里有一条三角形超边,就把它剪掉,缝入上一步路径小零件的一份新副本,让小零件的 aa、bb、cc 与该超边的三个顶点对齐(横截顶点对应到 aa)。对全部六条超边都这样做,结果就得到一个单一的、完全普通的平面图——任何地方都不再有超边——完全由和任何教科书图一样的普通部件构成。

根据两步之前的稳健超边引理,这个图继承了当初让霍勒姆超图例子成立的那个反向不等式:只在三个横截顶点处安放立柱,其余各处都进行普通的概率为 12\tfrac12 的键渗流,跨层连通的概率确实高于同层连通——从而一劳永逸地确定了上下铺猜想是错误的。

∣V(G)∣=10+6⋅1202=7,222,∣E(G)∣=6⋅2407=14,442|V(G)| = 10 + 6 \cdot 1202 = 7{,}222, \qquad |E(G)| = 6 \cdot 2407 = 14{,}442
详细分析

取第2步中霍勒姆的超图 HH,对它的六条 33-一致超边 {a,b,c}\{a,b,c\} 中的每一条,都替换成第5步路径小零件 GnG_n(取 n=1204n = 1204)的一份新副本,把小零件的 aa 与该超边的横截顶点等同起来,把 b,cb, c 与另外两个顶点等同起来(Gladkov, Pak & Zimin 2024年,第4.2节)。所得到的图 GG 是平面图(因为 HH 本身画成平面图且 GnG_n 是平面图),拥有 ∣V(G)∣=10+6×1202=7,222|V(G)| = 10 + 6 \times 1202 = 7{,}222 个顶点与 ∣E(G)∣=6×2407=14,442|E(G)| = 6 \times 2407 = 14{,}442 条边,并保留了与霍勒姆超图相同的三个横截顶点 T={u2,u7,u9}T = \{u_2, u_7, u_9\}。

根据第5步已验证 GnG_n 的各概率满足稳健超边引理的不等式,再结合第4步的引理本身,GG 上普通的 12\tfrac12 键渗流满足 Pr⁡[u1↔u10]<Pr⁡[u1↔u10′]\Pr[u_1 \leftrightarrow u_{10}] < \Pr[u_1 \leftrightarrow u_{10}']——这正是 Gladkov, Pak & Zimin(2024年)的定理1.2:存在一个具有 7,2227{,}222 个顶点与 14,44214{,}442 条边的连通平面图、一个大小为 33 的横截集合,以及两个顶点 u,vu, v,使得 Pr⁡1/2bb[u↔v]<Pr⁡1/2bb[u↔v′]\Pr^{\text{bb}}_{1/2}[u \leftrightarrow v] < \Pr^{\text{bb}}_{1/2}[u \leftrightarrow v']——这是一个显式的、完全构造性的上下铺猜想反例。值得注意的是,这一论证是通过前面几步逐层建立起来的引理链、以解析方式确立这个不等式的,而不是靠对整个图上渗流结果的暴力计算机搜索(那样的搜索规模过于庞大,根本无法枚举)。

作者们指出,三个横截顶点在可证明的意义上是任何反例所需的最少数目(更少就不可能奏效,这是由横截顶点为一个或两个时该猜想已知成立所决定的——见最后一步),但总顶点数 7,2227{,}222 极不可能是最优的;更小的反例几乎肯定存在,只是这并非本构造的目标。

本步骤用到的知识