Collaborative Research: Flag Algebra Methods

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

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.