{
  "id": "0808.4067",
  "version": "v3",
  "published": "2008-08-29T10:26:48.000Z",
  "updated": "2010-09-06T17:09:22.000Z",
  "title": "The diameter of sparse random graphs",
  "authors": [
    "Oliver Riordan",
    "Nicholas Wormald"
  ],
  "comment": "92 pages; expanded slightly with minor corrections; to appear in Combinatorics, Probability and Computing",
  "journal": "Combinatorics, Probability and Computing 19 (2010), 835--926",
  "doi": "10.1017/S0963548310000325",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In this paper we study the diameter of the random graph $G(n,p)$, i.e., the the largest finite distance between two vertices, for a wide range of functions $p=p(n)$. For $p=\\la/n$ with $\\la>1$ constant, we give a simple proof of an essentially best possible result, with an $O_p(1)$ additive correction term. Using similar techniques, we establish 2-point concentration in the case that $np\\to\\infty$. For $p=(1+\\epsilon)/n$ with $\\epsilon\\to 0$, we obtain a corresponding result that applies all the way down to the scaling window of the phase transition, with an $O_p(1/\\epsilon)$ additive correction term whose (appropriately scaled) limiting distribution we describe. Combined with earlier results, our new results complete the determination of the diameter of the random graph $G(n,p)$ to an accuracy of the order of its standard deviation (or better), for all functions $p=p(n)$. Throughout we use branching process methods, rather than the more common approach of separate analysis of the 2-core and the trees attached to it.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2010-09-06T17:09:22.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60C05"
    ],
    "keywords": [
      "sparse random graphs",
      "additive correction term",
      "largest finite distance",
      "separate analysis",
      "wide range"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 92,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0808.4067R"
    }
  }
}