Research Grant ``Random Graphs: Cores, Colourings and Contagion''

Summary

The aim of this collaborative project, which is hosted jointly at Goethe University Frankfurt in Germany and at TU Graz in Austria, is to advance the rigorous mathematical understanding of random graphs with the assistance of novel mathematical tools originating, for example, from enumerative combinatorics or the recent theory of graph limits. Specific problems that we intend to study include the graph colouring problem on random graphs, strongly connected sub-structures of random graphs called cores and the contagion of cascading events. For example, graph colouring has been a core topic of mathematics since the famous four colour problem posed by Gutherie in 1852. Cores have applications, for example, in coding theory, and contagion is a key topic in the study of complex social or artificial networks.

Grant Info

• International Cooperation Project (D-A-CH Scheme)
• Supported by Austrian Science Fund (FWF I3747) and German Research Foundation (DFG CO 646/4)
• Support period by FWF: 01.09.2018-30.06.2022

Team

• Goethe University Frankfurt (01.01.2019) and TU Dormund (01.10.2021-31.03.2022)
• Amin Coja-Oghlan (PI)
• Jean Bernoulli Ravelomanana (PhD student)


• TU Graz (01.09.2018-30.06.2022)
• Oliver Cooley (postdoctoral research fellow)
• Mihyun Kang (PI)

Collaborators and visitors (selection)

• Amin Coja-Oghlan, Goethe University Frankfurt
• Nikolaos Fountoulakis, University of Birmingham
• Mikhail Isaev, Monash University
• Tobias Kapetanopoulos, Goethe University Frankfurt
• Michael Krievelevich, Tel Aviv University
• Joon Lee, Goethe University Frankfurt
• Tamas Makai, UNSW Sydney
• Oleg Pikhurko, University of Warwick
• Jean Bernoulli Ravelomanana, Goethe University Frankfurt
• Benny Sudakov, ETH Zürich

Publications (supported by FWF I3747)

Articles in peer-reviewed journals

• Oliver Cooley, Tobias Kapetanopoulos, and Tamas Makai, The sharp threshold for jigsaw percolation in random graphs, Advances in Applied Probability 51 (2019), 378-407. doi:10.1017/apr.2019.24.
• Oliver Cooley and Abraham Gutierrez, Multi-coloured jigsaw percolation on random graphs, Journal of Combinatorics 11 (2020), 603-624. doi:10.4310/JOC.2020.v11.n4.a2.
• Nikolaos Fountoulakis, Mihyun Kang, and Tamas Makai, Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs, Random Structures and Algorithms 57 (2020), 1134-1156. doi:10.1002/rsa.20970.
• Joshua Erde, Mihyun Kang, and Michael Krivelevich, Large complete minors in random subgraphs, Combinatorics, Probability and Computing 30 (2021), 619-630. doi:10.1017/S0963548320000607.
• Oliver Cooley, Nemanja Draganic, Mihyun Kang, and Benny Sudakov, Large induced matchings in random graphs, SIAM J. Discrete Math. 35-1 (2021), 267-280. doi:10.1137/20M1330609.
• Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolas Sanhueza-Matamala, and Julian Zalla, Longest paths in random hypergraphs, SIAM J. Discrete Math. 35-4 (2021), pp. 2430-2458. doi:10.1137/20M1345712
• Mihyun Kang and Michael Missethan, Longest and shortest cycles in random planar graphs, Random Structures and Algorithms 60 (2022), 462-505. doi:10.1002/rsa.21040.
• Tuan Anh Do, Joshua Erde, and Mihyun Kang, Planarity and genus of sparse random bipartite graphs, SIAM J. Discrete Math. 36-2 (2022), 1394-1415. doi:10.1137/20M1341817.
• Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel, Phase transition in cohomology groups of non-uniform random simplicial complexes, Electron. J. Combin. 29 (2022), #P3.27. doi:10.37236/10607.
• Oliver Cooley, Mihyun Kang, and Julian Zalla, Loose cores and cycles in random hypergraphs, Electron. J. Combin. 29 (2022), #P4.13. doi:10.37236/10794.
• Oliver Cooley, Mihyun Kang, and Oleg Pikhurko, On a question of Vera T. Sós about size forcing of graphons, Acta Math. Hungar. 168 (2022), 1-26.
• Mikhail Isaev and Mihyun Kang, On the chromatic number in the stochastic block model, Electron. J. Combin. 30 (2023), #P2.56.
• Joshua Erde, Mihyun Kang, and Michael Krivelevich, Expansion in supercritical random subgraphs of the hypercube and its consequences, Annals of Probability 51 (1) (2023), 127-156.
• Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, Jean Bernoulli Ravelomanana, The sparse parity matrix, Advances in Combinatorics 2023:5, 68pp.
• Tuan Anh Do, Joshua Erde, and Mihyun Kang, A note on the width of sparse random graphs, Journal of Graph Theory (2024), to appear.

Articles in peer-reviewed conference proceedings

• Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel, Cohomology groups of non-uniform random simplicial complexes, In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Acta Math. Univ. Comenianae Vol. LXXXVIII, 3 (2019), pp. 553-560.
• Oliver Cooley, Mihyun Kang, and Oleg Pikhurko, On a question of Vera T. Sos about size forcing of graphons (extended abstract), Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.
• Oliver Cooley, Mihyun Kang, and Julian Zalla, Loose cores and cycles in random hypergraphs (extended abstract), Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.
• Tuan Anh Do, Joshua Erde, and Mihyun Kang, Component behaviour of random bipartite graphs, In Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives, Springer.
• Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, Jean Bernoulli Ravelomanana, The sparse parity matrix, In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 822-833. doi:10.1137/1.9781611977073.35.

Articles submitted for publication

• Oliver Cooley, Paths, cycles and sprinkling in random hypergraphs.
• Mikhail Isaev and Mihyun Kang, On the chromatic number of graphons.
• Oliver Cooley, Joon Lee, Jean Bernoulli Ravelomanana, Warning Propagation: stability and subcriticality.
• Oliver Cooley and Julian Zalla, High-order bootstrap percolation in hypergraphs.

Thesis

• Oliver Cooley, High-dimensional connectedness: cores and components, Habilitation Thesis, 2020.

Organisation of workshops

• Oberwolfach Workshop on Random Graphs: Combinatorics, Complex Networks and Disordered Systems, 3-9 May 2020 (not realised due to the Covid-19 pandemic).
• IBS Workshop on Extremal and Probabilistic Combinatorics, Institute of Basic Scienes, Korea, 24-28 August 2020 (not realised due to the Covid-19 pandemic).
• Banff Workshop on Random Graphs and Statistical Inference, online, 8-13 August 2021 (postponed to March 2023).

Graz, December 2019

last updated in January 2024