MathLabs

解法:卡恩与卡莱利用弗兰克尔–威尔逊定理反驳博苏克猜想

第 3/7 步:弗兰克尔–威尔逊交叉定理:所缺的代数工具
通俗地说

彼得·弗兰克尔与理查德·威尔逊于1981年证明了一个惊人精确的限制:一族大小相同的集合,如果禁止某一个特定的交集大小,它能有多大。只要排除一个"被禁止的重叠",这个族就会从天文数字般巨大骤降到可以用普通二项式系数控制的规模。他们的证明是组合数学中"线性代数方法"的一次早期胜利:把每个集合变成一个多项式,证明这些多项式必须线性无关,再从它们所在空间的维数读出可能存在多少个这样的多项式。

∣K∣≤2(n−1n/4−1)(Frankl–Wilson, 1981; n=4k, k prime power)|\mathcal K| \le 2\binom{n-1}{n/4-1} \qquad \text{(Frankl–Wilson, 1981; } n=4k,\ k \text{ prime power)}
详细分析

定理(弗兰克尔–威尔逊,1981)。设 kk 为素数幂,n=4kn = 4k。设 K\mathcal{K} 是 {1,…,n}\{1, \ldots, n\} 的一族 n/2n/2-子集,使得 K\mathcal{K} 中任意两个集合的交集都不恰好含 n/4n/4 个元素。那么 ∣K∣≤2(n−1n/4−1)|\mathcal K| \le 2\binom{n-1}{n/4-1}。

这个界最引人注目之处在于其形态:一个 nn 元集合的所有 n/2n/2-子集总数为 (nn/2)\binom{n}{n/2},这(相对于维数而言)比界 2(n−1n/4−1)2\binom{n-1}{n/4-1} 大出指数级——后者只计数了从一个略小的基础集合中取出、大小约为 n/4n/4 的子集。因此,禁止一个交集大小——听起来是极其温和的限制——却迫使这个族只能是所有可能集合中一个消失比例的部分,这个差距随着 n→∞n \to \infty 而无限增长。弗兰克尔与沃伊捷赫·罗德尔的一个密切相关的结果,回答了埃尔德什的一个问题,在不要求 k=n/4k=n/4 为素数幂的情况下,对任意能被四整除的 nn 给出了类似但更弱的界 ∣K∣≤(1.99)n|\mathcal K| \le (1.99)^n。

本步骤中的术语
线性代数方法(组合数学)
一种证明技巧,通过给每个成员关联一个多项式或向量,证明这些对象在某个向量空间中线性无关,从而得出该组合族的大小不超过该空间维数的上界。
本步骤用到的知识