DROPS

Document

DOI: 10.4230/LIPIcs.AofA.2018.17

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

Authors: Chris Dowden, Mihyun Kang, and Michael Krivelevich

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.

Cite as

Chris Dowden, Mihyun Kang, and Michael Krivelevich. The Genus of the Erdös-Rényi Random Graph and the Fragile Genus Property. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dowden_et_al:LIPIcs.AofA.2018.17,
  author =	{Dowden, Chris and Kang, Mihyun and Krivelevich, Michael},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.17},
  URN =		{urn:nbn:de:0030-drops-89100},
  doi =		{10.4230/LIPIcs.AofA.2018.17},
  annote =	{Keywords: Random graphs, Genus, Fragile genus}
}

Search Results

Documents authored by Dowden, Chris

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

Abstract

Cite as

Thanks for your feedback!

Could not send message