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

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 whenm is at most n2 +O(n 2/3) and whenm is at least ω ( n1+ 1 j ) for j ∈ N, and so we focus on intermediate cases. In particular, we show that g(n,m) = (1 + o(1))m2 whp (with high probability) when n m = n1+o(1); that g(n,m) = (1 + o(1))μ(λ)m whp for a given function μ(λ) when m ∼ λn for λ > 1 2 ; and that g(n,m) = (1 + o(1)) 8s3 3n2 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 n edges will whp result in a graph with genus Ω(n), even when is an arbitrarily small constant! We thus call this the ‘fragile genus’ property. 2012 ACM Subject Classification Mathematics of computing → Random graphs, Mathematics of computing → Graphs and surfaces