2026-07-23T13:07:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8910 2024-03-06T10:43:43Z ddc:004 open_access

The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property Dowden, Chris Kang, Mihyun Krivelevich, Michael Random graphs Genus Fragile genus 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chris Dowden and Mihyun Kang and Michael Krivelevich 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.17 urn:nbn:de:0030-drops-89100 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17 eng https://creativecommons.org/licenses/by/3.0/legalcode