Sperner定理及其证明

额，最近看到了一个十分有趣的定理——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$个:

然后我们考虑题目中子集互不包含的限制，在这里转化成了，从任何两个子集的各任取一个生成排列，这两个生成排列不相等。也就是所有的子集的生成排列是没有重复的。因为如果某个排列$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

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

巴特西

Sperner定理及其证明

最新文章

热门文章