Learning Extremal Structures in Combinatorics completed

Extremal Combinatorics focuses on the maximum or minimum sizes of discrete structures with specific properties, posing significant challenges due to their complexity. Traditional computational approaches often fail due to exponential growth in search spaces, but recent AI advancements, especially in Reinforcement Learning, offer new potential. Applying these AI methods could provide insights into combinatorial problems while also enhancing the understanding of AI techniques in complex, sparse reward environments.

MATH+ EF1-12
Jan 2021 to May 2024
4
13

🧑‍🎓 Project Members

Sebastian Pokutta
Principal Investigator
pokutta (at) zib.de
Tibor SzabĂł
Principal Investigator
szabo (at) math.fu-berlin.de
Christoph Spiegel
spiegel (at) zib.de
Olaf Parczyk
parczyk (at) zib.de

🪙 Funding

This project was being funded by the Berlin Mathematics Research Center MATH+ (project ID EF1-12), itself funded by the German Research Foundation (DFG) under Germany's Excellence Strategy (EXC-2046/1, project ID 390685689) from January 2021 to May 2024.

🔬 Project Description

The field of Extremal Combinatorics is concerned with the largest or smallest possible size of discrete structures satisfying some, usually highly structured and regular, properties. The dynamic underlying these problems, despite being well-structured, is incredibly complicated and understanding such complex systems is a major challenge for contemporary Mathematics. Often even a simple probabilistic argument provides a good or even the best known lower bound.

It is natural to try computational approaches in order to gain insights into the nature of these problems. However, in most cases a straight-forward exhaustive search on small examples will very quickly fall into the trap of combinatorial chaos as the search space grows exponentially. Often one small instance can be handled by hand, while the next larger is already out of reach even on modern computers. The right computational approach can however gain insights on problems in Extremal Combinatorics: the most notable example is Razborov’s introduction of Flag Algebras.

We intend to study the applicability of recent incredible advancement in Artificial Intelligence to problems from Extremal Combinatorics. Machine Learning algorithms are solving tasks that were unthinkable up until recently. Many of these tasks, such as recent advancements in the game of Go, can be described as combinatorial problems whose complexity originates from simple rules. Applying these methods to Extremal Combinatorics is a largely untapped field and we are studying to what degree techniques coming from Reinforcement Learning can be used to tame the combinatorial chaos. Results stemming from this research likewise also have the potential to reflect back on the area of Machine Learning: combinatorial problems can provide challenging environments to study the efficacy of different methods and to see how they handle complex environments with a sparse rewards structure.

đź’¬ Talks and posters

Conference and workshop talks

Oct 2024
Extending the Continuum of Six-Colorings by Christoph Spiegel
41st Kolloquium ĂĽber Kombinatorik (KolKom), Heidelberg [PDF]
Jul 2024
Extending the Continuum of Six-Colorings by Christoph Spiegel
13th Discrete Mathematics Days (DMD), Alcalá de Henares [PDF]
May 2024
On the Maximum Diameter of D-dimensional Simplicial Complexes by Silas Rathke
Berlin-Poznań-Hamburg-Warsaw Seminar, Berlin
Dec 2023
New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
45th Australasian Combinatorics Conference (ACC), Perth
Jun 2023
New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
FoCM 2023 Workshop I.3: Graph Theory and Combinatorics, Paris
May 2023
New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
Berlin-Poznań-Hamburg-Warsaw Seminar, Hamburg
Mar 2023
Computer-assisted Proofs in Extremal Combinatorics by Christoph Spiegel
Workshop on Optimization and Machine Learning, Waischenfeld [PDF]
Feb 2023
Fully Computer-assisted Proofs in Extremal Combinatorics by Christoph Spiegel
37th AAAI Conference on Artificial Intelligence (AAAI), Washington, DC [PDF]
Sep 2022
Proofs in Extremal Combinatorics Through Optimization by Christoph Spiegel
6th ZIB-IMI-ISM-NUS-RIKEN-MODAL Workshop, Tokyo / Fukuoka [PDF]
Sep 2022
New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
DMV Annual Meeting, Berlin
Aug 2022
New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
20th RS&A Conference, Gniezno
Jul 2022
New Ramsey Multiplicity Bounds and Search Heuristics by Christoph Spiegel
12th Discrete Mathematics Days (DMD), Santander [PDF]
Jun 2022
New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
Third Southwestern German Workshop on Graph Theory, Heidelberg

Research seminar talks

Dec 2024
Coloring the Plane with Neural Networks by Christoph Spiegel
Research Seminar Combinatorics, Berlin [PDF]
Jun 2024
On the Maximum Diameter of D-dimensional Simplicial Complexes by Silas Rathke
Mittagsseminar Discrete Mathematics, Berlin
May 2024
New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
Research seminar in Discrete Mathematics [video]
Mar 2024
New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
Atlanta Lecture Series Combinatorics and Graph Theory XXVIII, Atlanta
Feb 2024
Maximal Diameter of Simplicial D-complexes by Olaf Parczyk
Seminar on Combinatorics, Games and Optimisation, London
Nov 2023
New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
Seminar on Discrete Mathematics at Adam Mickiewicz University, Poznan
Apr 2022
New Ramsey Multiplicity Bounds and Search Heuristics by Christoph Spiegel
LIMDA Seminar, Barcelona

