Phase transitions in graphs on orientable surfaces

Abstract: Let

m a t h b b 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

m a t h c a l S_{g} (n, m)

of all graphs on vertex set

[n] = 1, d o t s c, n

with

m

edges embeddable on

m a t h b b S_{g}

features two phase transitions. The first phase transition mirrors the classical phase transition in the ErdH{o}s--R'enyi random graph

G (n, m)

chosen uniformly at random from all graphs with vertex set

[n]

and

m

edges. It takes place at

m = f r a c 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

m a t h c a l S_{g} (n, m)

throughout the regimes of these two phase transitions.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Phase transitions in graphs on orientable surfaces