Phase transitions in graphs on orientable surfaces

LetS gbe the orientable surface of genus g and denote by g ( n , m ) the class of all graphs on vertex set [ n ] = { 1 , … , n } with m edges embeddable onS g . We prove that the component structure of a graph chosen uniformly at random from g ( n , m ) features two phase transitions. The first phase transition mirrors the classical phase transition in the Erdős‐Rényi random graph G ( n , m ) chosen uniformly at random from all graphs with vertex set [ n ] and m edges. It takes place at m = n 2 + O ( n 2 / 3 ) , when the giant component emerges. The second phase transition occurs at m = n + O ( n 3 / 5 ) , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from G ( n , m ) and has only been observed for graphs on surfaces.