Sperner 定理

贡献者： huanglei0829

　　 先给出一些记号：

• 集合 $\{1,2,\cdots ,n\}$ 简记为 $[n]$
• 集合 $X$ 的所有子集构成的集族记为 $2^X$，称为 $[n]$ 的幂集

　　 下面我们给出 Sperner 定理：

　　 为给出定理 1 的证明，我们先引入链的定义：

　　 定理 1的证明：

1. 如果 $\mathcal{F}$ 是独立族，那么每一条极大链 $\mathcal{C}$ 中至多含有一个 $\mathcal{F}$ 中的集合；
2. 算两次：$\sum _{A\in \mathcal{F}}{N}_A=\sum _{\mathcal{C}}{N}_{\mathcal{C}}$，其中 $N_A$ 表示包含集合 $A$ 的极大链的个数，$N_{\mathcal{C}}$ 表示极大链 $\mathcal{C}$ 中含有的 $\mathcal{F}$ 中的集合的个数，$\sum _{\mathcal{C}}$ 表示对所有极大链求和；
3. 考察 $N_A$，$N_A=|A|!\cdot (n-|A|)!=\frac{n!}{\left(\begin{array}{c}n\\ |A|\end{array}\right)}\ge \frac{n!}{\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)}$；
4. 由 1.，我们有：$N_{\mathcal{C}}\le 1$；
5. 从而 $n!=\sum _{\mathcal{C}}1\ge \sum _{\mathcal{C}}{N}_{\mathcal{C}}=\sum _{A\in \mathcal{F}}{N}_A\ge \sum _{A\in \mathcal{F}}\frac{n!}{\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)}=\frac{n!}{\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)}\cdot |\mathcal{F}|$，整理即得 $|\mathcal{F}|⩽\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)$，证毕。$◻$

　　 Sperner 定理（定理 1）的另一个证明用到如下引理 1：（以下讨论默认对 $[n]$ 进行）
$$ 先给出对称链的定义：

　　 引理 1的证明：利用数学归纳法可证明引理 1。此处略去不表。

引理 1 注记：考察引理 1 中划分出的不交对称链的个数：每个大小为 $\lfloor \frac{n}{2}\rfloor$ 的集合都唯一包含于某一条对称链，从而对称链个数为 $\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)$。$◻$

　　 定理 1的另证：考虑引理 1中的对称链划分，我们知道每个 $A_i\in \mathcal{F}$ 被包含于唯一一条对称链，从而 $\mathcal{F}$ 中 $A_i$ 的个数不大于对称链的个数，即 $|\mathcal{F}|\le \left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)$，证毕。$◻$


下面我们来考察 Sperner 定理中等号成立的条件：

　　 定理 2的证明：

1. 定理 1 中等号取到当且仅当 $|A|=\lfloor \frac{n}{2}\rfloor$ 或 $\lceil \frac{n}{2}\rceil ,\mathrm{\forall }A\in \mathcal{F}$ 且 $N_{\mathcal{C}}=1,\mathrm{\forall }\mathcal{C}$ 是极大链。可以看出，只需要考察 $n=2k+1$ 的情形（即 $n$ 是奇数）；
2. 倘若 $A\in \mathcal{F}$ 使得 $|A|=\lfloor \frac{n}{2}\rfloor =k$，则 $\mathrm{\forall }x\in [n]\mathrm{\setminus }A,y\in A,\hat{A}\triangleq A\cup \{x\}\notin \mathcal{F}$；
3. 由于 $N_{\mathcal{C}}=1$，这里 $\mathcal{C}$ 取作包含 $\hat{A}$ 和 $B\triangleq \hat{A}\mathrm{\setminus }\{y\}$ 的极大链，我们有 $B\in \mathcal{F}$。也就是说，任一大小为 $k$ 的集合若落在 $\mathcal{F}$ 中，则其替换了一个元素后得到的集合依旧落在 $\mathcal{F}$ 中；
4. 而每一个大小为 $k$ 的集合总可以对任一大小为 $k$ 的集合作若干次替换后得到，故若存在 $A\in \mathcal{F}$ 使得 $|A|=k$，则 ${\mathcal{A}}_k\subset \mathcal{F}$。
5. 由 $|{\mathcal{A}}_{\lfloor \frac{n}{2}\rfloor }|=|{\mathcal{A}}_{\lceil \frac{n}{2}\rceil }|=\left(\begin{array}{c}n\\ \lfloor \frac{n}{2}\rfloor \end{array}\right)$ 我们知道：此时 $\mathcal{F}={\mathcal{A}}_{\lfloor \frac{n}{2}\rfloor }$ 或 ${\mathcal{A}}_{\lceil \frac{n}{2}\rceil }$，证毕.$◻$