umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sharpness in the k-nearest-neighbours random geometric graph model
Queen Mary University of London, School of Mathematical Sciences.
Queen Mary University of London, School of Mathematical Sciences.
2012 (English)In: Advances in Applied Probability, ISSN 0001-8678, E-ISSN 1475-6064, Vol. 44, no 3, 617-634 p.Article in journal (Refereed) Published
Abstract [en]

Let Sn,k denote the random 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ás, Sarkar and Walters (2005) conjectured that, for every 0 < ε < 1 and all sufficiently large n, there exists C = C(ε) such that, whenever the probability that Sn,k is connected is at least ε, then the probability that Sn,k+Cis connected is at least 1 - ε. In this paper we prove this conjecture. As a corollary, we prove that there exists a constant C' such that, whenever k(n) is a sequence of integers such that the probability Sn,k(n) is connected tends to 1 as n → ∞, then, for any integer sequences(n) with s(n) = o(logn), the probability Sn,k(n)+⌊C'slog logn is s-connected (i.e. remains connected after the deletion of any s - 1 vertices) tends to 1 as n → ∞. This proves another conjecture given in Balister, Bollobás, Sarkar and Walters (2009).

Place, publisher, year, edition, pages
Applied Probability Trust , 2012. Vol. 44, no 3, 617-634 p.
Keyword [en]
Random geometric graph, connectivity, sharp transition
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:umu:diva-80522DOI: 10.1239/aap/1346955257OAI: oai:DiVA.org:umu-80522DiVA: diva2:650004
Available from: 2013-09-19 Created: 2013-09-19 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aap/1346955257http://www.jstor.org/stable/41714068

Search in DiVA

By author/editor
Falgas-Ravry, Victor
In the same journal
Advances in Applied Probability
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 53 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf