二段ベッド予想の反例（7,222点で破れた不等式）

反例を示すには、グラフを1つ作り、ある$p$で不等式の向きが逆だと証明すればよい。3人の証明は2段構えである。まず「三角形が不完全でも、ある条件を満たせば逆転は残る」という補題を示し、次にその条件を満たす部品を作る。ここでは筋を追い、細かい場合分けは論文に譲る。

三角形の3点を、柱のある点$a$と、残りの$b,c$とする。三角形を何かのグラフに置き換えると、$a,b,c$の分かれ方は5通りになる。全部つながるのが$p_{abc}$、どれもつながらないのが$p_{a|b|c}$、$a$だけ離れて$b$と$c$がつながるのが$p_{a|bc}$、片方だけ$a$とつながるのが$p_{ab|c}$と$p_{ac|b}$で、この2つは等しいとする。完全な三角形なら$p_{abc}$と$p_{a|b|c}$だけが残る。

6つの三角形は、道$u_1\to u_3\to u_6\to u_5\to u_4\to u_8\to u_{10}$に沿って順に並ぶ。この道は柱のある点を通らない。

1. 鍵になるのは次の$\Delta$である。$a$と$b$、$a$と$c$がどれだけ一緒につながりやすいかを測る量で、普通のグラフではハリス＝クライトマンの不等式から$\Delta \ge 0$になる

   $$\begin{array}{rl}\Delta =& p_{abc}{p}_{a|b|c}\\ & -p_{ab|c}{p}_{ac|b}\end{array}$$

2. 補題の条件は、$b$と$c$が$a$抜きでつながる確率が$\Delta$の400分の1以下であることだ

   $$400p_{a|bc}\le \Delta$$

手順3から8の筋は、入れ替えられる組があればその先の三角形を上下に入れ替えて差を消し、消えずに残る場合をホロムの64通りと手順2の条件で見積もる、というものだ。

3. 1つの三角形の上下の状態の組は25通りある。$a|bc$を含まない16通りのうち、$(abc,a|b|c)$と$(ab|c,ac|b)$、それぞれの上下を逆にした組を除く12通りを「入れ替えられる組」と呼ぶ

   $$16-4=12$$

4. 入れ替えられる組が1つでもあれば、道に沿って最初のものを選び、そこから先の三角形をすべて上下入れ替える（組の種類によっては、その三角形も含める）。同じ段につながる場合と違う段につながる場合が1対1に対応し、確率も変わらないので、この場合に絞った確率$P_1$では差が消える

   $$\begin{array}{rl}& P_1[u_1\leftrightarrow u_{10}]\\ & =P_1[u_1\leftrightarrow u_{10}^{\prime }]\end{array}$$

5. 組$(ab|c,ac|b)$は、$(abc,a|b|c)$に読み替えると同じように入れ替えられる。確率が釣り合わないので、逆向きの読み替えには確率$\kappa$をかける。これで差はまた消え、$(abc,a|b|c)$の組には重み$\Delta$だけが残る

   $$\begin{array}{rl}& \kappa =\frac{p_{ab|c}{p}_{ac|b}}{p_{abc}{p}_{a|b|c}}\\ & p_{abc}{p}_{a|b|c}(1-\kappa )=\Delta \end{array}$$

6. 差が残るのは、すべての三角形が「片方の段で全部つながり、もう片方で何もつながらない」か、$a|bc$を含むときだけである。前者がそろう事象を$A$とすると、ホロムの模型そのものになる

   $$\begin{array}{rl}& P[u_1\leftrightarrow u_{10}\mid A]\\ & -P[u_1\leftrightarrow u_{10}^{\prime }\mid A]\\ & =\frac{12}{64}-\frac{13}{64}=-\frac{1}{64}\end{array}$$

7. $a|bc$の混ざる割合を押さえる。差が残る場合に絞ると、条件から三角形1つあたり$1/401$以下になるので、6つでは次のとおり

   $$\begin{array}{rl}P(A)& \ge (1-\frac{1}{401}{)}^6\\ & \ge 1-\frac{6}{401}>\frac{64}{65}\end{array}$$

8. 合わせると差は負になる。$A$の外では差は高々1だから、絞った場合の差は次のように押さえられる

   $$\begin{array}{rl}& P[u_1\leftrightarrow u_{10}]\\ & -P[u_1\leftrightarrow u_{10}^{\prime }]\\ & <\frac{1}{65}-\frac{64}{65}\cdot \frac{1}{64}=0\end{array}$$

手順4と5の場合の差は0なので、全体の差も負になる。これで補題が言えた。あとは条件を満たす部品を作ればよい。3人が選んだのは扇形のグラフ$G_n$である。点$a$と道$v_1,\dots ,v_n$を用意し、$a$をすべての$v_k$と結ぶ。点は$n+1$個、辺は$2n-1$本で、$b=v_1$、$c=v_n$とし、どの辺も確率1/2で残す。

9. $b$と$c$が$a$抜きでつながるのは、道の$n-1$本がすべて残り、$a$から出る$n$本がすべて消えるときだけである

   $$p_{a|bc}=2^{-(2n-1)}$$

10. 漸化式を解くと、$a$と$c$がつながる確率は$\frac{2}{3}(1-4^{-n})$になり、3点がつながる確率は次のとおりである

    $$\begin{array}{rl}{p}_{abc}& =\frac{4}{9}(1-4^{-n})\\ & +\frac{n}{3}{2}^{-(2n-1)}\end{array}$$

11. $\Delta$に代入すると、$n$がかかるのは$p_{abc}$の第2項だけで、ここが効く

    $$\Delta \ge (\frac{n}{3}-1)2^{-(2n-1)}$$

12. 3人は$n/3-1\ge 400$を満たすように、$n=3\cdot 401+1=1204$と置いた。三角形を扇に替えると、元の10点に内側の点が1,202個ずつ加わる

    $$\begin{array}{rl}|V|& =10+6\cdot 1202\\ & =7222\\ |E|& =6\cdot 2407\\ & =14442\end{array}$$

できたグラフは平面グラフで、柱は$u_2,u_7,u_9$の3本のままだ。¹柱が3本というのは、予想が破れる最小の本数でもある。

完全な証明は論文にあり、3人は補題の場合分けを計算機でも確かめて、コードを公開している。ただ、証明そのものは計算機に頼らない。ホロムの64通りは手で数えられる大きさで、残りは式の評価だけで済むからだ。

なお、柱も確率で残す版の予想も同じ考え方で破れ、差は柱3本の反例よりさらに小さい。『PNAS』の版では、柱がほぼ確実に立つように部品を増やし、点と辺がそれぞれ100万未満のグラフにした。パクのブログにある7,523点と$10^{-6500}$は、この版を扱ったarXivの第1版に沿った値である。Quanta Magazineはこの$10^{-6500}$を7,222点のグラフの差として書いているが、柱3本を固定した論文の評価は「$10^{-4331}$より小さい」である。