Research Grant ``Sparse random combinatorial structures''

Summary

Probabilistic combinatorics is a mathematical discipline concerned with the study of random combinatorial structures such as random graphs, networks or matrices. Such random structures play a pivotal role in randomised constructions in computer science and other areas of application. Over the past two decades probabilistic combinatorics has received impulses from statistical physics, where a heuristic method called the "Cavity Method" has been developed to put forward intriguing conjectures on numerous long-standing problems. The aim of this project is to provide a rigorous mathematical basis for the techniques upon which the cavity method is based. The focus will be on sparse random combinatorial structures. Specifically, the project concentrates on three prominent, closely related challenges: random combinatorial matrices and random equations over discrete algebraic structures; weighted matchings on sparse random graphs; Hamilton cycles in sparse random graphs.

Grant Info

• Grant DOI: 10.55776/I6502
• International projects supported by Austrian Science Fund (FWF I6502) and German Research Foundation (DFG CO 646/6-1)
• Support period by FWF: 14.10.2023-13.10.2026

Team

• TU Dortmund, Research Group Efficient Algorithms and Complexity Theory
• Amin Coja-Oghlan (PI)
• Pavel Zakharov (PhD student)


• TU Graz, Research Group Combinatorics
• Mihyun Kang (PI)
• Vincent Pfenninger (postdoc)

Collaborators and visitors (selection)

• 5-10 May 2024, Michael Krievelevich, Tel Aviv University
• 5-10 May 2024, Sahar Diskin, Tel Aviv University
• 15-19 January 2024, Michael Anastos, IST Austria
• 18-22 December 2023, Amin Coja-Oghlan, TU Dortmund
• 18-21 December 2023, Lena Krieg, TU Dortmund
• 18-21 December 2023, Maurice Rolvien, TU Dortmund
• 18-21 December 2023, Olga Scheftelowitsch, TU Dortmund
• 18-21 December 2023, Pavel Zakharov, TU Dortmund

Publications (supported by FWF I6502)

Articles in peer-reviewed journals

• Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Percolation on irregular high-dimensional product graphs, Combin. Probab. Comput., 33(3):377-403, 2024. doi:10.1017/S0963548323000469
• Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Isoperimetric inequalities and supercritical percolation on high-dimensional product graphs, Combinatorica (2024), to appear. doi:10.1007/s00493-024-00089-0
• Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, and Dominik Schmid, Catching a robber on a random $k$-uniform hypergraph, Canadian Journal of Mathematics (2024), to appear.
• Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, and Maurice Rolvien, The $k$-XORSAT threshold revisited, Electron. J. Combin. (2024), to appear.

Articles submitted for publication

• Mihyun Kang, Christoph Koch, and Tamas Makai, Bootstrap percolation on the binomial random $k$-uniform hypergraph.
• Michael Anastos, Oliver Cooley, Mihyun Kang, and Matthew Kwan, Partitioning problems via random processes.
• David Gamarnik, Mihyun Kang, and Pawel Pralat, Cliques, chromatic number, and independent sets in the semi-random process.
• Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Percolation on high-dimensional product graphs.

Organisation of workshops

• Strobl Combinatorics Workshop, BIFEB in Strobl, 4-7 September 2024
• Kick-Off Workshop, BIFEB in Strobl, 23-28 October 2023

Strobl, October 2023

last updated in April 2024