基于有限集和独立集的几类极值组合问题研究

The extreme set theory is an important branch of combinatorial mathematics, Studying the extremal problems based on finite set and independent set not only promotes the development for extreme set theory, but also affords a strong tool for applying this theory to theoretical computer science, biological science, information science, etc. In this proposal we mainly study some extremal problems based on finite set and independent set, and we hope to solve some challenging problems in combinatorics. The main content of this proposal contains the following: Firstly, based on finite set we study the upper bounds of the size of L-intersecting family, k-wise L-intersecting family with some restricted conditions. Secondly, we not only study the upper bounds of the size of nontrivial L-intersecting family, and nontrivial k-uniform t-intersecting family with restricted conditions , but also study the corresponding structures of families. Finally, we study the structures of the largest size of intersecting family based on r-independent set of sparse graphs, such as trees, bipartite graphs with given some graphic structure parameters. The problems studied in this project is an important problems in the theory of intersecting family, and the research will help to develop the theory of extreme set theory.

极值集合论是组合数学的一个重要分支，研究基于有限集和独立集的极值问题，不仅能大力促进极值集合论自身的发展，而且为理论计算机科学、信息科学、生命科学等领域的发展提供有力的工具。本项目将研究基于有限集和独立集的几类相关极值问题，解决一些富有挑战性的组合问题。研究内容主要包括：(1) 研究基于有限集的L-交族、k-wise L-交族等在满足一定条件下所含子集个数的上界；(2) 研究当非平凡集族分别是具有限制条件下的 L-交族、k-均匀 t-交族时，集族所含子集个数的上界和结构特征；(3) 重点研究稀疏图如：给定图结构参数下树、二部图等的r-元独立集构成的最大交族的结构及相关极值问题。本项目所研究的问题是交族理论中的重要问题，问题的解决对极值理论的发展有较大的推动作用。

极值集合论是组合数学的一个重要分支，其主要研究满足一定性质的有限集合构成的集族中的极大族或极小族问题。本项目通过构造多项式、随机路径、集合变换等方法，针对有限集和独立集中的极值问题完成了以下的研究工作。首先，我们采用构造独立多项式的方法研究k-wise L-交族和两个L-交族在限制条件下的上界，该结论可以部分解决著名的Snevily猜想。其次，基于Frankl和 Tokushige巧妙利用随机路径方法研究L-交族、k-wise L-交族的方法，我们对随机路径的几种表现形式展开研究。对于给定直径、匹配数、二划分等图结构参数情况下，我们刻画了树的hitting time 的上下界。该研究给出了与我们传统研究交族不一样的方法，极大地丰富了极值理论的内涵。对于随机路径的另外两种形式cover cost和reverse cost, 我们也刻画了它们取得下界时极图的结构，这些问题的解决使得我们部分解决Georgakopoulos教授提出的公开问题。最后，我们研究了给定图结构参数下二部图的独立多项式系数的极值问题，并且刻画了达到极值时极图的结构。此外，我们考虑了树的r-独立集构成的交族的上界。本项目按照计划书，全面完成了研究计划的目标和内容，为今后全面和深入研究交族的相关极值问题奠定了基础。