{
  "id": "math/0112029",
  "version": "v1",
  "published": "2001-12-04T01:49:44.000Z",
  "updated": "2001-12-04T01:49:44.000Z",
  "title": "The diameter of a long range percolation graph",
  "authors": [
    "Don Coppersmith",
    "David Gamarnik",
    "Maxim Sviridenko"
  ],
  "comment": "To appear in Symposium on Discrete Algorithms, 2002",
  "categories": [
    "math.PR",
    "math-ph",
    "math.CO",
    "math.MP"
  ],
  "abstract": "We consider the following long range percolation model: an undirected graph with the node set $\\{0,1,...,N\\}^d$, has edges $(\\x,\\y)$ selected with probability $\\approx \\beta/||\\x-\\y||^s$ if $||\\x-\\y||>1$, and with probability 1 if $||\\x-\\y||=1$, for some parameters $\\beta,s>0$. This model was introduced by Benjamini and Berger, who obtained bounds on the diameter of this graph for the one-dimensional case $d=1$ and for various values of $s$, but left cases $s=1,2$ open. We show that, with high probability, the diameter of this graph is $\\Theta(\\log N/\\log\\log N)$ when $s=d$, and, for some constants $0<\\eta_1<\\eta_2<1$, it is at most $N^{\\eta_2}$, when $s=2d$ and is at least $N^{\\eta_1}$ when $d=1,s=2,\\beta<1$ or $s>2d$. We also provide a simple proof that the diameter is at most $\\log^{O(1)}N$ with high probability, when $d<s<2d$, established previously by Berger and Benjamini.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2001-12-04T01:49:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60K35",
      "82B43",
      "82B26"
    ],
    "keywords": [
      "long range percolation graph",
      "long range percolation model",
      "high probability",
      "simple proof",
      "one-dimensional case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2001math.....12029C"
    }
  }
}