Sperner 定理
问题
给定 n∈N∗,集合 S={1,2,...,n} 的一组子集 A1,A2,...,Ak,其中任意两个子集互不包含。即,对于 ∀ 1≤i<j≤k,均有 Ai⊈Aj,并且 Ai⊉Aj。
- 当 n=5 时,求 kmax
- 对 n∈N∗,求 f(n)=kmax
定理
对于 ∀ 包含 n 个元素的集合 S,最多可以选择其 (⌊2n⌋n) 个子集,使得任意两个子集互不包含。
证明
显然,如果我们选择全部 (mn) 个大小为 m 的子集,肯定不会出现包含关系。而 (mn) 的最大值为 (⌊2n⌋n),所以 kmax≥(⌊2n⌋n)。
接下来,我们要证明 kmax≤(⌊2n⌋n)。
对于 S 的一个子集 A,定义 PA 为 A 的全排列和 ∁SA 的全排列两两组合形成的 ∣A∣!×∣∁SA∣! 个排列所构成的集合。例如,对于 S={1,2,3,4,5},A={2,3},PA 为:
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
∣PA∣=12。
可以说明,对于 S 的任意两个子集 A,B(A=B),当且仅当 PA∩PB=∅ 时,A 和 B 互不包含。
充分性
若 A,B 存在包含关系,不妨设 A⊂B。令 C=∁BA,D=∁SB,则可以构造排列 A⊕C⊕D∈(PA∩PB)。所以 PA∩PB=∅ 时,A 和 B 互不包含。
必要性
若 PA∩PB=∅,不妨假设 ∣A∣≤∣B∣。设排列 Q∈(PA∩PB)。要么 A=∅,则 A⊂B;要么 A 和 B 同时为 Q 的一个前缀,又有 ∣A∣≤∣B∣,故 A⊂B。所以 A 和 B 互不包含时,PA∩PB=∅。
因此,原问题等价于选出 k 个子集 {A1,A2,...,Ak},使得对于 ∀ 1≤i<j≤k,有 PAi∩PAj=∅。
注意到 S 的全排列大小为 n!,则有:
i=1∑k∣PAi∣≤n!
即:
i=1∑k∣Ai∣!×(n−∣Ai∣)!≤n!
两边同除以 n!,得:
i=1∑k(∣Ai∣n)1≤1
由于 (∣Ai∣n)≤(⌊2n⌋n),(∣Ai∣n)1≥(⌊2n⌋n)1,所以 k≤(⌊2n⌋n)。原命题得证。

图片来源 ᴮᵃᶜᵏᵘᵖ
参考
Sperner 定理及其证明 | www.cnblogs.com ᴮᵃᶜᵏᵘᵖ