The evolution of random graphs on surfaces

Abstract

For integers $g,m\ge 0$ and $n>0$, let $S_g(n,m)$ denote the graph taken uniformly at random from the set of all graphs on $\{1,2,\dots ,n\}$ with exactly $m=m(n)$ edges and with genus at most $g$. We use counting arguments to investigate the components, subgraphs, maximum degree, and largest face size of $S_g(n,m)$, finding that there is often different asymptotic behaviour depending on the ratio $\frac{m}{n}$. In our main results, we show that the probability that $S_g(n,m)$ contains any given non-planar component converges to $0$ as $n\to \infty$ for all $m(n)$; the probability that $S_g(n,m)$ contains a copy of any given planar graph converges to $1$ as $n\to \infty$ if $\mathrm{liminf}\frac{m}{n}>1$; the maximum degree of $S_g(n,m)$ is $\Theta (\ln n)$ with high probability if $\mathrm{liminf}\frac{m}{n}>1$; and the largest face size of $S_g(n,m)$ has a threshold around $\frac{m}{n}=1$ where it changes from $\Theta (n)$ to $\Theta (\ln n)$ with high probability.

35 pages