具有禁用子图结构的图和超图的极值问题研究

Extremal graph theory is one of core research fields in combinatorics and graph theory. Due to the profound results and relevant methods, the research on extremal problems has attracted much attention and it becomes one of the most important topics in combinatorics. Extremal graph theory has many applications in coding theory, discrete geometry, theoretical computer science. In this project, we will discuss extremal problems of Turán type of graphs, extremal problems of Turán type of hypergraphs, extremal problems for p-spectral radius of hypergraphs. We will focus on matching conjecture proposed by Erdős, open problems on extremal function of expansion of a graph with tree-width at most 2, extremal function of expansion of a planar graph with an acyclic 3-coloring proposed by Kostochka and an open problem on lower bound of spectral radius of r-uniform hypergraphs proposed by Nikiforov. By using analytic methods, algebraic methods, probabilistic methods and tensor theory, we shall work on these problems. This project involves in transversal, matching, coloring and spectral of graphs and hypergraphs. Our aim is to solve or partly solve these problems. Meanwhile, we will find some new and effective methods and theories.

极值图论是组合图论中的核心研究内容之一，由于结果的深刻性以及从中发展出来的理论方法使得极值图论成为一个重要的研究领域，其在编码理论、离散几何和计算机科学等领域有广泛的应用。本课题将研究带有禁用子图结构的Turán类型极值问题,以图的扩张为禁用子超图的超图极值问题和超图的p-谱半径的极值等问题，给出这些问题的极值数并刻画相应的极图。我们将围绕著名学者Erdős关于匹配扩张的极值数猜想、Kostochka关于树宽不超过2的图的扩张、无圈3-染色平面图扩张的极值数的两个公开问题和Nikiforov提出的关于一致超图的谱半径下界的公开问题等开展工作，运用组合构造方法、优化方法、代数方法、随机方法和张量理论等对这些问题进行研究。研究内容涉及图和超图的横贯、匹配、染色、谱半径等重要结构参数。该项目的研究目标是对这些问题和猜想有实质性的推进,同时我们也将探索一些新的理论和方法。

极值组合是组合学中最重要的研究领域之一，其在编码理论、离散几何、理论计算机科学等领域有广泛的应用。本课题研究了具有禁用子图结构的Turán类型极值问题，图的谱Turán型极值问题和超图的邻接谱半径问题。我们研究了Berge-K4超图的极值问题，给出了Berge-K4超图的极值数和极值图。研究了超图的反-Ramsey数问题，确定了k-匹配在r-部r-一致完全超图上的反-Ramsey数的准确值，并确定了唯一的极值染色。研究了超图的邻接谱半径问题，否定了Nikiforov在2014年提出的一致超图的关于2-section的一个猜想，同时我们给出了用点度和co-度表示的超图的邻接张量和无符号拉普拉斯张量谱半径的上界，并刻画了取得上界的极图。研究了图的谱Turán型极值问题，彻底证明了知名学者Cioabă等人提出的关于图的谱Turán型极值问题的一个猜想，并且得到了比此猜想更强的结果。这些研究成果推进了文献中已有的相关工作,研究成果以学术论文地形式呈现。在国际重要期刊《Journal of Combinatorial Theory, Series B》、《Discrete Mathematics》、《Discrete Applied Mathematics》、《Journal of Combinatorial Optimization》、《The Electronic Journal of Combinatorics》、《Linear and Multilinear Algebra》、《Linear Algebra and its Applications》等发表学术论文26篇。其中在组合图论的顶级期刊《Journal of Combinatorial Theory, Series B》上发表学术论文1篇。