若干极图问题研究

As a vibrating branch of graph theory born in the mid last century, the theory of extremal graphs concerns the problem of those with certain properties and the relation between the global property and the local structure of graphs, i.e. the structure of subgraphs etc. In recent decades, the theory has become a very active branch in graph theory since it is gradually systemized and new research tools have been developed. Not only is its theory an important foundation of modern graph theory, but the involved research tools and methods have been successfully applied to many other mathematical branches and even to theoretical computer sciences. For instance, the Szemerédi regularity lemma has been used proving and to prove many vital conjectures on extremal problems, including the long standing conjecture of existing arbitrarily long arithmetic prime progressions proven by the 2006 Fields medalist Terence Tao and the 2007 Sastra Ramanujan Prize winner Ben Green, and the Erdös probabilistic method stemed from the extremal graph theory has widely been applied to many other areas, such as analysis of algorithms and complexities etc. This project will focus on several most important problems that are widely concerned in the theory of extremal graphs.

极值图论是图论极具生命力的重要分支之一，诞生于上世纪中叶，主要研究满足某种性质的极图问题，以及图的整体性质如何影响图的局部子结构，即子图结构等相关问题。近半个世纪以来，由于其理论的不断系统化和研究工具的不断创新，使得极值图论发展成为图论中一个非常活跃的分支。她不仅是现代图论的重要理论基础，而且其所蕴含的研究工具和方法也已成功地运用到了其它数学学科甚至理论计算机科学，如：Szemerédi正则引理被成功地应用于解决众多关于极值问题的猜想，其中包括2006年获Fields奖的陶哲轩与2007年荣获Sastra Ramanujan奖的Green合作完成关于存在任意长等差素数列猜想的证明；以及Erdös概率方法也早已跨出图论甚至组合数学的范围而在理论计算机科学和复杂性分析等学科中大放异彩等。本项目将致力于研究极值图论中的几个相当重要的热点问题。

本项目深入研究了极值图论中的几个重要的热点问题。图上测地圈是微分几何相同概念的离散化，与Gromov双曲度有密切联系，而Gromov双曲度可以理解为图与树状结构的近似程度，所以随机图上测地圈的研究对图结构的了解很重要。我们将Benjamini等人在2011年得到的随机正则图测地圈的性质推广到了一般随机图上，论文发表在Discrete Mathematics上。著名的双圈覆盖猜想与很多重要猜想都有关系，如：Berge和Fulkerson的匹配猜想、Jaeger和Tarsi的最短圈覆盖猜想与Tutte的流猜想等。我们从极图的角度在允许负边存在的情况下，利用Jaeger的八流定理和Seymour的六流定理证明了符号双圈覆盖的存在性并提出了一个符号双圈覆盖猜想，论文发表在The Electronic Journal of Combinatorics上。对化学拓扑Hosoya 指数、Merrifield-Simmons指数和Randic指数我们研究了其在连通图上的情况，给出了固定边数连通图上的指标的紧估计。对给定阶和边数的连通图，我们也补充了部分结果。这些结果既有数学理论意义又有潜在的化学应用价值，论文发表在Journal of Mathematical Chemistry上。图同态的计数有着丰富的历史和重要的应用，我们获得了路到路、树到树等一系列与极值有关的结果，研究论文发表在Rocky Mountain Journal of Mathematics上。置换中最长递增子列的长度分布问题一直受到人们关注，著名数学家Deft等作出过重要结果，我们在以231为禁模式的对合中最长递增子列的长度分布问题取得了进展。我们在具有极小discrepancy的组合矩形的计数理论方面的工作也获得接受。