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

Christoph Spiegel
Principal Investigator
spiegel (at) zib.de
Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de
Aldo Kiem
kiem (at) zib.de
Olivia Röhrig
roehrig (at) zib.de

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

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.

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

  1. Kiem, A., Pokutta, S., and Spiegel, C. (2024). Categorification of Flag Algebras. Proceedings of Discrete Mathematics Days. [URL]
    [BibTeX]
    @inproceedings{kps_flagalgebracategory_24,
      year = {2024},
      booktitle = {Proceedings of Discrete Mathematics Days},
      url = {https://dmd2024.web.uah.es/files/abstracts/paper_47.pdf},
      author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph},
      title = {Categorification of Flag Algebras}
    }
  2. Kiem, A., Pokutta, S., and Spiegel, C. (2024). The 4-color Ramsey Multiplicity of Triangles. Proceedings of Discrete Mathematics Days. [URL] [arXiv] [code]
    [BibTeX]
    @inproceedings{kps_flagalgebrasymmetries_22,
      year = {2024},
      booktitle = {Proceedings of Discrete Mathematics Days},
      url = {https://dmd2024.web.uah.es/files/abstracts/paper_3.pdf},
      archiveprefix = {arXiv},
      eprint = {2312.08049},
      primaryclass = {math.CO},
      author = {Kiem, Aldo and Pokutta, Sebastian and Spiegel, Christoph},
      title = {The 4-color Ramsey Multiplicity of Triangles},
      code = {https://github.com/FordUniver/kps_trianglemult}
    }
  3. 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]
    @inproceedings{rs_radomult_23,
      year = {2023},
      booktitle = {Proceedings of European Conference on Combinatorics},
      doi = {10.5817/CZ.MUNI.EUROCOMB23-108},
      url = {https://journals.muni.cz/eurocomb/article/view/35642},
      archiveprefix = {arXiv},
      eprint = {2304.00400},
      primaryclass = {math.CO},
      author = {Rué, Juan José and Spiegel, Christoph},
      title = {The Rado Multiplicity Problem in Vector Spaces Over Finite Fields},
      code = {https://github.com/FordUniver/rs_radomult_23}
    }