解法: グラドコフ=パク=ジミンによる二段ベッド予想の明示的反例(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の反例が示すのは、これらのグラフ類の特定の構造を利用するのではなく純粋に一般的な組合せ論的恒等式のみに頼る証明戦略は、任意のグラフと任意の横断集合には拡張できないということだけである。
この明示的な反例はちょうど 個の横断頂点を用いており、著者らはこれが可能な最小の個数であると指摘する:この予想は である限りすでに成り立つことが知られているため、三が実際にこの現象が初めて可能になる閾値なのである。Gladkov, Pak & Zimin(2024年)の第6節はさらにこの反証を完全BBCと呼ばれる変種——横断集合 があらかじめ固定されるのではなく一様ランダムに選ばれるもの——へと拡張し、同じ定性的な破綻がそこでも持続することを示している。
二段ベッド予想が成り立つグラフ類・確率領域と、それが破綻し得るグラフ類・確率領域との正確な境界を見出し、その違いが何によって生じるのかを理解することは、論文の結びの remarks で論じられている予想の変種(異なる浸透モデル、1990年代にHäggströmによって証明されたランダムクラスター模型/イジング模型の類似物、そして無限グラフの場合)とともに、今や確率的組合せ論における活発な未解決問題である。