2017/08/25 by Mihyun Kang, Kang, Mihyun, Michael Moßhammer +3
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1708.07671
openalex publication_date 2017/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let \mathbbSg be the orientable surface of genus g. We prove that the component structure of a graph chosen uniformly at random from the class Sg(n,m) of all graphs on vertex set [n]=\1,\dotsc,n\ with m edges embeddable on \mathbbSg 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(n2/3), when a unique largest component, the so-called giant component, emerges. The second phase transition occurs at m = n+O(n3/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. Moreover, we derive an asymptotic estimation of the number of graphs in Sg(n,m) throughout the regimes of these two phase transitions.