{
  "id": "1006.0444",
  "version": "v2",
  "published": "2010-06-02T16:57:26.000Z",
  "updated": "2010-11-08T20:57:56.000Z",
  "title": "Two critical periods in the evolution of random planar graphs",
  "authors": [
    "Mihyun Kang",
    "Tomasz Łuczak"
  ],
  "comment": "30 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $P(n,M)$ be a graph chosen uniformly at random from the family of all labeled planar graphs with $n$ vertices and $M$ edges. In the paper we study the component structure of $P(n,M)$. Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of $P(n,M)$. The first one, of width $\\Theta(n^{2/3})$, is analogous to the phase transition observed in the standard random graph models and takes place for $M=n/2+O(n^{2/3})$, when the largest complex component is formed. Then, for $M=n+O(n^{3/5})$, when the complex components cover nearly all vertices, the second critical period of width $n^{3/5}$ occurs. Starting from that moment increasing of $M$ mostly affects the density of the complex components, not its size.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-11-08T20:57:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C10",
      "05C80",
      "05C30",
      "05A16"
    ],
    "keywords": [
      "random planar graphs",
      "critical period",
      "standard random graph models",
      "largest complex component",
      "complex components cover"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1006.0444K"
    }
  }
}