{
  "id": "1709.00864",
  "version": "v1",
  "published": "2017-09-04T08:52:07.000Z",
  "updated": "2017-09-04T08:52:07.000Z",
  "title": "The evolution of random graphs on surfaces",
  "authors": [
    "Chris Dowden",
    "Mihyun Kang",
    "Philipp Sprüssel"
  ],
  "comment": "33 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For integers $g,m \\geq 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, \\ldots, 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 $\\liminf \\frac{m}{n} > 1$; the maximum degree of $S_{g}(n,m)$ is $\\Theta (\\ln n)$ with high probability if $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-04T08:52:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07",
      "05C10",
      "05C80"
    ],
    "keywords": [
      "random graphs",
      "maximum degree",
      "high probability",
      "largest face size",
      "non-planar component converges"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 33,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}