Sperner 定理

Sperner 定理

问题

给定 nNn\in \mathbb{N}^*,集合 S={1,2,...,n}S=\{1,2,...,n\} 的一组子集 A1,A2,...,AkA_1,A_2,...,A_k,其中任意两个子集互不包含。即,对于  1i<jk\forall\ 1\le i\lt j\le k,均有 AiAjA_i\nsubseteq A_j,并且 AiAjA_i\nsupseteq A_j

  1. n=5n=5 时,求 kmaxk_{\max}
  2. nNn\in \mathbb{N}^*,求 f(n)=kmaxf(n)=k_{\max}

定理

对于 \forall 包含 nn 个元素的集合 SS,最多可以选择其 (nn2)\binom n {\lfloor\frac n 2\rfloor} 个子集,使得任意两个子集互不包含。

证明

显然,如果我们选择全部 (nm)\binom n m 个大小为 mm 的子集,肯定不会出现包含关系。而 (nm)\binom n m 的最大值为 (nn2)\binom n {\lfloor\frac n 2\rfloor},所以 kmax(nn2)k_{\max}\ge\binom n {\lfloor\frac n 2\rfloor}

接下来,我们要证明 kmax(nn2)k_{\max}\le\binom n {\lfloor\frac n 2\rfloor}

对于 SS 的一个子集 AA,定义 PAP_AAA 的全排列和 SA\complement_S A 的全排列两两组合形成的 A!×SA!|A|!\times|\complement_S A|! 个排列所构成的集合。例如,对于 S={1,2,3,4,5}S=\{1,2,3,4,5\}A={2,3}A=\{2,3\}PAP_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

PA=12|P_A|=12

可以说明,对于 SS 的任意两个子集 A,BA,BABA\neq B),当且仅当 PAPB=P_A\cap P_B=\varnothing 时,AABB 互不包含。


充分性

A,BA,B 存在包含关系,不妨设 ABA\subset B。令 C=BA,D=SBC=\complement_B A,D=\complement_S B,则可以构造排列 ACD(PAPB)A\oplus C\oplus D\in (P_A\cap P_B)。所以 PAPB=P_A\cap P_B=\varnothing 时,AABB 互不包含。

必要性

PAPBP_A\cap P_B\neq\varnothing,不妨假设 AB|A|\le |B|。设排列 Q(PAPB)Q\in (P_A\cap P_B)。要么 A=A=\varnothing,则 ABA\subset B;要么 AABB 同时为 QQ 的一个前缀,又有 AB|A|\le |B|,故 ABA\subset B。所以 AABB 互不包含时,PAPB=P_A\cap P_B=\varnothing


因此,原问题等价于选出 kk 个子集 {A1,A2,...,Ak}\{A_1,A_2,...,A_k\},使得对于  1i<jk\forall\ 1\le i\lt j\le k,有 PAiPAj=P_{A_i}\cap P_{A_j}=\varnothing

注意到 SS 的全排列大小为 n!n!,则有:

i=1kPAin! \sum_{i=1}^k |P_{A_i}|\le n!

即:

i=1kAi!×(nAi)!n! \sum_{i=1}^k |A_i|!\times(n-|A_i|)!\le n!

两边同除以 n!n!,得:

i=1k1(nAi)1 \sum_{i=1}^k \frac 1 {\binom n{|A_i|}} \le 1

由于 (nAi)(nn2)\binom n{|A_i|}\le \binom n{\lfloor\frac n 2\rfloor}1(nAi)1(nn2)\frac 1{\binom n{|A_i|}} \ge \frac 1{\binom n{\lfloor\frac n 2\rfloor}},所以 k(nn2)k\le\binom n{\lfloor\frac n 2\rfloor}。原命题得证。

girl

图片来源 ᴮᵃᶜᵏᵘᵖ

参考

Sperner 定理及其证明 | www.cnblogs.com ᴮᵃᶜᵏᵘᵖ

热门博文