Dowden, Chris ;
Kang, Mihyun ;
Krivelevich, Michael
The Genus of the ErdösRényi Random Graph and the Fragile Genus Property
Abstract
We investigate the genus g(n,m) of the ErdösRé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.
BibTeX  Entry
@InProceedings{dowden_et_al:LIPIcs:2018:8910,
author = {Chris Dowden and Mihyun Kang and Michael Krivelevich},
title = {{The Genus of the Erd{\"o}sR{\'e}nyi Random Graph and the Fragile Genus Property}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {17:117:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770781},
ISSN = {18688969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8910},
URN = {urn:nbn:de:0030drops89100},
doi = {10.4230/LIPIcs.AofA.2018.17},
annote = {Keywords: Random graphs, Genus, Fragile genus}
}
18.06.2018
Keywords: 

Random graphs, Genus, Fragile genus 
Seminar: 

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Issue date: 

2018 
Date of publication: 

18.06.2018 