解法：格拉德科夫–帕克–齐明给出的上下铺猜想显式反例(2024年)
于是,这个被相信了将近四十年的上下铺猜想,最终在一般情形下被证明是错误的——但这个反例是一个经过精心设计、专门构造出来的图,并非典型的图。事实上,2024年之前已经被验证过的每一种图形——树、车轮图、完全图、完全二部图,以及在 与 之间具有足够对称性的任何图——依然真正满足这个猜想,而且今后也将一直如此,因为那些更早的证明仍然完全成立。
一个诚实的总结不是“上下铺猜想毫无意义”,而是“上下铺猜想并不是关于所有图的定理”:它在“简单到同层连通总能取胜”的图与“复杂到足以容许这份证明所构造出的那种奇特失衡”的图之间,划出了一条真实存在、但至今仍未被充分理解的边界。
尽管在一般情形下已被反驳,上下铺不等式 对树(归于卡斯特林的原始1985年论证的直接推论,并由 Linusson 2011年针对单个横截顶点的情形明确证明)、两个横截顶点的情形(Leander 2018年,第6.3节)、车轮图(Leander 2009年)、完全图与完全二部图(van den Berg 2016年、2018年;Hutchcroft & Leander 2019年;Richterich 2022年)、关于 自同构对称的图(Richterich 2022年),以及——值得注意的是——对所有图在极限 下(Hollom, Nachmias & Klivans 2023年;Hollom 2024a年)仍然成立且已被证明。格拉德科夫、帕克与齐明的反例只表明:任何仅依赖纯粹一般组合恒等式、而不利用这些图类特定结构的证明策略,都无法推广到任意图和任意横截集合。
这个显式反例恰好使用了 个横截顶点,作者们指出这是可能的最小数目:该猜想在 时已被证明成立,因此三确实是这一现象首次成为可能的临界值。Gladkov, Pak & Zimin(2024年)论文第6节进一步把这一反驳扩展到一种称为完全 BBC的变体,其中横截集合 是均匀随机选取而非事先固定的,表明同样定性的失效在那里依然存在。
找出上下铺猜想成立与可能失效的图类及概率区间之间的精确边界——并理解是什么造成了这种差异——如今是概率组合数学中一个活跃的开放问题,与论文结语中讨论的该猜想的其他变体(不同的渗流模型、Häggström在1990年代证明的随机团簇/伊辛模型类比,以及无限图的情形)一道,共同构成了这一领域的前沿。