The evolution of random graphs on surfaces of non-constant genus

C. Dowden, M. Kang, M. Mosshammer, P. Sprüssel

Research output: Contribution to journalConference articlepeer-review


Given a graph G, the genus of G denotes the smallest integer g for which G can be drawn on the orientable surface of genus g without crossing edges. For integers g,m≥0 and n>0, we let Sg(n,m) denote the graph taken uniformly at random from the set of all graphs on {1,2,...,n} with exactly m=m(n) edges and with genus at most g=g(n). We investigate the evolution of Sg(n,m) as m increases, focussing on the number |H1| of vertices in the largest component. For g=o(n), we show that |H1| exhibits two phase transitions, one at around m=n/2 and a second one at around m=n. The exact behaviour of |H1| in the critical windows of these phase transitions depends on the order of g=g(n).
Original languageEnglish
Pages (from-to)631-636
JournalActa Mathematica Universitatis Comenianae
Issue number3
Publication statusPublished - 2019
EventEuropean Conference on Combinatorics, Graph Theory and Applications: Eurocomb 2019 - Bratislava, Slovakia
Duration: 26 Aug 201930 Aug 2019


Dive into the research topics of 'The evolution of random graphs on surfaces of non-constant genus'. Together they form a unique fingerprint.

Cite this