贡献者： 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$
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。