Scaling Up Flag Algebras in Combinatorics ongoing

Computers have always been an important tool for mathematicians to conjecture, prove and verify mathematical statements. The use of computer assistance has been particularly fruitful in Extremal Combinatorics, where the most formalized and successful approach is an application of flag algebras, allowing one to establish bounds on certain problems through Semidefinite Programming (SDP). Razborov introduced the notion of flag algebras in 200, citing both Bondy’s work on the Caccetta-Häggkvist conjecture as well as Lovász and Szegedy’s work on graph limits as inspiration. He famously used flag algebras as a purely theoretical framework to establish the exact relation of triangle and edge density in graphs. As a computational framework, the main observation consists of observing that and underlying combinatorial optimization problem is equivalent to a (dual) conic optimization problem. Sums of squares (SOS) are used as a computationally feasible relaxation of this conic optimization problem that results in an SDP formulation. The density computations and the size of the SDP scale with the order of the squares where larger orders give better bounds but also result in quickly growing computational costs.

Figure. A flag algebra formulation of the asymptotic lower bound on the number of monochromatic triangles in two-colorings of the complete graph originally formualted by Goodman in 1959.

Many long-standing conjectures were resolved through this method, such as proving a conjecture of Erdős by determining the maximum number of 5-cycles in triangle-free graphs, and progress has been made on others, most notably Turán’s Conjecture about the maximum edge density of 3-uniform hypergraphs without 4-cliques. The theoretical framework was also extended to derive additional results from the generated information, such as the stability of extremal constructions. Existing applications have however largely been limited to a personal computing context.

This project aims to both improve the underlying computational aspects in order to scale up the flag algebra calculus for existing problems and theories and to open up new areas of application of the SDP-based flag approach. We have made first steps towards both steps with recent publications and are actively developing a software framework enabling other researchers to use the resulting tools.