{
  "id": "1708.07671",
  "version": "v1",
  "published": "2017-08-25T09:54:00.000Z",
  "updated": "2017-08-25T09:54:00.000Z",
  "title": "Phase transitions in graphs on orientable surfaces",
  "authors": [
    "Mihyun Kang",
    "Michael Moßhammer",
    "Philipp Sprüssel"
  ],
  "comment": "47 pages, 1 figure. An extended abstract of this paper has been published in the Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb17), Electronic Notes in Discrete Mathematics 61:687--693, 2017",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\mathbb{S}_g$ be the orientable surface of genus $g$. We prove that the component structure of a graph chosen uniformly at random from the class $\\mathcal{S}_g(n,m)$ of all graphs on vertex set $[n]=\\{1,\\dotsc,n\\}$ with $m$ edges embeddable on $\\mathbb{S}_g$ features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd\\H{o}s--R\\'enyi random graph $G(n,m)$ chosen uniformly at random from all graphs with vertex set $[n]$ and $m$ edges. It takes place at $m=\\frac{n}{2}+O(n^{2/3})$, when a unique largest component, the so-called \\emph{giant component}, emerges. The second phase transition occurs at $m = n+O(n^{3/5})$, when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from $G(n,m)$ and has only been observed for graphs on surfaces. Moreover, we derive an asymptotic estimation of the number of graphs in $\\mathcal{S}_g(n,m)$ throughout the regimes of these two phase transitions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-25T09:54:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "orientable surface",
      "vertex set",
      "first phase transition mirrors",
      "second phase transition occurs",
      "giant component covers"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 47,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}