Collaborative Research: Flag Algebra and Its Applications

Iowa State University, Ames IA

Investigators

Abstract

Extremal graph theory studies properties of very large networks. Especially with the advent of interest in big data, such networks appear in a host of very important applications. In this project, the researchers focus on the density of small substructures appearing in large networks. The goal is to further develop a powerful method based on semidefinite programming, allowing its application to more complicated structures and longstanding problems in the field. The project involves undergraduate and graduate students. Open-source software under development in the project will be made readily available to other researchers. This research project aims to extend and develop the flag algebra method to new models in order to solve longstanding open problems, principally in extremal combinatorics. In prior work, the investigators and collaborators created a stability method and a blow-up technique using flag algebras. The stability method can be applied to solve problems, previously impervious to attack, where the extremal construction has an iterative structure. The blow-up technique translates questions on small graphs into the language of graph limits accessible to flag algebras, building bridges from one area of graph theory to another. This project will develop these techniques further for application to a number of important topics, including crossing numbers and small Ramsey numbers. It is expected that the work will draw on tools from linear and nonlinear programming to obtain exact results. The investigators will involve graduate students at their schools in the project and will work with graduate students from other schools during annual workshops.