Random Structures & Algorithms

The genus of the Erdős‐Rényi random graph and the fragile genus property

Early View

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 and for , and so we focus on the intermediate cases. We establish that 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 , and that whp when 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.

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.