Premium
Phase transitions in graphs on orientable surfaces
Author(s) -
Kang Mihyun,
Moßhammer Michael,
Sprüssel Philipp
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20900
Subject(s) - combinatorics , giant component , mathematics , vertex (graph theory) , random graph , phase transition , discrete mathematics , graph , random regular graph , 1 planar graph , chordal graph , physics , quantum mechanics
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.