We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The genus of the Erdős‐Rényi random graph and the fragile genus property.
- Authors
Dowden, Chris; Kang, Mihyun; Krivelevich, Michael
- 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 behavior depending on which "region" m falls into. Results already exist for m≤n2+O(n2/3) and m=ωn1+1j for j∈N, and so we focus on the intermediate cases. We establish that g(n,m)=(1+o(1))m2 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 λ>12, and that g(n,m)=(1+o(1))8s33n2 whp when m=n2+s 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.
- Subjects
RANDOM graphs; RANDOM numbers; GRAPH connectivity; EMBEDDINGS (Mathematics)
- Publication
Random Structures & Algorithms, 2020, Vol 56, Issue 1, p97
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20871