Collaborative Research: Flag Algebra Methods

Iowa State University, Ames IA

Investigators

Abstract

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.