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

Abstract

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