Sperner定理及其证明

时间:2021-02-03 19:27:30

额,最近看到了一个十分有趣的定理——Sperner定理。其实这个定理在OI中没什么用处,因此我都没把这篇文章放到我的OI标签里(不知道在MO中是否有用?)但是觉得它很有趣于是就过来写一下。

由于博主太弱不会用LaTeX写取整符号,本文中用\([x]\)表示\(x\)下取整。

问题: 有一个\(n\)元集合\(S_n\),从中选出若干个子集,满足没有任何两个子集之间存在包含关系,问最多能选出多少个?

首先结论是很好猜的。如果把所有\(k\)元子集全部选出,那么显然不会包含,一共能选\(n\choose k\)个子集。显然这个数在\([\frac{n}{2}]\)时取到最大值,我也构造不出来什么更优的选法,我猜答案就是\(n\choose [\frac{n}{2}]\)

正确答案就是\(n\choose [\frac{n}{2}]\). 但这个结论的精彩之处在于它的证明:

证明: 对于选出的每一个子集\(S\),我们定义它的生成排列(好吧这个名字是我自己瞎起的)为一些\(1\)\(n\)的排列,这个排列应当满足前\(|S|\)个元素构成的集合为\(S\), 后\(n-|S|\)个元素构成的集合为\(S_n-S\). 不难发现一个集合\(S\)的生成排列有\(|S|!(n-|S|)!\)个。

例如: \(n=5\),集合\({1,3,4}\)的生成排列有以下\(12\)个:

1 3 4 2 5
1 3 4 5 2
1 4 3 2 5
1 4 3 5 2
3 1 4 2 5
3 1 4 5 2
3 4 1 2 5
3 4 1 5 2
4 1 3 2 5
4 1 3 5 2
4 3 1 2 5
4 3 1 5 2

然后我们考虑题目中子集互不包含的限制,在这里转化成了,从任何两个子集的各任取一个生成排列,这两个生成排列不相等。也就是所有的子集的生成排列是没有重复的。因为如果某个排列\(p\)同时是两个不相等的子集\(A,B\)的生成排列,若\(|A|=|B|\)则有\(A\)\(B\)都是排列\(p\)的同一前缀构成的集合,\(A,B\)相等,矛盾;否则不妨设\(|A|<|B|\), 则\(A\)集合内元素的一个排列是\(B\)内元素的一个排列的前缀,显然有\(A\in B\)。同样地,我们可以证明如果\(A\)包含\(B\), 则一定存在排列\(p\)满足\(p\)同时是\(A\)\(B\)的生成排列。

因此,原题条件等价于,选出尽量多的集合,使得所有集合的生成排列没有重复。而设选出了\(m\)个集合,第\(i\)个集合的大小是\(S_i\), 因为所有生成排列没有重复,所有生成排列的个数不超过\(n!\), 也就是\[\sum^m_{i} |S_i|!(n-|S_i|)!\le n!\]\(n!\)除过去\[\sum^m_{i=1} \frac{1}{n\choose S_i}\le 1\]根据简单的二项式系数性质可得\(m\le {n\choose [\frac{n}{2}]}\)

(非常抱歉我把如此简单的东西讲复杂了QAQ)

不过以上过程虽然很容易理解,但是确实很难想啊……据说数学界研究了十几年才得到这个证明QAQ

另外还听说这个定理可以推广到可重集。