The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property

Abstract

We investigate the genus g(n,m) of the Erdös-Rényi random graph G(n,m), providing a thorough description of how this relates to the function m=m(n), and finding that there is different behaviour depending on which `region' m falls into.
Existing results are known for when m is at most n/(2) + O(n^{2/3}) and when m is at least omega (n^{1+1/(j)}) for j in N, and so we focus on intermediate cases.
In particular, we show that g(n,m) = (1+o(1)) m/(2) whp (with high probability) when n << m = n^{1+o(1)}; that g(n,m) = (1+o(1)) mu (lambda) m whp for a given function mu (lambda) when m ~ lambda n for lambda > 1/2; and that g(n,m) = (1+o(1)) (8s^3)/(3n^2) whp when m = n/(2) + s for n^(2/3) << s << n.
We then also show that the genus of fixed graphs can increase dramatically if a small number of random edges are added. Given any connected graph with bounded maximum degree, we find that the addition of epsilon n edges will whp result in a graph with genus Omega (n), even when epsilon is an arbitrarily small constant! We thus call this the `fragile genus' property.