解法: グラドコフ=パク=ジミンによる二段ベッド予想の明示的反例(2024年)

ハイパーグラフは、ハイパーエッジが二頂点だけでなく任意の個数の頂点を含むことを許すことでグラフを一般化したものである。$3$-一様ハイパーグラフとは、すべてのハイパーエッジのサイズがちょうど $3$ であるものをいう。ローレンス・ハロム(2024年)は代替的な二段ベッドハイパーグラフ浸透モデルを研究した。そこでは下段のハイパーグラフ $H$ の各ハイパーエッジ $e$ は、それが保持されて上段の対応するコピー $e'$ が削除されるか、あるいはその逆かのいずれかとなり、それぞれ確率 $\tfrac12$ で、ハイパーエッジ間で独立に決まる——これは通常の二段ベッド浸透の自然なハイパーグラフ版である。

ハロムは、$10$個の頂点と$6$個のハイパーエッジを持つ具体的な$3$-一様ハイパーグラフ $H$ を、横断集合 $T = \{u_2, u_7, u_9\}$ とともに示し、$\Pr^{\text{alt}}[u_1 \leftrightarrow u_{10}'] = \tfrac{13}{64}$ である一方 $\Pr^{\text{alt}}[u_1 \leftrightarrow u_{10}] = \tfrac{12}{64}$ であることを正確に計算した——これはハイパーグラフに対する二段ベッド不等式の違反であり、その正確な分数は、六つのハイパーエッジが解決し得る等確率な $2^6 = 64$ 通りを直接列挙して確認できるほど小さい(Gladkov, Pak & Zimin 2024年、補題3.1、Hollom 2024年を引用)。

$3$要素のハイパーエッジを持つハイパーグラフ浸透は文字通りの意味では通常のグラフ上のボンド浸透ではないため、ハロムの結果は二段ベッド予想の自然な一般化に対する反例であって、予想そのものに対する反例ではない。しかしそれは、複数の$3$方向への分岐が相互作用する頂点に集中する不均衡という、この証明の残りの部分が通常のグラフへ適応させる、まさにその正確な組合せ論的な仕組みを浮かび上がらせている。