{
  "id": "1101.3083",
  "version": "v1",
  "published": "2011-01-16T17:55:49.000Z",
  "updated": "2011-01-16T17:55:49.000Z",
  "title": "Sharpness in the k-nearest neighbours random geometric graph model",
  "authors": [
    "Victor Falgas-Ravry",
    "Mark Walters"
  ],
  "comment": "22 pages; 1 figure",
  "journal": "Advances in Applied Probability, 44(3) (2012), 617-634",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Let $S_{n,k}$ denote the random geometric graph obtained by placing points in a square box of area $n$ according to a Poisson process of intensity 1 and joining each point to its $k$ nearest neighbours. Balister, Bollob\\'as, Sarkar and Walters conjectured that for every $0< \\epsilon <1$ and all $n$ sufficiently large there exists $C=C(\\epsilon)$ such that whenever the probability $S_{n,k}$ is connected is at least $\\epsilon $ then the probability $S_{n,k+C}$ is connected is at least $1-\\epsilon $. In this paper we prove this conjecture. As a corollary we prove that there is a constant $C'$ such that whenever $k=k(n)$ is a sequence of integers such that the probability $S_{n,k(n)}$ is connected tends to one as $n$ tends to infinity, then for any $s(n)$ with $s(n)=o(\\log n)$, the probability that $S_{n,k(n)+C's\\log \\log n}$ is $s$-connected tends to one This proves another conjecture of Balister, Bollob\\'as, Sarkar and Walters.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-01-16T17:55:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60K35",
      "82B43"
    ],
    "keywords": [
      "neighbours random geometric graph model",
      "k-nearest neighbours random geometric graph",
      "probability",
      "conjecture",
      "connected tends"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}