用户: Hbghlyj/Erdős–Ko–Rado 定理

1最大的相交族的基数

定义 1.1. 考虑集合 $N=\{1,\cdots ,N\}$. 称子集族 $\mathcal{F}$ 为相交族, 若 $\mathcal{F}$ 中任两个元素至少有一个公共元.

命题 1.2. 最大的相交族的基数为 $2^{n-1}$.

证明. 若 $A\in \mathcal{F}$, 那么其补集 $A^c=N\setminus A$ 与 $A$ 相交为空, 故不能出现在 $\mathcal{F}$ 里. 所以相交族最多可以有所有的子集数 $2^n$ 的一半那么多的元素, 即 $|\mathcal{F}|⩽2^{n-1}$.

另一方面, 考虑含有某个固定点的所有子集, 例如含有 1 的所有子集构成的族 ${\mathcal{F}}_1$, 则显然 $|{\mathcal{F}}_1|=2^{n-1}$, 问题就解决了.

$\square$

2最大的相交 $k$-集族的基数

定义 2.1. 相交族 $\mathcal{F}$ 之中, 每个子集有同样的基数, 比方说 $k$, 称这样的族为相交 $k$-集族.

相交 $k$-集族最大可能的基数是多少? 不妨设 $n⩾2k$, 否则任两个 $k$-子集必相交, 故无需证明. 用上面的思想, 取含固定点 (如 1) 的所有 $k$-子集当然可以得到满足条件的集族 ${\mathcal{F}}_1$. 显然 ${\mathcal{F}}_1$ 里的子集可以通过把 1 加到 $\{2,3,\cdots ,n\}$ 所有的 $(k-1)$-子集里得到, 因此 $|{\mathcal{F}}_1|=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. 还可以更优吗? 不──这就是 Erdős-Ko-Rado 定理.

定理 2.2. 当 $n⩾2k$, 一个 $n$-集合的相交 $k$-集族最大可能的基数是 $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

注 2.3. 1938 年,Paul Erdős,柯召和 Richard Rado 发现了这个定理, 但直到 23 年后才将之发表 [Erdős 1987]. 此后众多证明和变形纷至沓来, 但下面的由 Gyula Katona 给出的证明格外优雅.

证明.

证明的关键是一个乍看上去和我们的问题毫不相干的简单引理.

定义 2.4 (弧). 考虑被 $n$ 个点分成 $n$ 条边的圆周 $C$, 每条长为 $k$ 的弧包含 $k+1$ 个连续的点和它们之间的 $k$ 条边.

引理 2.5. 设 $n⩾2k$, 且设有 $t$ 条长为 $k$ 的互异的弧 $A_1,\cdots ,A_t$, 使得任两条弧之交非空, 则 $t⩽k$.

证明. 为证引理, 注意 $C$ 的每一点至多是某 1 条弧的端点. 事实上, 若 $A_i,A_j$ 有公共的端点 $v$, 则它们不得不向相反的方向延展 (因为它们是相异的). 但由 $n⩾2k$ 它们将不会有公共边. 固定 $A_1$, 由于每个 $A_i(i⩾2)$ 与 $A_1$ 有公共边,$A_i$ 的一个端点是 $A_1$ 的内点. 从上面看出这些端点各不相同, 而 $A_1$ 共有 $k-1$ 个内点, 所以 $A_1$ 以外只能有至多 $k-1$ 条弧, 加起来至多有 $k$ 条弧. 引理得证.

$\square$

现在继续证明 Erdős-Ko-Rado 定理. 令 $\mathcal{F}$ 是一个相交 $k$-集族, 考虑上述有 $n$ 个点,$n$ 条边的圆周 $C$. 取环排列 $\pi =(a_1,a_2,\cdots ,a_n)$, 将 $a_i$ 依顺时针写在 $C$ 的各边上. 对满足其 $k$ 个元素连续地出现在 $C$ 上的集合 $A\in \mathcal{F}$ 计数. 由于 $\mathcal{F}$ 是相交族, 引理告诉我们至多有 $k$ 个这样的集合. 这对所有的环排列都是如此, 又因为一共有 $(n-1)!$ 个环排列, 故以上的方式产生了至多 $k(n-1)!$ 个 $\mathcal{F}$ 中的集合. 其元素连续地出现在某个环排列上. 对固定的集合 $A\in \mathcal{F}$, 我们计数了多少次呢? 很容易: 如果 $A$ 的 $k$ 个元素是按照某种顺序连续出现的, 则 $A$ 出现在 $\pi$ 里. 而我们共有 $k!$ 种可能连续地书写 $A$, 以及 $(n-k)!$ 种方式将剩余的元素排序. 因此, 固定的集合 $A$ 恰好出现在 $k!(n-k)!$ 个环排列里面, 从而$$|\mathcal{F}|⩽\frac{k(n-1)!}{k!(n-k)!}=\frac{(n-1)!}{(k-1)!(n-1-(k-1))!}=\left(\begin{array}{l}n-1\\ k-1\end{array}\right)$$

$\square$

3参考文献

•	Martin Aigner, Günter M. Ziegler (1998). Proofs from THE BOOK. Springer.
•	Paul Erdős(1987), My joint work with Richard Rado, Surveys in combinatorics, 1987: Invited Papers for the Eleventh British Combinatorial Conference, London Mathematical Society Lecture Note Series, volume 123, Cambridge University Press, pages 53–80, http://www.renyi.hu/ p_erdos/1987-12.pdf