Sperner 定理

前言#

这是我个人在 2024 暑期外出培训时自己写的笔记，仅摘录一些简单又有用的内容。

Sperner 定理#

Sperner 定理：设$A$为$n$元集合，它的$k$个子集$A_{1},A_{2},...,A_{k}$互不包含，有$k_{max}=C_{ n}^{[\frac{n}{2}]}$。

Sperner 证明#

我们新定义一个结构叫做“最大链”，它是长这样的：

其中$S_{i+1}$比$S_{i}$多一个元素，显然，这个链条是最长的，故称之为“最大链”。这个概念有什么用呢？我们可以发现以下特点：

1. 在$n$元集合$A$中，一共有$n!$条最大链；
2. 所有的最大链中的所有集合包含了$A$的所有子集；
3. 若$A_{i}$在一条最大链上，则$A_{j}$不可能和$A_{i}$在同一条链上；
4. 一个子集$A_{i}$所“占据”的最大链有$card(A_{i})![n-card(A_{i})]!$条。
5. 在理想情况下，只要还有剩余的最大链，就不会出现重合。

所以，现在问题被转换成了，如何在$n!$条最大链构成的集合中放入尽可能多的子集并且保证每一条最大链最多只包含一个子集。

因为“在理想情况下，只要还有剩余的最大链，就不会出现重合”，所以我们希望每一个子集所“占据”的最大链尽可能少。可以发现，当$card(A_{i})=[\frac{n}{2}]$时，子集$A_{i}$所“占据”的最大链最少。则一共可以放入$\frac{n!}{[\frac{n}{2}]!(n-[\frac{n}{2}])!}$个集合。显然这个数就是$C_{ n}^{[\frac{n}{2}]}$。

Sperner 例题#

我们可以列一个表格来表示每天每人的表演情况：

这里我们把每一个的表演场次安排看作一个集合，里面的每一个元素包含了表演的天数，也就是说不表演的天数是不放在里面的。题目要求任意两个人都互相给对面表演过，那么就是要求出现下面的结构：

这个结构我们不好直接考虑什么时候存在，让我们想想什么时候两个人没有互相表演：

1. 两个人表演场次完全相同，也就是两个人的表演场次安排集合相同；
2. 两个人只有一个人为另一个表演过，也就是两个人的表演场次安排集合相互包含。

下面是两个例子：

两个人都没有为对方表演过：此时两个集合相同。

只有一个人为另一个人表演过：此时两个集合存在包含关系。

那么显然当两个人的表演安排场次互不包含时，就出现了我们需要的结构。也就是说，让两个人互相为对方表演，需要让他们两个的表演安排场次集合互不包含。

现在的问题是，有没有足够的互不包含子集为所有小朋友分配而不重复？

我们可以通过Sperner 定理获得在不同天数下最多的方案数：

1. 一天：不用考虑；
2. 两天：$C_{2}^{[\frac{2}{2}]} = 2$，最多只有两种，无法分配；
3. 三天：$C_{3}^{[\frac{3}{2}]} = 3$，最多只有三种，无法分配；
4. 四天：$C_{4}^{[\frac{4}{2}]} = 6$，最多只有六种，无法分配；
5. 五天：$C_{5}^{[\frac{5}{2}]} = 10$，最多只有十种，无法分配；
6. 六天：$C_{6}^{[\frac{6}{2}]} = 20$，可以分配；

综上，至少需要六天。