Phase transitions in graphs on orientable surfaces. Issue 4 (13th January 2020) - Kang, Mihyun; Moßhammer, Michael; Sprüssel, Philipp
Abstract : Let S g be 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 on S 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.