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

对连通图 $G = (V, E)$ 与选定的横截顶点子集 $T \subseteq V$,上下铺图 $\overline{G}$ 由两个副本 $G$ 与 $G'$(第 $0$ 层与第 $1$ 层)以及对每个 $w \in T$ 连接 $w$ 与 $w'$ 的一条立柱边组成。在上下铺渗流中,$G$ 与 $G'$ 的每条边都独立地以概率 $p \in (0,1)$ 保留,而每根立柱始终保留。卡斯特林1985年提出的上下铺猜想(Gladkov, Pak & Zimin 2024年,猜想1.1,经 van den Berg & Kesten 2001年注5归于卡斯特林)断言:对所有这样的 $G$、$T$、$p$,以及任意一对顶点 $u, v \in V$,都有 $\Pr^{\text{bb}}_p[u \leftrightarrow v] \ge \Pr^{\text{bb}}_p[u \leftrightarrow v']$——连通到 $v$ 自身所在层的概率,至少不小于连通到 $v$ 在另一层副本的概率。

最常被引用的特殊情形取 $T = V$(每个顶点都有立柱),但格拉德科夫、帕克与齐明真正处理的,是横截集合 $T$ 为任意集合的一般性断言,他们的反例反驳的正是这个版本。这个猜想曾在若干特殊情形中得到验证——车轮图、完全图、完全二部图、存在交换 $u$ 与 $v$ 的自同构的图,以及横截顶点为一个或两个的情形——并且值得注意的是,在极限 $p \to 1$ 下也成立,但一个完全一般性的证明或反驳,在这个猜想提出后近四十年间始终困扰着概率论学者。

这份证明接下来的部分,将构造一个显式的图、一个横截集合以及一对顶点,使得该不等式在 $p = \tfrac12$ 处失效,从而在一般情形下反驳了这一猜想。