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 的两个割 S(A,B),S(C,D)S(A,B), S(C,D)(即第4步中最小交集、最大距离的那些对)。把第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} 块。

一个斯特林近似的计算(对 m=4km=4k、令 kk 取遍素数幂,并利用素数定理保证素数幂不至于太稀疏)表明,当 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 是 Rd\mathbb{R}^d 中一个真正的有界子集,其直径等于第4步中计算出的最大距离,这就对所有足够大的 dd 直接反驳了博苏克猜想。

本步骤用到的知识