Collaborative Research: Flag Algebra and Semidefinite Programming

Extremal combinatorics seeks to identify and characterize optimal objects within a given class, revealing rich mathematical structure with connections across many areas. Over the past two decades, computer-assisted methods have transformed the field, most notably Razborov's flag algebra framework (2007), which translates extremal problems into semidefinite programs that can be solved using modern optimization software. This versatile approach has led to breakthroughs on longstanding open problems in graphs, hypergraphs, permutations, oriented graphs, point sets, embedded graphs, and phylogenetic trees. Despite being introduced nearly twenty years ago, the community is still working on understanding and extending the method. The PIs will advance the flag algebra method by extending it to new models and developing new techniques to tackle longstanding open problems in extremal combinatorics. Building on their previous work, they have introduced a stability method for extremal constructions with iterative structure, a blow-up technique connecting local graph structure with graph limits, and adaptations that make flag algebra methods effective even for small graphs, leading to results such as the solution of Erdős' pentagon conjecture and the computation of small Ramsey numbers. They plan to further develop these techniques and make them more applicable to other problems. The PIs expect that the proposed objectives will draw on tools from linear and nonlinear programming to obtain exact results. Additionally, the PIs plan to work with graduate students at their schools as well as graduate students from other schools during annual workshops co-organized by the PIs. 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.