**Project Heads**

Sebastian Pokutta, Christoph Spiegel

**Project Members**

Aldo Kiem

**Project Duration**

01.01.2023 − 31.12.2025

**Located at**

ZIB

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.

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.

**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.