# Scaling Up Flag Algebras in Combinatorics ongoing

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.

## đź§‘â€ŤđźŽ“ Project Members

## đźŞ™ Funding

This project is being funded by the Berlin Mathematics Research Center MATH+ (project ID EF1-21), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from October 2022 to September 2025.

## đź”¬ Project Description

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.

## đź’¬ Talks and posters

### Conference and workshop talks

- Jul 2024
*The Four-Color Ramsey Multiplicity of Triangles*by Aldo Kiem

25th ISMP Conference, MontrĂ©al- Jul 2024
*The Four-Color Ramsey Multiplicity of Triangles*by Aldo Kiem

13th DMD Conference, AlcalĂˇ de Henares- Jun 2023
*Towards Flag Algebras in Additive Combinatorics*by Christoph Spiegel

FoCM 2023 Workshop I.3 Workshop, Paris [PDF]- Jun 2023
*The 4-color Ramsey Multiplicity of Triangles*by Aldo Kiem

FoCM 2023 Workshop I.3 Workshop, Paris- May 2023
*Towards Flag Algebras in Additive Combinatorics*by Christoph Spiegel

15th CANT Conference, New York [PDF]

## View More / Less

- Mar 2023
*Computer-assisted Proofs in Extremal Combinatorics*by Christoph Spiegel

Optimization and ML Workshop, Waischenfeld [PDF]- Jan 2023
*Fully Computer-assisted Proof in Extremal Combinatorics*by Christoph Spiegel

Combinatorial Optimization Workshop, Aussois [PDF]- Dec 2022
*Leveraging Combinatorial Symmetries in Flag Algebra-based SDP Formulations*by Christoph Spiegel

Recent Advances in Optimization Workshop, Toronto [PDF]

### Research seminar talks

- Jun 2024
*Categorification of Flag Algebras*by Aldo Kiem

LIMDA Seminar, Barcelona- Feb 2023
*The Four-color Ramsey Multiplicity of Triangles*by Christoph Spiegel

LIMDA Seminar, Barcelona [PDF]- Nov 2022
*Flag Algebras for Edge-colored Graphs*by Aldo Kiem

Research Seminar Combinatorics, Berlin

### Poster presentations

- Jul 2024
*Categorification of Flag Algebras*by Aldo Kiem

13th DMD Conference, AlcalĂˇ de Henares

## đź“ť Publications and preprints

- Kiem, A., Pokutta, S., and Spiegel, C. (2024). Categorification of Flag Algebras.
*Proceedings of Discrete Mathematics Days*. [URL]## [BibTeX]

- Kiem, A., Pokutta, S., and Spiegel, C. (2024). The 4-color Ramsey Multiplicity of Triangles.
*Proceedings of Discrete Mathematics Days*. [URL] [arXiv] [code]## [BibTeX]

- RuĂ©, J. J., and Spiegel, C. (2023). The Rado Multiplicity Problem in Vector Spaces Over Finite Fields.
*Proceedings of European Conference on Combinatorics*. DOI: 10.5817/CZ.MUNI.EUROCOMB23-108 [URL] [arXiv] [code]## [BibTeX]