Sperner 定理
贡献者： huanglei0829
先给出一些记号：
- 集合 $\{1,2,\cdots,n\}$ 简记为 $[n]$
- 集合 $X$ 的所有子集构成的集族记为 $2^{X}$，称为 $[n]$ 的幂集
定义 1 独立族
设 $\mathcal{F}\subset 2^{[n]}$ 是 $[n]$ 的一个子集族。我们说 $\mathcal{F}$ 是独立的如果 $\forall A,B\in \mathcal{F}$ 我们都有 $A\not\subset B$ 和 $B\not\subset A$（即 $\mathcal{F}$ 中的任意两个集合互不包含）.
下面我们给出 Sperner 定理：
定理 1 Sperner's Theorem
对于任意 $[n]$ 的独立子集族 $\mathcal{F}$，我们有：
$|\mathcal{F}|\leq \begin{pmatrix}n\\\lfloor \frac{n}{2}\rfloor\end{pmatrix} $
为给出定理 1 的证明，我们先引入链的定义：
定义 2 链
$[n]$ 的子集构成的一条链指一列 $[n]$ 的子集 $\{A_i\}_{i=1}^{k}$ 使得：
$A_1\subset A_2\subset A_3\subset \cdots \subset A_k$，其中 $A_1,\cdots,A_k$ 互不相同。这里 $k$ 称为链的长度。
$\qquad$
一条链称为极大链如果 $k=n+1$。简单地我们知道，$[n]$ 的子集可以构成的极大链的个数为 $n!$。
定理 1的证明：
- 如果 $\mathcal{F}$ 是独立族，那么每一条极大链 $\mathcal{C}$ 中至多含有一个 $\mathcal{F}$ 中的集合；
- 算两次：$\sum\limits_{A\in \mathcal{F}}N_A=\sum\limits_{\mathcal{C}}N_{\mathcal{C}}$，其中 $N_A$ 表示包含集合 $A$ 的极大链的个数，$N_{\mathcal{C}}$ 表示极大链 $\mathcal{C}$ 中含有的 $\mathcal{F}$ 中的集合的个数，$\sum\limits_{\mathcal{C}}$ 表示对所有极大链求和；
- 考察 $N_A$，$N_A=|A|!\cdot (n-|A|)!=\frac{n!}{ \begin{pmatrix}n\\|A|\end{pmatrix} }\geq \frac{n!}{ \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} }$；
- 由 1.，我们有：$N_{\mathcal{C}}\leq 1$；
- 从而 $n!=\sum\limits_{\mathcal{C}}1\geq \sum\limits_{\mathcal{C}}N_{\mathcal{C}}=\sum\limits_{A\in \mathcal{F}}N_A\geq \sum\limits_{A\in \mathcal{F}}\frac{n!}{ \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} }=\frac{n!}{ \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} }\cdot |\mathcal{F}|$，整理即得 $|\mathcal{F}|\leqslant \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} $，证毕。$\square$
Sperner 定理（定理 1）的另一个证明用到如下引理 1：（以下讨论默认对 $[n]$ 进行）
$\qquad$ 先给出对称链的定义：
定义 3 对称链
一个链称为对称链如果 $|A_1|=\frac{n+1-k}{2}$ 且 $|A_k|=n-\frac{n+1-k}{2}$
$\qquad$
换句话说，存在 $s\in \mathbb{N}$ 使得链中的集合大小分别为 $s,s+1,\cdots,n-s$。
例 1 对称链的例子与反例
$n=3$ 时，$\{\{2\},\{2,3\}\}$ 是对称链，$\{\{1\},\{1,2\},\{1,2,3\}\}$ 不是对称链;
$n=4$ 时，$\{\emptyset,\{1,2,3,4\}\}$ 不是对称链。
引理 1 [n] 的幂集的对称链划分
$2^{[n]}$ 可以划分为不交对称链。
引理 1的证明：利用数学归纳法可证明引理 1。此处略去不表。
引理 1 注记：考察引理 1 中划分出的不交对称链的个数：每个大小为 $\lfloor\frac{n}{2}\rfloor$ 的集合都唯一包含于某一条对称链，从而对称链个数为 $ \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} $。$\square$
定理 1的另证：考虑引理 1中的对称链划分，我们知道每个 $A_i\in \mathcal{F}$ 被包含于唯一一条对称链，从而 $\mathcal{F}$ 中 $A_i$ 的个数不大于对称链的个数，即 $|\mathcal{F}|\leq \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} $，证毕。$\square$
下面我们来考察 Sperner 定理中等号成立的条件：
定理 2 Sperner 定理的取等条件
Sperner 定理中等号成立当且仅当 $\mathcal{F}=\mathcal{A}_{\lfloor\frac{n}{2} \rfloor}$ 或 $ \mathcal{A}_{\lceil\frac{n}{2} \rceil}$，这里 $\mathcal{A}_s\triangleq\{B\subset[n]||B|=s\}$。
定理 2的证明：
- 定理 1 中等号取到当且仅当 $|A|=\lfloor\frac{n}{2} \rfloor$ 或 $\lceil\frac{n}{2} \rceil,\forall A\in \mathcal{F}$ 且 $N_{\mathcal{C}}=1,\forall \mathcal{C}$ 是极大链。可以看出，只需要考察 $n=2k+1$ 的情形（即 $n$ 是奇数）；
- 倘若 $A\in \mathcal{F}$ 使得 $|A|=\lfloor\frac{n}{2} \rfloor=k$，则 $\forall x\in [n]\backslash A,y\in A,\hat{A}\triangleq A\cup\{x\}\notin \mathcal{F}$；
- 由于 $N_{\mathcal{C}}=1$，这里 $\mathcal{C}$ 取作包含 $\hat{A}$ 和 $B\triangleq \hat{A}\backslash\{y\}$ 的极大链，我们有 $B\in \mathcal{F}$。也就是说，任一大小为 $k$ 的集合若落在 $\mathcal{F}$ 中，则其替换了一个元素后得到的集合依旧落在 $\mathcal{F}$ 中；
- 而每一个大小为 $k$ 的集合总可以对任一大小为 $k$ 的集合作若干次替换后得到，故若存在 $A\in \mathcal{F}$ 使得 $|A|=k$，则 $\mathcal{A}_k\subset \mathcal{F}$。
- 由 $|\mathcal{A}_{\lfloor\frac{n}{2} \rfloor}|=| \mathcal{A}_{\lceil\frac{n}{2} \rceil}|= \begin{pmatrix}n\\ \lfloor\frac{n}{2} \rfloor\end{pmatrix} $ 我们知道：此时 $\mathcal{F}=\mathcal{A}_{\lfloor\frac{n}{2} \rfloor}$ 或 $ \mathcal{A}_{\lceil\frac{n}{2} \rceil}$，证毕.$\square$