Poster presentations

Mar 2023
A Fully Computer-assisted Proof in Extremal Combinatorics by Christoph Spiegel
Workshop on Optimization and Machine Learning, Waischenfeld [PDF]
Feb 2023
A Fully Computer-assisted Proof in Extremal Combinatorics by Christoph Spiegel
37th AAAI Conference on Artificial Intelligence (AAAI), Washington, DC [PDF]

đź“ť Publications and preprints

  1. Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2024). New Ramsey Multiplicity Bounds and Search Heuristics. Foundations of Computational Mathematics. DOI: 10.1007/s10208-024-09675-6 [arXiv] [code]
    [BibTeX]
    @article{2022_ParczykPokuttaSpiegelSzabo_Ramseymultiplicityheuristics,
  year = {2024},
  journal = {Foundations of Computational Mathematics},
  doi = {10.1007/s10208-024-09675-6},
  archiveprefix = {arXiv},
  eprint = {2206.04036},
  primaryclass = {math.CO},
  author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and SzabĂł, Tibor},
  title = {New Ramsey Multiplicity Bounds and Search Heuristics},
  code = {https://zenodo.org/record/6602512#.YyvFhi8Rr5g}
}
  2. Kiem, A., Pokutta, S., and Spiegel, C. (2024). The Four-color Ramsey Multiplicity of Triangles. Proceedings of the Discrete Mathematics Days. [URL] [arXiv] [code]
    [BibTeX]
    @inproceedings{2023_KiemPokuttaSpiegel_4colorramsey,
  year = {2024},
  booktitle = {Proceedings of the 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 Four-color Ramsey Multiplicity of Triangles},
  code = {https://github.com/FordUniver/kps_trianglemult}
}
  3. Díaz, A. E., Gupta, P., Cecchelli, D. M., Parczyk, O., and Sgueglia, A. (2024). Dirac’s Theorem for Graphs of Bounded Bandwidth. [arXiv]
    [BibTeX]
    @misc{2024_AlbertoEtAl_Diractheorembandwidth,
  archiveprefix = {arXiv},
  eprint = {2407.05889},
  primaryclass = {math.CO},
  year = {2024},
  author = {Díaz, Alberto Espuny and Gupta, Pranshu and Cecchelli, Domenico Mergoni and Parczyk, Olaf and Sgueglia, Amédeo},
  title = {Dirac's Theorem for Graphs of Bounded Bandwidth}
}
  4. Böttcher, J., Sgueglia, A., Skokan, J., and Parczyk, O. (2024). The Square of a Hamilton Cycle in Randomly Perturbed Graphs. Random Structures & Algorithms, 65(2), 342–368. DOI: 10.1002/rsa.21215 [arXiv]
    [BibTeX]
    @article{2024_BoettcherAmedeoJozefParczyk_Hamiltoncycleperturbation,
  year = {2024},
  journal = {Random Structures & Algorithms},
  volume = {65},
  number = {2},
  pages = {342-368},
  doi = {10.1002/rsa.21215},
  archiveprefix = {arXiv},
  eprint = {2202.05215},
  primaryclass = {math.CO},
  author = {Böttcher, Julia and Sgueglia, Amédeo and Skokan, Jozef and Parczyk, Olaf},
  title = {The Square of a Hamilton Cycle in Randomly Perturbed Graphs}
}
  5. Illingworth, F., Lang, R., MĂĽyesser, A., Parczyk, O., and Sgueglia, A. (2024). Spanning Spheres in Dirac Hypergraphs. [arXiv]
    [BibTeX]
    @misc{2024_FreddieEtAl_Spanningspheresdirac,
  archiveprefix = {arXiv},
  eprint = {2407.06275},
  primaryclass = {math.CO},
  year = {2024},
  author = {Illingworth, Freddie and Lang, Richard and Müyesser, Alp and Parczyk, Olaf and Sgueglia, Amédeo},
  title = {Spanning Spheres in Dirac Hypergraphs}
}
  6. Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Geombinatorics Quarterly, XXXIV. [URL] [arXiv]
    [BibTeX]
    @article{2024_MundingerPokuttaSpiegelZimmer_SixcoloringsExpansion,
  year = {2024},
  journal = {Geombinatorics Quarterly},
  volume = {XXXIV},
  url = {https://geombina.uccs.edu/past-issues/volume-xxxiv},
  archiveprefix = {arXiv},
  eprint = {2404.05509},
  primaryclass = {math.CO},
  author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max},
  title = {Extending the Continuum of Six-Colorings}
}
  7. Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Proceedings of the Discrete Mathematics Days. [URL] [arXiv]
    [BibTeX]
    @inproceedings{2024_MundingerPokuttaSpiegelZimmer_SixcoloringsExpansion:1,
  year = {2024},
  booktitle = {Proceedings of the Discrete Mathematics Days},
  url = {https://dmd2024.web.uah.es/files/abstracts/paper_27.pdf},
  archiveprefix = {arXiv},
  eprint = {2404.05509},
  primaryclass = {math.CO},
  author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max},
  title = {Extending the Continuum of Six-Colorings}
}
  8. Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2023). Fully Computer-assisted Proofs in Extremal Combinatorics. Proceedings of the AAAI Conference on Artificial Intelligence. DOI: 10.1609/aaai.v37i10.26470 [URL] [arXiv] [code]
    [BibTeX]
    @inproceedings{2022_ParczykPokuttaSpiegelSzabo_Ramseymultiplicityheuristics:1,
  year = {2023},
  booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence},
  doi = {10.1609/aaai.v37i10.26470},
  url = {https://ojs.aaai.org/index.php/AAAI/article/view/26470},
  archiveprefix = {arXiv},
  eprint = {2206.04036},
  primaryclass = {math.CO},
  author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and SzabĂł, Tibor},
  title = {Fully Computer-assisted Proofs in Extremal Combinatorics},
  code = {https://zenodo.org/record/6602512#.YyvFhi8Rr5g}
}
  9. Böttcher, J., Frankl, N., Cecchelli, D. M., Skokan, J., and Parczyk, O. (2023). Graphs with Large Minimum Degree and No Small Odd Cycles Are 3-colourable. [arXiv]
    [BibTeX]
    @misc{2023_BoettcherEtAl_Graphs3colourable,
  archiveprefix = {arXiv},
  eprint = {2302.01875},
  primaryclass = {math.CO},
  year = {2023},
  author = {Böttcher, Julia and Frankl, Nóra and Cecchelli, Domenico Mergoni and Skokan, Jozef and Parczyk, Olaf},
  title = {Graphs with Large Minimum Degree and No Small Odd Cycles Are 3-colourable}
}
  10. Mattos, L., Cecchelli, D. M., and Parczyk, O. (2023). On Product Schur Triples in the Integers. [arXiv]
    [BibTeX]
    @misc{2023_MattosDomenicoParczyk_Productschurtriples,
  archiveprefix = {arXiv},
  eprint = {2311.18796},
  primaryclass = {math.CO},
  year = {2023},
  author = {Mattos, LetĂ­cia and Cecchelli, Domenico Mergoni and Parczyk, Olaf},
  title = {On Product Schur Triples in the Integers}
}
  11. Rué, J. J., and Spiegel, C. (2023). The Rado Multiplicity Problem in Vector Spaces Over Finite Fields. Proceedings of the European Conference on Combinatorics, Graph Theory and Applications. DOI: 10.5817/CZ.MUNI.EUROCOMB23-108 [URL] [arXiv] [code]
    [BibTeX]
    @inproceedings{2023_RueSpiegel_Radomultiplicity,
  year = {2023},
  booktitle = {Proceedings of the European Conference on Combinatorics, Graph Theory and Applications},
  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}
}
  12. Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2022). New Ramsey Multiplicity Bounds and Search Heuristics. Proceedings of the Discrete Mathematics Days. [arXiv] [code]
    [BibTeX]
    @inproceedings{2022_ParczykPokuttaSpiegelSzabo_Ramseymultiplicityheuristics:2,
  year = {2022},
  booktitle = {Proceedings of the Discrete Mathematics Days},
  archiveprefix = {arXiv},
  eprint = {2206.04036},
  primaryclass = {math.CO},
  author = {Parczyk, Olaf and Pokutta, Sebastian and Spiegel, Christoph and SzabĂł, Tibor},
  title = {New Ramsey Multiplicity Bounds and Search Heuristics},
  code = {https://zenodo.org/record/6602512#.YyvFhi8Rr5g}
}
  13. Böttcher, J., Sgueglia, A., Skokan, J., and Parczyk, O. (2021). The Square of a Hamilton Cycle in Randomly Perturbed Graphs. Proceedings of the European Conference on Combinatorics, Graph Theory and Applications, 14, 644–650. DOI: 10.1007/978-3-030-83823-2_103 [arXiv]
    [BibTeX]
    @inproceedings{2024_BoettcherAmedeoJozefParczyk_Hamiltoncycleperturbation:1,
  year = {2021},
  booktitle = {Proceedings of the European Conference on Combinatorics, Graph Theory and Applications},
  volume = {14},
  pages = {644-650},
  doi = {10.1007/978-3-030-83823-2_103},
  archiveprefix = {arXiv},
  eprint = {2202.05215},
  primaryclass = {math.CO},
  author = {Böttcher, Julia and Sgueglia, Amédeo and Skokan, Jozef and Parczyk, Olaf},
  title = {The Square of a Hamilton Cycle in Randomly Perturbed Graphs}
}