旗代数理论与图划分问题

Graph partition problems ask for paritions with certain properties. For exmaple, Max Cut problem is NP-complete, asks for the largest bipartite subgraph of a graph G. This question was raised 50 years ago by Erdős and has been the subject of extensive research. For triangle-free graph, Erdős asked how many edges needed to be deleted to make a triangle-free graph bipartite. Erdős also asked a related question. Determine the number e such that any triangle-free graph on n vertices should contain a set of n/2 vertices that span e edges. These two questions attracted a lot of attention, however the best known results were from more than 20 years ago. Flag Algebra was invented by Prof Razborov from University of Chicago in 2007. And Razborov was awarded Robbins prize in 2013 for introducing this powerful new method to solve problems in extremal combinatorics. So far Flag algebra have not been applied to partition problems. Applicant has used Flag algebra method to attack Turán type problems and graph coloring extremal problems. Applicant has also developed method to use Flag algebra to attack problems that Flag algebra itself cannot deal with, for example when extremal structures are not unique. This project will develop new methods which together with Flag algebra method can be used to attack graph partition problems and make progress on the above questions.

图划分问题研究图上满足一定性质的划分。如最大割问题研究图的二划分使割边最多，最早由Erdős在50年前提出，之后一直是极值图论中的热点问题。旗代数是2007年由芝加哥大学Razborov教授创造的理论，通过编程计算来研究图中的不等式，用电脑来优化已有的研究方法。这个理论已被用于解决了图论领域几个大的猜想，并被应用于研究极值组合中的多种问题，但还未能用于图划分问题。本课题拟研究新的方法，以拓展旗代数理论来描述及研究图划分问题。同时本课题拟分析图划分问题的已有研究方法，研究如何将这些方法归入旗代数理论，从而可用电脑来实现及最优化这些方法。本课题将以此来研究Erdős提出的不含三角形的图的最大割问题和局部密度问题，即最少删除多少条边后可保证变成二部图，及最少删除多少条边后可把点集分成相等的两部分且其中一个为独立集。

图划分问题研究图上满足一定性质的划分。如最大割问题研究图的二划分使割边最多，最早由Erdos在50年前提出，是NP完全问题，也一直是极值图论中的热点问题。旗代数是2007年由芝加哥大学Razborov教授创造的理论，通过半正定规划来研究图中的不等式，用电脑辅助计算来优化已有的研究方法。这个理论已被用于解决了图论领域几个大的猜想，并被应用于研究极值组合中的多种问题，但还未能用于图划分问题。本课题研究了新的方法，将旗代数理论扩展来描述及研究图划分问题。本课题以此研究了Erdos提出的不含三角形的图的最大割问题，即最少删除多少条边后可保证变成二部图，并对相关问题给出了解。本课题还研究了有向图何时有最多的诱导星图问题。