Research Grant ``Asymptotic properties of graphs on a surface''

Summary

Since the foundation of the theory of random graphs by Erdos and Renyi five decades ago, various random graphs have been introduced and studied. One example is random graphs on a surface, in particular random planar graphs. Graphs on a 2-dimensional surface and related objects (e.g. planar graphs, triangulations) have been among the most studied objects in graph theory, enumerative combinatorics, discrete probability theory, and statistical physics. The main objectives of this project are to study the asymptotic properties and limit behaviour of random graphs on a surface (e.g. evolution, phase transition, critical behaviour, component size distribution) and to investigate enumerative and algorithmic aspects of unlabelled graphs on a surface (e.g. connectivity, symmetry, decomposition, random generation).

Grant Info

Supported by Austrian Science Fund (FWF), Grant no. P27290, 01.06.2015-30.06.2019

Team

  • Oliver Cooley
  • Chris Dowden
  • Wenjie Fang
  • Mihyun Kang (PI)
  • Michael Moßhammer (PhD defence on May 4, 2018)
  • Philipp Sprüssel (Co-PI)

Collaborators and visitors

  • Ron Aharoni, Technion
  • Michael Drmota, TU Wien
  • Eric Fusy, Ecole Polytechnique
  • Daniele Gardy, Universite de Versailles Saint-Quentin
  • Jason Zhicheng Gao, Carleton University
  • Mikhail Isaev, Monash University
  • Michael Krievelevich, Tel Aviv University
  • Colin McDiarmid, University of Oxford
  • Konstantinos Panagiotou, University of Munich
  • Milos Stojakovic, University of Novi Sad

Publications

Articles in Journals
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.
  • Chris Dowden, Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel, The evolution of random graphs on surfaces of non-constant genus, In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2019), Acta Math. Univ. Comenianae Vol. LXXXVIII, 3 (2019), pp. 631-636.
  • Oliver Cooley, Wenjie Fang, Nicola Del Giudice, and Mihyun Kang, Subcritical random hypergraphs, high-order components, and hypertrees, In Proceedings of Analytic Algorithmics and Combinatorics (ANALCO19), pp. 111-118, https://doi.org/10.1137/1.9781611975505.12.
  • Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprü:ssel, Vanishing of cohomology groups of random simplicial complexes, In the Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), pp. 7:1-7:14, doi:10.4230/LIPIcs.AofA.2018.7.
  • Chris Dowden, Mihyun Kang, and Michael Krivelevich, The genus of the Erdos-Renyi random graph and the fragile genus property, In the Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), pp. 17:1-17:13, doi:10.4230/LIPIcs.AofA.2018.17.
    • In the Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018).
  • Chris Dowden, Mihyun Kang, and Philipp Sprussel, The evolution of random graphs on surfaces. In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), pp. 367-373.
  • Oliver Cooley, Penny Haxell, Mihyun Kang, and Philipp Sprüssel, Homological connectedness of random hypergraphs. In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), pp. 279-285.
  • Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel, Evolution of the giant component in graphs on orientable surfaces, In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2017), Electronic Notes in Discrete Mathematics 61 (2017), pp. 687-693.
  • Mihyun Kang and Philipp Sprüssel, Charaterisation of symmetries of unlabelled triangulations, In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), Electronic Notes in Discrete Mathematics (2015), pp.587-594.
  • Wenjie Fang, Mihyun Kang, Michael Moßhammer, and Philipp Sprüssel, Enumeration of cubic multigraphs on orientable surfaces, In the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015), Electronic Notes in Discrete Mathematics (2015), pp. 603-610.

Thesis
  • Michael Moßhammer, Phase transitions and structural properties of random graphs on surfaces, PhD Thesis, May 2018.

last updated in January 2020