关于组合数学中最大杂置的证明
本帖最后由 sir_chen 于 2009-10-16 21:55 编辑令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=$时,C_k有最多的元素,因此由这种方法最大可以生成大小为$C_n^{}$的杂置.Sperner证明了有n个元素的集合S最大能生成大小为$C_n^{}$的杂置.
现在要证明的问题是这个问题的逆命题:S是n个元素集合,如果n为偶数,那么大小为$C_n^{}$的杂置有且仅有一个,该杂置为C_{n/2}(即S所有含有n/2个元素的子集形成的集合);如果n是奇数,则大小为$C_n^{}$的杂置有且仅有两个,这两个杂置是C_{{n-1}/2}和C_{{n+1}/2}. 很简单.
提示,构造$C_n^{}$个集合链.每个集合链包含了从空集到全集的n+1个相互包含的集合.
而所有这些链的并覆盖所有$2^n$个集合. 本帖最后由 sir_chen 于 2009-10-16 22:05 编辑
你的这个证法好像是证明最大杂置大小为$C_n^{}$,我现在要证的是逆命题,杂置大小为$C_n^{}$的只能是$C_{}$,也就是说将$C_{}中任意多个集合换成其他类型的必存在包含关系.对于n为偶数的情况我已经证明了,现在的问题是当n为奇数时,如何证明含有{{n+1}/2}与{{n-1}/2}混合的集合一定存在包含关系
页:
[1]