MathLabs

解法: フランクル–ウィルソンの定理によるカーン=カライのボルスク予想の反証

ステップ 5/7: 構成とフランクル–ウィルソンを組み合わせる:少なくとも (1.2)d(1.2)^{\sqrt{d}} 個の部分が必要
ざっくり言うと

ここでステップ4のカットを、ステップ3のフランクル–ウィルソンの定理に直接当てはめる:ボルスクの意味での「真に小さい直径を持つ部分」とは、まさに、唯一の危険な交わりの大きさ ∣A∩C∣=k|A \cap C| = k を避けるカットの部分族のことであり、定理は、そのような部分族はどれも全体に比べてごく小さくなければならないと述べる。(巨大な)カットの総数を(はるかに小さい)最大の安全な部分族で割ると、必要な部分の数の下限が得られる——そしてその比は (1.2)d(1.2)^{\sqrt d} のように増大し、予想されていた d+1d+1 をはるかに上回ることが分かる。

f(d) ≥ 12(m2k)2(m−1k−1) > (1.2)d,d=(m2)−1f(d) \ \ge\ \frac{\tfrac12\binom{m}{2k}}{2\binom{m-1}{k-1}} \ >\ (1.2)^{\sqrt d}, \qquad d = \binom m2 - 1
詳しい解説

K\mathcal K の部分が真に小さい直径を持つのは、それが ∣A∩C∣=k|A \cap C| = k(ステップ4の最小交わり・最大距離のペア)であるような二つのカット S(A,B),S(C,D)S(A,B), S(C,D) を含まないとき、かつそのときに限る。ステップ3のフランクル–ウィルソンの定理を、サイズ n:=mn := m の台集合 VV と禁止された交わりの大きさ n/4=kn/4 = k に対して適用すると、そのような K\mathcal K の「安全な」部分族はどれも大きさが高々 2(m−1k−1)2\binom{m-1}{k-1} である。K\mathcal K 自身は 12(m2k)\tfrac12\binom{m}{2k} 個の要素を持つため、K\mathcal K をより小さい直径の部分に分割するには少なくとも 12(m2k)/2(m−1k−1)\tfrac12\binom{m}{2k} \big/ 2\binom{m-1}{k-1} 個の部分が必要である。

スターリング近似による計算(kk が素数冪を渡るように m=4km=4k に対して行われ、素数冪があまり疎でないことを保証するために素数定理を用いる)は、d=(m2)−1d = \binom{m}{2}-1 が十分大きくなると、この比が (1.203)d(1.203)^{\sqrt d} を超えることを示し、これは予想されていた d+1d+1 よりも指数的に大きい。K⊂{0,1}d\mathcal K \subset \{0,1\}^d は、ステップ4で計算された最大距離に等しい直径を持つ Rd\mathbb{R}^d の正真正銘の有界部分集合であるため、これは十分大きいすべての dd に対してボルスクの予想を直接反証する。

このステップで使う知識