Project
EF1-21
Scaling up Flag Algebras in Combinatorics
Project Heads
Sebastian Pokutta, Christoph Spiegel
Project Members
Aldo Kiem
Project Duration
01.01.2023 − 31.12.2025
Located at
ZIB
Short Summary
This project aims to obtain new bounds in Extremal Combinatorics through an application of flag algebras. The goal is to both improve the underlying computational aspects for existing problems as well as to further develop the theory of flag algebras to extend it to new areas of application.
Background
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.
Goals
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.
Related Publications
- Rué Perna, J. J., and Spiegel, C. (2023). The Rado Multiplicity Problem in Vector Spaces Over Finite Fields. Proceedings of European Conference on Combinatorics. Paper available as arXiv:2304.00400.
- Kiem, A., Pokutta, S., and Spiegel, C. (2023). The Four-Color Ramsey Multiplicity of Triangles. In preparation.
Software Repositories
- The code accompanying arXiv:2304.00400 is available at github.com/FordUniver/rs_radomult_23.
- We are currently developing zaszlokat, a modern, fast, and accessible software framework for general Flag Algebra calculus expected to be available by the end of 2023.