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.


• 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


• 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, 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.


• 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.


• Mihyun Kang and Michael Missethan, Concentration of maximum degree in random planar graphs, Journal of Combinatorial Theory, Series B (2022), 1394-1415.


• 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.


• 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, Mihyun Kang, and Michael Missethan, Component behaviour and excess of random bipartite graphs near the critical point, Electron. J. Combin. 30 (2023), #P3.7.


• 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.


• Mikhail Isaev and Mihyun Kang, On the chromatic number in the stochastic block model, Electron. J. Combin. 30 (2023), #P2.56.


• Mihyun Kang and Michael Missethan, The early evolution of the random graph process in planar graphs and related classes, SIAM J. Discrete Math. 37-1 (2023), 146-162.


• Tuan Anh Do, Joshua Erde, and Mihyun Kang, A note on the width of sparse random graphs, Journal of Graph Theory, 106(2) (2024), 273-295.

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 (SODA2022), pp. 822-833. doi:10.1137/1.9781611977073.35.

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 October 2024