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. The focus will be on sparse random combinatorial structures.

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 Austrian Science Fund (FWF): 15.10.2023-14.10.2026

Team

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


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

Collaborators and visitors (selection)

• 2-6 June 2025, Michael Anastos, IST Austria
• 2-6 June 2025, Sahar Diskin, Tel Aviv University
• 2-6 June 2025, Michael Krievelevich, Tel Aviv University
• 4-9 April 2025, Sang-il Oum, IBS
• 13-17 January 2025, Michael Anastos, IST Austria
• 21-24 October 2024, Sahar Diskin, Tel Aviv University
• 14-18 October 2024, Jinyoung Park, New York University
• 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

• Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, and Maurice Rolvien, The $k$-XORSAT threshold revisited, Electron. J. Combin. 31-2 (2024), #P2.16. doi:10.37236/11815


• 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 44, 741-784 (2024). 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. Published online 2024:1-28. doi:10.4153/S0008414X24000270


• David Gamarnik, Mihyun Kang, and Pawel Pralat, Cliques, chromatic number, and independent sets in the semi-random process, SIAM J. Discrete Math. 38(3) (2024), 2312-2334. doi:10.1137/23M1561105


• Michael Anastos, Oliver Cooley, Mihyun Kang, and Matthew Kwan, Partitioning problems via random processes, Journal of the London Mathematical Society (2024), 110: e70010. doi:10.1112/jlms.70010


• Sahar Diskin, Joshua Erde, Mihyun Kang, and Michael Krivelevich, Percolation on high-dimensional product graphs, Random Structures & Algorithms (2025), 66: e21268. doi:10.1002/rsa.21268

Articles submitted for publication

• Mikhail Isaev and Mihyun Kang, On the chromatic number of graphons.


• Mihyun Kang, Christoph Koch, and Tamas Makai, Bootstrap percolation on the binomial random $k$-uniform hypergraph.


• Vincent Pfenninger, On $k$-uniform tight cycles: the Ramsey number for $C$_kn^(k) and an approximate Lehel's conjecture.


• Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, and Gregory Sorkin, Belief Propagation Guided Decimation on Random k-XORSAT


• Michael Anastos, Joshua Erde, Mihyun Kang, and Vincent Pfenninger, The law of the circumference of sparse binomial random graphs.

Organisation of workshops

• 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 March 2025