# 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]

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

- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings.
*Geombinatorics Quarterly*,*XXXIV*. [URL] [arXiv]## [BibTeX]

- Mundinger, K., Pokutta, S., Spiegel, C., and Zimmer, M. (2024). Extending the Continuum of Six-Colorings.
*Proceedings of Discrete Mathematics Days*. [URL] [arXiv]## [BibTeX]

- Parczyk, O., Pokutta, S., Spiegel, C., and SzabĂł, T. (2024). New Ramsey Multiplicity Bounds and Search Heuristics.
*Foundations of Computational Mathematics*. [arXiv] [code]## [BibTeX]

- 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]

- 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]

- 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]

- 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]

- DĂaz, A. E., Gupta, P., Cecchelli, D. M., Parczyk, O., and Sgueglia, A.
*Diracâ€™s Theorem for Graphs of Bounded Bandwidth*. [arXiv]## [BibTeX]

- 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]

- Mattos, L., Cecchelli, D. M., and Parczyk, O.
*On Product Schur Triples in the Integers*. [arXiv]## [BibTeX]

- Illingworth, F., Lang, R., MĂĽyesser, A., Parczyk, O., and Sgueglia, A.
*Spanning Spheres in Dirac Hypergraphs*. [arXiv]## [BibTeX]