Collaborative Research: Flag Algebra Methods

图极限是最近发展起来的一个概念，用于研究可用于模拟大型网络的大型图。它们将分析和图论中的概念结合在一起。开发了不同的语言来提供关于大图中的小子图的数量的统计。特别是，这个项目利用了拉兹博罗夫开发的被称为旗帜代数的机器。这一机制在解决许多长期悬而未决的猜测方面非常有效。这些应用程序通常是计算机辅助的，这使得可以构造以前不可能的大小的证明。该项目涉及研究生和本科生。本课题所开发的软件对其他研究人员也具有一定的借鉴意义。本课题的主要研究课题是推广旗代数方法的应用。这些方法是由Razborov开发的，目的是解决一些长期悬而未决的问题。特别地，将Turan定理推广到3-一致超图。在某些情况下，这些方法的应用相当简单。然而，在具有迭代极值结构的应用中，所得到的结果通常是不精确的，需要额外的工作。在之前的工作中，研究人员和他们的合作者开发了处理迭代构造的方法。这个问题的一个例子是最大化图中诱导5-圈的数目的问题。在这个项目中，研究人员将进一步开发这些方法。迭代结构出现在许多环境中，例如在Ramsey理论中的多项式到指数转换中。该项目的另一个方向是将该方法扩展到小图形。在之前的工作中，调查人员已经将这样的想法应用于Ramsey数和鄂尔多斯的五角大楼问题。调查人员将改进这些方法，并将其应用于其他情况。研究生将被纳入研究项目，研究人员将继续支持一年一度的组合学研究生研究研讨会。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graph limits are a recent concept developed to study large graphs which can be used to simulate large networks. They bring together concepts from analysis and graph theory. Different languages were developed to provide statistics about the number of small subgraphs in large graphs. In particular, this project utilizes the machinery developed by Razborov called flag algebra. This machinery has been very effective in resolving many long standing open conjectures. The applications are usually computer assisted, which allows to construct proofs of a size impossible before. The project involves graduate and undergraduate students. The software developed during this project will be available to other researchers.The main topic of the research in this project is to extend the applications of flag algebra methods. These methods were developed by Razborov to attack a number of long standing open problems. In particular, the extension of Turan's Theorem to 3-uniform hypergraphs. In some cases, the application of the methods is quite straightforward. However, in applications with iterated extremal structure, the obtained result is usually not exact and additional work is needed. In prior work, the investigators and their collaborators developed methods for dealing with iterated constructions. An example of this problem is the question to maximize the number of induced 5-cycles in a graph. In this project the investigators will further develop these methods. Iterated structures appear in many contexts, for example in the polynomial to exponential transition in Ramsey theory. Another direction of the project is to extend the method to small graphs. In prior work, the investigators have applied such ideas to Ramsey numbers and to Erdos' Pentagon problem. The investigators will refine these methods and apply them in other contexts. Graduate students will be included in the research projects and the investigators will continue to support the annual graduate research workshop in combinatorics.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.