Sperner 定理
Sperner 定理
问题
给定 n\in \mathbb{N}^*，集合 S=\{1,2,...,n\} 的一组子集 A_1,A_2,...,A_k，其中任意两个子集互不包含。即，对于 \forall\ 1\le i\lt j\le k，均有 A_i\nsubseteq A_j，并且 A_i\nsupseteq A_j。
- 当 n=5 时，求 k_{\max}
- 对 n\in \mathbb{N}^*，求 f(n)=k_{\max}
定理
对于 \forall 包含 n 个元素的集合 S，最多可以选择其 \binom n {\lfloor\frac n 2\rfloor} 个子集，使得任意两个子集互不包含。
证明
显然，如果我们选择全部 \binom n m 个大小为 m 的子集，肯定不会出现包含关系。而 \binom n m 的最大值为 \binom n {\lfloor\frac n 2\rfloor}，所以 k_{\max}\ge\binom n {\lfloor\frac n 2\rfloor}。
接下来，我们要证明 k_{\max}\le\binom n {\lfloor\frac n 2\rfloor}。
对于 S 的一个子集 A，定义 P_A 为 A 的全排列和 \complement_S A 的全排列两两组合形成的 |A|!\times|\complement_S A|! 个排列所构成的集合。例如，对于 S=\{1,2,3,4,5\}，A=\{2,3\}，P_A 为：
2 3 | 1 4 5
3 2 | 1 4 5
2 3 | 1 5 4
3 2 | 1 5 4
2 3 | 4 1 5
3 2 | 4 1 5
2 3 | 4 5 1
3 2 | 4 5 1
2 3 | 5 1 4
3 2 | 5 1 4
2 3 | 5 4 1
3 2 | 5 4 1
|P_A|=12。
可以说明，对于 S 的任意两个子集 A,B（A\neq B），当且仅当 P_A\cap P_B=\varnothing 时，A 和 B 互不包含。
充分性
若 A,B 存在包含关系，不妨设 A\subset B。令 C=\complement_B A,D=\complement_S B，则可以构造排列 A\oplus C\oplus D\in (P_A\cap P_B)。所以 P_A\cap P_B=\varnothing 时，A 和 B 互不包含。
必要性
若 P_A\cap P_B\neq\varnothing，不妨假设 |A|\le |B|。设排列 Q\in (P_A\cap P_B)。要么 A=\varnothing，则 A\subset B；要么 A 和 B 同时为 Q 的一个前缀，又有 |A|\le |B|，故 A\subset B。所以 A 和 B 互不包含时，P_A\cap P_B=\varnothing。
因此，原问题等价于选出 k 个子集 \{A_1,A_2,...,A_k\}，使得对于 \forall\ 1\le i\lt j\le k，有 P_{A_i}\cap P_{A_j}=\varnothing。
注意到 S 的全排列大小为 n!，则有：
即：
两边同除以 n!，得：
由于 \binom n{|A_i|}\le \binom n{\lfloor\frac n 2\rfloor}，\frac 1{\binom n{|A_i|}} \ge \frac 1{\binom n{\lfloor\frac n 2\rfloor}}，所以 k\le\binom n{\lfloor\frac n 2\rfloor}。原命题得证。
