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

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

  1. 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}
}
  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. 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}
}
  4. 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}
}
  5. 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}
}
  6. 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}
}
  7. 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}
}
  8. 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}
}
  9. 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}
}
  10. 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}
}
  11. 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}
}
  12. 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}
}
  13. 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}
}