图与单纯复形的EKR型交性质研究

项目名称： 图与单纯复形的EKR型交性质研究

项目编号： No.11201409

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 李玉双

作者单位： 燕山大学

项目金额： 22万元

中文摘要： 有限集的Erd?s-Ko-Rado (EKR)定理是极值组合学乃至整个组合数学领域的重要定理。本项目将围绕该定理展开对图与单纯复形的EKR型交性质的研究。首先从具有明显结构特征的弦图、二部图和含孤立点的图入手，通过对它们的研究总结出具备哪些特性的图一定具有EKR性质；然后围绕EKR性质的一种重要推广形式- - cross交性质展开讨论。基于cross-交性质的建立在一定程度上要依赖于EKR性质，而图与单纯复形的EKR性质目前尚未完全解决，所以我们先讨论二者的cross-交对的性质，再对已知EKR性质的特殊图进行cross-交性质研究。在此基础上深入探索图与单纯复形的cross-交性质，最终为它们的EKR型交性质研究作出贡献。项目中除运用常用的组合移位算子外，还将融入交性质研究中不多见的代数移位算子和生成集法，进一步挖掘这两种方法的适用范围，以期为EKR型交理论研究提供更多的思路。

中文关键词： EKR定理；交性质；单纯复形；图表示；生物序列

英文摘要： Erd?s-Ko-Rado (EKR) Theorem for systems of finite sets is highly important in the area of extremal combinatorics, even in the whole combinatorics. This project will focus on this theorem to research the EKR-type intersecting properties for graphs and simplicial complexes. We will start with chordal graphs, bipartite graphs and graphs containing singletons, whose structure characteristics are all distinct, and then conclude which grpahs must have EKR properties. Next, pay our attention to a well-known generalization of EKR properties, i.e. cross-intersecting properties. They always depend on the EKR properties to a great extent, but until now the EKR properties for graphs and simplicial complexes have not been solved completely. Hence we will first discuss the cross-intersecting pairs for them, and then investigate the cross-intersecting properties for such graphs having EKR properties. On that basis we will proceed to explore cross-intersecting properties for graphs and simplicial complexes, and finally contribute to the research. Besides familiar combinatorial shifting, we will employ algebraic shifting and generating sets which are rarely used to prove intersection theorems, and further extend their applicability such that more ideas for the EKR-type intersection research can be found.

英文关键词： Erdos-Ko-Rado (EKR) Theorem；intersecting property；simplicial complex；graphical representation；biological sequence