Name
Abstract | ||
|---|---|---|
We investigate the genus g(n, m) of the Erdos-Renyi 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 <= n/2+O(n(2/3)) and m = omega(n(1+1/j)) for j is an element of N, and so we focus on the intermediate cases. We establish 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 similar to 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 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 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/rsa.20871 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | Field | DocType |
fragile genus,genus,random graphs | Discrete mathematics,Combinatorics,Random graph,Mathematics | Journal |
Volume | Issue | ISSN |
56.0 | 1.0 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Dowden | 1 | 5 | 4.26 |
| Mihyun Kang | 2 | 163 | 29.18 |
| michael krivelevich | 3 | 1688 | 179.90 |