 License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-89100
URL:

; ;

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

 pdf-format:

### Abstract

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.

### 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}s-R{\'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:1--17:13},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-078-1},
ISSN =	{1868-8969},
year =	{2018},
volume =	{110},
editor =	{James Allen Fill and Mark Daniel Ward},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8910},
URN =		{urn:nbn:de:0030-drops-89100},
doi =		{10.4230/LIPIcs.AofA.2018.17},
annote =	{Keywords: Random graphs, Genus, Fragile genus}
}
```

 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

DROPS-Home | Fulltext Search | Imprint | Privacy 