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.
🧑‍🎓 Project Members
🪙 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
- Jul 2024
- Extending the Continuum of Six-Colorings by Christoph Spiegel
13th DMD Conference, Alcalá de Henares [PDF] - Jun 2024
- On the Maximum Diameter of D-dimensional Simplicial Complexes by Silas Rathke
Mittagsseminar Discrete Mathematics, Berlin - May 2024
- On the Maximum Diameter of D-dimensional Simplicial Complexes by Silas Rathke
Berlin-Poznań Seminar, Berlin - Dec 2023
- New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
45th Australasian Combinatorics Conference, Perth - Jun 2023
- New Ramsey Multiplicity Bounds and Search Heuristics by Olaf Parczyk
FoCM 2023 Workshop I.3 Workshop, Paris
View More / Less
- May 2023
- New Ramsey Multiplicity Bounds and Search Heuristics by Tibor SzabĂł
Berlin-Poznań Seminar, Hamburg - Mar 2023
- Computer-assisted Proofs in Extremal Combinatorics by Christoph Spiegel
Optimization and ML Workshop, Waischenfeld [PDF] - Feb 2023
- Fully Computer-assisted Proofs in Extremal Combinatorics by Christoph Spiegel
37th AAAI Conference, Washington, DC [PDF] - Sep 2022
- Proofs in Extremal Combinatorics Through Optimization by Christoph Spiegel
6th 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 DMD Conference, 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
- 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 and PhD 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
đź“ť Publications and preprints
- 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{hamilton_cycle_2021, year = {2024}, journal = {Random Structures & Algorithms}, volume = {65}, number = {2}, pages = {342-368}, doi = {10.1002/rsa.21215}, archiveprefix = {arXiv}, eprint = {2202.05215}, author = {Böttcher, Julia and Sgueglia, Amedeo and Skokan, Jozef and Parczyk, Olaf}, title = {The Square of a Hamilton Cycle in Randomly Perturbed Graphs} }
- 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} }
- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Geombinatorics Quarterly, XXXIV.
[URL]
[arXiv]
[BibTeX]
@article{mpsz_hadwigernelsonspectrum_24, year = {2024}, journal = {Geombinatorics Quarterly}, volume = {XXXIV}, url = {https://geombina.uccs.edu/past-issues/volume-xxxiv}, archiveprefix = {arXiv}, eprint = {2404.05509}, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings} }
- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings. Proceedings of Discrete Mathematics Days.
[URL]
[arXiv]
[BibTeX]
@inproceedings{mpsz_hadwigernelsonspectrum_24:1, year = {2024}, booktitle = {Proceedings of Discrete Mathematics Days}, url = {https://dmd2024.web.uah.es/files/abstracts/paper_27.pdf}, archiveprefix = {arXiv}, eprint = {2404.05509}, author = {Mundinger, Konrad and Pokutta, Sebastian and Spiegel, Christoph and Zimmer, Max}, title = {Extending the Continuum of Six-Colorings} }
- 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{ppss_ramsey_22, 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} }
- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2023). Fully Computer-assisted Proofs in Extremal Combinatorics. Proceedings of AAAI Conference on Artificial Intelligence.
DOI: 10.1609/aaai.v37i10.26470
[URL]
[arXiv]
[code]
[BibTeX]
@inproceedings{ppss_ramsey_22:1, year = {2023}, booktitle = {Proceedings of 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} }
- 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} }
- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2022). New Ramsey Multiplicity Bounds and Search Heuristics. Proceedings of Discrete Mathematics Days.
[arXiv]
[code]
[BibTeX]
@inproceedings{ppss_ramsey_22:2, year = {2022}, booktitle = {Proceedings of 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} }
- Böttcher, J., Sgueglia, A., Skokan, J., and Parczyk, O. (2021). The Square of a Hamilton Cycle in Randomly Perturbed Graphs. Proceedings of 11th EuroComb Conference, 14, 644–650.
DOI: 10.1007/978-3-030-83823-2_103
[arXiv]
[BibTeX]
@inproceedings{hamilton_cycle_2021:1, year = {2021}, booktitle = {Proceedings of 11th EuroComb Conference}, volume = {14}, pages = {644-650}, doi = {10.1007/978-3-030-83823-2_103}, archiveprefix = {arXiv}, eprint = {2202.05215}, author = {Böttcher, Julia and Sgueglia, Amedeo and Skokan, Jozef and Parczyk, Olaf}, title = {The Square of a Hamilton Cycle in Randomly Perturbed Graphs} }
- DĂaz, A. E., Gupta, P., Cecchelli, D. M., Parczyk, O., and Sgueglia, A. Dirac’s Theorem for Graphs of Bounded Bandwidth.
[arXiv]
[BibTeX]
@misc{dirac_bandwidth_2024, archiveprefix = {arXiv}, eprint = {2407.05889}, author = {DĂaz, Alberto Espuny and Gupta, Pranshu and Cecchelli, Domenico Mergoni and Parczyk, Olaf and Sgueglia, Amedeo}, title = {Dirac's Theorem for Graphs of Bounded Bandwidth} }
- Böttcher, J., Frankl, N., Cecchelli, D. M., Skokan, J., and Parczyk, O. Graphs with Large Minimum Degree and No Small Odd Cycles Are 3-colourable.
[arXiv]
[BibTeX]
@misc{large_min_degree_2023, archiveprefix = {arXiv}, eprint = {2302.01875}, 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} }
- Mattos, L., Cecchelli, D. M., and Parczyk, O. On Product Schur Triples in the Integers.
[arXiv]
[BibTeX]
@misc{schur_triples_2023, archiveprefix = {arXiv}, eprint = {2311.18796}, author = {Mattos, LetĂcia and Cecchelli, Domenico Mergoni and Parczyk, Olaf}, title = {On Product Schur Triples in the Integers} }
- Illingworth, F., Lang, R., MĂĽyesser, A., Parczyk, O., and Sgueglia, A. Spanning Spheres in Dirac Hypergraphs.
[arXiv]
[BibTeX]
@misc{spheres_dirac_2024, archiveprefix = {arXiv}, eprint = {2407.06275}, author = {Illingworth, Freddie and Lang, Richard and MĂĽyesser, Alp and Parczyk, Olaf and Sgueglia, Amedeo}, title = {Spanning Spheres in Dirac Hypergraphs} }