论文部分内容阅读
极值集合论是组合数学的一个重要分支,主要研究一定限制条件下(或者说满足一定性质)的集合系。它在数学和计算机的其他分支如概率论、离散几何等领域都有应用。其最初的研究可以回溯到1928年发表出来的Sperner的一个定理。Sperner定理指出:对于n元集合上的子集而言,要求这些子集满足两两互不包含的条件,如果想尽可能多地找出这样的子集,那么最好的答案就是选出所有的大小为[n/2]的子集。之后不久,Erd(o)s,柯召,Rado三人给出了著名的Erd(o)s-Ko-Rado定理,即对满足其中任意两个子集相交不为空的集合系给出了其上界,并且这个上界是可以达到的。这两个定理是极值集合论中十分重要的两个结果,许多研究人员不仅对它们以不同的方法加以证明,并且对其相关问题进行深入研究。在上个世纪八、九十年代Sperner定理就发展成为了组合数学中的专门问题--Sperner理论。而在Erd(o)s-Ko-Rado定理发表之后,人们对它所涉及的问题进行了两个方向上的探究,一方面考虑集合之间不同的相交条件,得出了很多著名的结论,如Delsarte定理,Ray Chaudhuri-Wilson定理,Frankl-Wilson定理,Alon-Babai-Suzuki定理,Snevily猜想:另一方面如果引入复形的概念,则原定理中的相交条件下的集合系是不包含1-复形的,进而考虑更一般的情况,Chvátal给出了一个关于集合系中不含d-复形的猜想,习惯上称为Chvátal复形猜想。
本研究在结构上由两部分组成。第一部分是关于相交集合系以及交错相交系的研究,第二部分是关于Chvátal复形猜想的一些研究。第一章里,首先介绍本文中用到的一些基本定义和记号,进而给出极值集合论主要研究问题的概述以及一些典型的结论,最后对本文的结构安排和主要结论作以简要叙述。本文的第一部分由第二章和第三章组成。在第二章,我们研究限制模素数情况下的集合系,即考虑的集合系中的元素大小及元素相交产生集合的大小均限制在模素数条件下。我们给出两个关于交错相交系的结果,其中一个可以看做Franld在1984年的一个结论的延伸:另一个考虑集合系中的元的大小及元相交集合大小限制在一定的范围,得到更紧一些的结论,并且如果稍微改变一下条件,由此可以推出Chen和Liu在2009年的一个结果。在此基础上,我们给出了关于k个元相交条件下的集合系的上界。在第三章,我们研究限制模素数幂情况下的集合系。我们引入分离多项式和(p-adic)赋值的概念,研究对象涉及交错相交系、一致相交系、限制集合差和集合对称差的集合系,分别给出它们的多项式上界。在本章的最后,我们还给出了关于代码的一个上界,从它可以直接导出我们前面一个关于限制集合对称差的集合系的结论。第四章作为本文的第二部分,我们研究了Chvátal复形猜想,并且证明了猜想在n=k+2时的正确性。我们引入补集的讨论,将问题转化为简单图上的问题并和匹配理论建立了联系。在主要结果的证明之后,我们又对其边界问题单独给出了两个证明。