Name
Abstract | ||
|---|---|---|
investigate the genus $g(n,m)$ of the ErdH{o}s-Ru0027enyi 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 `regionu0027 $m$ falls into. Results already exist for $m$ at most $frac{n}{2} + O(n^{2/3})$ and $m$ at least $omega left( n^{1+frac{1}{j}} right)$ for $j mathbb{N}$, and so we focus on the intermediate cases. establish that $g(n,m) = (1+o(1)) frac{m}{2}$ whp (with high probability) when $n ll m = n^{1+o(1)}$, that $g(n,m) = (1+o(1)) mu (lambda) m$ whp for a given function $mu (lambda)$ when $m sim lambda n$ for $lambda u003e frac{1}{2}$, and that $g(n,m) = (1+o(1)) frac{8s^{3}}{3n^{2}}$ whp when $m = frac{n}{2} + s$ for $n^{2/3} ll s ll 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! thus call this the `fragile genusu0027 property. |
Year | Venue | Field |
|---|---|---|
2018 | AofA | Graph,Discrete mathematics,Combinatorics,Random graph,Omega,Degree (graph theory),Connectivity,Mathematics,Lambda,Bounded function |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chris Dowden | 1 | 5 | 4.26 |
| Mihyun Kang | 2 | 163 | 29.18 |
| michael krivelevich | 3 | 1688 | 179.90 |