图分割和标志代数

Graph partitioning problems have wide applications in and are important to extremal combinatorics, optimization, compute science and other fields. Flag algebras is experiencing rapid growth in recent years and plays as a driving force to the development of combinatorics, in particular of extremal combinatorics. The applicant has made many achievements on graph partitioning problems, flag algebras and several other important problems in combinatorics. And this project mainly involves the study on the two major themes of graph partitioning and flag algebra. The research topics includes: the norm problem in graph partitioning, Bollobas-Scott conjecture on bisections, Caccetta-Haggkvist conjecture, Seymour-Jackson conjecture on Eulerian digraphs, and Erdos conjecture on triangle-free graphs.

图分割问题，在极值组合、优化和计算机科学等领域中有广泛的应用和重要的影响。标志代数，作为近年来蓬勃发展的一门新兴理论，对组合特别是极值组合的发展有着巨大的推动力。申请者已经在包括这两大领域在内的一些推动学科发展的重要问题上，得到了不少重大创新成果。本项目主要围绕着图分割和标志代数这两大主题开展研究。其研究内容包括：图分割范数问题，关于平分划分的Bollobas-Scott猜想，Caccetta-Haggkvist猜想，欧拉有向图的Seymour-Jackson猜想以及无三角形图的Erdos猜想。

本项目主要研究了关于图的分割问题，标识代数等图论中的重要问题，通过研究我们取得了一系列结果，包括：我们证明了Bollobas and Scott提出的关于图平分划分的猜想，进一步我们还证明了这个猜想对任意k-划分都是正确的；证明了Scott关于图分割的范数问题；证明了关于Turan数和染色推广Turan数之间关系的Keevash-Sudakov猜想对一个无穷图集成立，得到了这个猜想目前最好的结果，并且还得到了当这个猜想成立时对应的染色是唯一的；推广了众所周知的完全二部图的Turan数的结果到完全r部r一致超图，提供了一种利用随机代数的方法构造非退化的特殊的图（超图）来解决一系列Turan类问题的想法；证明了关于Thomassen在1983年提出的关于最小顶点度较大的图中的圈长的猜想当k是偶数时，猜想成立，当k是奇数且将最小顶点度满足的条件改为“大于等于k+4”时猜想成立；关于Verstraete的关于超图的圈长问题，发展了一种新的方法来研究超图中的圈长问题，证明了每个平均顶点度大于等于7r(k + 1)的r-一致线性超图都包含k条连续长度的Berge圈；证明了对最小度k和最长圈长度c满足条件10 ≤ c < n且e(G) > max{f(n, k +1, c), f(n, ⌊2c⌋ - 1, c)}的n的顶点的二连通图的Turan类问题的结果进行了优化，并且得到了一个稳定性的结论。.除上述主要结果外，我们还得到了包括图染色在内的其他结果。在本项目的支持下，一共在国际组合数学顶级期刊Combinatorica，JCTB，JCTA等数学期刊上发表学术论文11篇。