关于组合数学中最大杂置的证明

sir_chen

令S是n个元素的集合,S的一个杂置(clutter)是S的组合的集合C,且C中没有一个组合包含另一个组合.
例如:$S={a,b,c,d}$,则$C={{a,b},{b,c,d},{a,d},{a,c}}$就是一个杂置.得到S的杂置的一种方法是选择一个整数k≤n,然后取$C_k$(从S中任取k个元素形成的所有组合的集合)为S的所有的k-组合.由于$C_k$中的每个组合都有k个元素,因此在$C_k$中没有组合能够包含另外的组合,从而$C_k$是一个杂置.当$k=[n/2]$时,$C_k$有最多的元素,因此由这种方法最大可以生成大小为$C_n^{[n/2]}$的杂置.Sperner证明了有n个元素的集合S最大能生成大小为$C_n^{[n/2]}$的杂置.
现在要证明的问题是这个问题的逆命题:S是n个元素集合,如果n为偶数,那么大小为$C_n^{[n/2]}$的杂置有且仅有一个,该杂置为$C_{n/2}$(即S所有含有$n/2$个元素的子集形成的集合);如果n是奇数,则大小为$C_n^{[n/2]}$的杂置有且仅有两个,这两个杂置是$C_{{n-1}/2}$和$C_{{n+1}/2}$.

mathe

很简单.
提示,构造$C_n^{[n/2]}$个集合链.每个集合链包含了从空集到全集的n+1个相互包含的集合.
而所有这些链的并覆盖所有$2^n$个集合.

sir_chen

你的这个证法好像是证明最大杂置大小为$C_n^{[n/2]}$,我现在要证的是逆命题,杂置大小为$C_n^{[n/2]}$的只能是$C_{[n/2]}$,也就是说将$C_{[n/2]}中任意多个集合换成其他类型的必存在包含关系.对于n为偶数的情况我已经证明了,现在的问题是当n为奇数时,如何证明含有{{n+1}/2}与{{n-1}/2}混合的集合一定存在包含关系