图与单纯复形的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.

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

EKR定理是极值组合学发展的直接推动力，是最基本的定理。EKR型交理论是极值组合学研究的重要问题之一。本项目主要研究图和单纯复形的EKR型交性质。利用组合移位算子的方法不仅彻底解决了Hurlbert 和Kamat提出的问题，即建立了梯图的EKR性质，而且进一步证明了梯图的严格EKR性质；证明了“梯图”满足cross-交对的猜想，并且进一步发现：如果一个图的任意诱导子图都与它属于同一类，且都存在两个顶点v1，v2，使得N[v2]包含N[v1]（这里N[vi]表示vi和vi的邻居构成的集合），那么这个图一定满足Kamat猜想；提出“单纯复形cross-交对的最大长度一定为单纯复形在该层的基数”的猜想。这个猜想包含了Kamat提出的猜想，并且证明了这个猜想对于压缩的单纯复形是成立的。这些工作丰富了EKR理论，为交性质的研究提供了新的思路。.项目中增加了图在生物序列相似性分析中的应用，实现了生物序列的可视化，即图表示。通过研究图的性质提炼出隐藏在生物序列背后的生物信息。本项目利用巧妙的组合映射，分别建立了蛋白质序列的2维图表示，DNA序列的2维图表示和3维图表示，并且提出了图表示的有效数值特征。这些图表示及其数值特征成功应用于物种的进化分析，流感病毒、戊型肝炎病毒等的序列分析和比较中，成为定性地和定量地分析生物学数据的强有力工具，为生物工作者在信息存储、序列比对和统计分析方面提供一定的理论依据和技术支持。