图的图兰型问题及超饱和极值问题

Extremal graph theory is interesting in the maximum or minimum of the parameters of graphs with given graph properties in combinatorics. This kind of problem has always been the core and hot issue of graph theory. The edge extremal problem that determines the maximal edges of graph without containing a subgraph H is called the Turan problem, and the number of edge of the extremal graph is called the Turan number of the graph H. For the classical Turan problem, a natural generalization, which is called supersaturation problems for graphs, is that determins the minimum number of copies of H when the number of edges of a graph exceeds the Turan number of graph H. This project focuses on Turan problems of graphs, and the supersaturation problems of graphs, and studies the extremal problem for new families of graphs. The research topics include:Erdos-Sos conjecture, Turan problems for linear forest, Turan problems for non-bipartite graphs, anti-Ramsey problems for non-bipartite graphs and supersaturation problems for matching-cirtitcal graphs.

极值图论是组合学中的一个分支，它研究这样的问题：给定的图的某个性质，在满足这个给定性质的一类图中，确定某种图的参数可能取到的最大或者最小值，这一类问题一直是图论的核心及热门问题。我们把确定不含有图H作为子图的固定顶点数的图可能取到的而最大的边数的这类问题称为图兰问题，称这个最大的边数为图H的图兰数。对于经典的图兰问题，一个自然的推广是：如果图的边数超过了图H的图兰数，那么这个图至少含有多少个子图H的复制？这类问题称为图的超饱和极值问题。本项目主要专注于图的图兰类型极值问题，以及超饱和极值问题，研究更多图类的极值问题。研究内容包括：Erdos-Sos猜想，线性森林和非二部图图兰问题，非二部图反拉姆塞问题以及匹配临界图的超饱和问题。

图兰型极值问题是极值图论的一个重要的研究方向。1941年图兰确定了不含完全图的图的最大边数。在此之后，研究各种图的图兰数以及相关的变形问题成为了极为重要的图论分支：极值图论。本项目主要研究图兰型极值问题以及与图兰问题相关的一些极值问题。主要内容有以下几个。一，线性森林的图兰数，二，边爆炸图的图兰数，三，路和圈的幂图的图兰数，四，给定最大度条件的图兰数，五，有关圈长的极值图论问题，六，轮图，不交团的图兰数。项目进展顺利，将Erdos等的一个重要结果推广到了任意的图类，该结果发表在图论顶级期刊JCTB上。证明了著名数学家Katona等提出的猜想。解决了轮图，以及两个不交团的图兰数。确定了一大类线性森林的确切的图兰数。得到了若干有关圈长问题的结果。项目执行期间共发表SCI论文10篇（接受1篇），其中JCTB1篇，EUJC2篇，JGT2篇，EJC1篇，DM3篇，GC1篇。本项目的研究为极值图论的研究注入了新的活力，被国内外同行广泛的引用，促进了学科同行之间的交流。