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 behavior depending on which “region” m falls into.
Results already exist for urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0001 and urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0002 for urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0003, and so we focus on the intermediate cases. We establish that urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0004 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 urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0005, and that urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0006 whp when urn:x-wiley:rsa:media:rsa20871:rsa20871-math-0007 for n2/3 ≪ s ≪ n.
We then also show that the genus of a fixed graph 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.