组合与图论中的一类极值问题研究

The extremal combinatorics is one of the most active research area in combinatorics and graph theory. Typical problems is to determine the extremal value and structure of a certain systems. The Erdós-Ko-Rado theorem of finite set is one of the central theorems of this field. There are many generalizations on this theorem. Thoes generalizations are mainly concentrated on set systems, vector space of finite fields and symetric group, etc. In this project, we will generalize it from the aspect of graph and hypergraph, and develop a uniform framework for generalizing EKR theorem in different fields. Particular problems we shall study in this project include EKR property in general systems, the k-independent set of kneser graphs, the Erdós conjecture on the relation between matching number and edge number of hypergraph. We shall try to solve some open problems and conjectures.

极值理论是近几十年来组合数学与图论研究领域中一直十分活跃的一个研究方向。极值的确定以及达到极值时集族结构的确定是这一领域的主要研究内容。有限集上的Erd?s-Ko-Rado定理（简称EKR定理）是这一领域的核心定理，以往关于该定理的推广主要集中在子集系，有限向量空间以及置换群等具体的对象上。在本项目中我们将从简单图和超图等不同的角度推广EKR定理，把不同领域中看似孤立的问题通过EKR定理联系在一起，试图在一个一般的框架体系下研究极值问题。具体内容为：一般集系上的EKR性质研究；Kneser图的2-独立集研究；超图中关于边数与匹配数关系的 Erd?s猜想研究。力争解决其中的一些公开问题和猜想。相关结论的取得将推动有限向量空间、置换群等对象上的一系列同类问题的研究，从而带来EKR理论研究的新的繁荣，最终促进组合极值理论的进一步发展。

极值理论是近几十年来组合数学与图论研究领域中一直十分活跃的一个研究方向。极值的确定以及达到极值时集族结构的确定是这一领域的主要研究内容。有限集上的Erdós-Ko-Rado定理（简称EKR定理）是这一领域的核心定理，以往关于该定理的推广主要集中在子集系，有限向量空间以及置换群等具体的对象上。在本项目中我们将从简单图和超图等不同的角度推广EKR定理，把不同领域中看似孤立的问题通过EKR定理联系在一起，试图在一个一般的框架体系下研究极值问题。具体内容为：一般集系上的EKR性质研究；Kneser图的2-独立集研究；超图中关于边数与匹配数关系的 Erdós猜想研究。力争解决其中的一些公开问题和猜想。在项目执行期间，我们在着色集上推广了Erdós匹配猜想；在一些集系上推广了EKR定理；确定了多个Kneser图卷积的独立数。另外，我们还确定了三个图乘积的独立数。相关结论的取得将会促进EKR定理的发展。