Phase transitions in graphs on orientable surfaces

Abstract

Let ${\mathbb{S}}_g$ be the orientable surface of genus $g$. We prove that the component structure of a graph chosen uniformly at random from the class ${\mathcal{S}}_g(n,m)$ of all graphs on vertex set $[n]=\{1,\dots ,n\}$ with $m$ edges embeddable on ${\mathbb{S}}_g$ 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=\frac{n}{2}+O(n^{2/3})$, when a unique largest component, the so-called \emph{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. Moreover, we derive an asymptotic estimation of the number of graphs in ${\mathcal{S}}_g(n,m)$ throughout the regimes of these two phase transitions.

47 pages, 1 figure. An extended abstract of this paper has been published in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb17), Electronic Notes in Discrete Mathematics 61:687--693, 2017

References in corpus (1)

• Asymptotic normality of the $k$-core in random graphs