超图中几个极值问题的研究

Extremal graph theory is one of the core branches in discrete mathematics, especially in graph theory. Hypergraphs are natural extensions of graphs, which have many important practical applications, especially in VLSI and super-networks. Turán-type problems are the cornerstone of extremal graph theory, which frequently appear in the areas of discrete geometry, number theory, computer science and coding theory etc. In this project, based on the our previous research, we will study some extremal problems in hypergraphs by using random and combinatorial methods: study the Turán number or Turán density of some special classes of graphs (including small graphs, regular graphs) and try to improve some results; investigate the Erdos' open problem on jumping numbers and characterize some jumping and non-jumping numbers of k-uniform hypergraphs; do some research on the Turán numbers and strong jumping numbers of non-uniform hypergraphs; study the conjecture of Griggs and Lu on the Turán density of posets and try to improve some existing results. Extremal problem on hypergraphs has strong important theoretical significance and application background, and is a very challenging topic. Through this project, hope that we can do some contribution to the development of extremal hypergraph theory.

极值图论是离散数学，特别是图论学科的一个核心分支。超图是图的自然推广，具有很多的实际应用，特别是在大规模集成电路的设计以及超网络的研究中具有很重要的应用。Turán类问题是极值图论的基石，经常出现在离散几何、数论、计算机科学以及编码等研究领域。本项目将在前期工作的基础上，主要利用组合方法和随机方法，围绕超图中的几个极值问题展开研究：研究一些特殊子图（如小子图、正则图等）的Turán数或Turán密度，尝试改进一些相关结果；围绕Erdos的关于跳跃数的公开问题展开研究，刻画一致超图的跳跃数和非跳跃数；研究非一致超图的Turán数和强跳跃数；围绕Griggs和陆临渊的关于偏序集的Turán密度的猜想展开研究，希望改进其中的若干结果。超图的极值问题的研究具有重要的理论意义和应用背景，是非常具有挑战的课题。计划通过本项目的研究，为超图极值理论的发展添砖加瓦。

本项目已按计划完成，达到预期目标。主要取得了如下研究成果：(A). 与李学良等合作，构造了5-一致超图的一些非跳跃数； (B). 与李佳傲、顾冉等合作，确定了k-一致超图中路和圈的反Ramsey数；(C). 与Henry Liu、美国的Colton Magnant、日本的Akira Saito、德国的Ingo Schiermeyer等合作，确定了K4 的Gallai-Ramsey数的精确值；与博士生雷辉和美国的宋梓霞等合作确定了10圈和12圈的Gallai-Ramsey 数；(D). 与博士生兰永新和美国的宋梓霞等合作，刻画了H-free的平面图的结构性质；研究了路和圈的平面反Ramsey数，刻画了一些上下界；研究了禁止子图为Theta图的平面极值问题；撰写了关于平面Turan数和平面反Ramsey数的综述文章；(E). 与博士生兰永新等合作，刻画了禁止森林的图的度幂和的极值及相应极图；刻画了部分星森林的Turan数；刻画了一些短路的平面Turan数。(F). 与韩国的Suil O等合作，刻画了k-边连通图的饱和数及这类图的谱半径的界；与美国的范能和河海大学的顾冉合作，研究了随机图的混合连通度的性质；(G). 与加拿大的Kathie Cameron、比利时的Jan Goedgebeur以及黄申为等合作，给出了(P5, H)-free 的图中k-临界图的一个完整刻画；(H). 博士研究生雷辉与陆临渊教授等合作，在超图的拉格朗日方面，研究了Frankl-Furedi猜想，结果已经投稿；(I). 与博士生雷辉和美国的宋梓霞等合作，用最大平均度给出了subcubic重图的星色指数的上界，部分解决了Dvořak等提出的猜想；(J). 与博士生雷辉等合作，研究了有向图的彩虹顶点连通数和全彩虹顶点连通数，刻画了一些上下界；(K). 与韩国的Suil O合作，刻画了给定最大度和最小度的图的Randic指数的紧的界。