Phase transitions in graphs on orientable surfaces. Issue 4 (13th January 2020)

• Record Type: Journal Article
• Authors: Kang, Mihyun; Moßhammer, Michael; Sprüssel, Philipp
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 1117
• Page End: 1170
• Publication Date: 2020-01-13
• Subjects: giant component -- graphs on surfaces -- phase transition -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20900
• Languages: English
• ISSNs: 1042-9832

Abstract

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.