Balister–Bollobás–Sarkar–Walters sharpness conjecture for k-nearest-neighbour graphs
Balister–Bollobás–Sarkar–Walters sharpness conjecture for k-nearest-neighbour graphs
Let , place points in according to a Poisson process of intensity , and join each point to its nearest neighbours to obtain the random geometric graph . Balister–Bollobás–Sarkar–Walters' sharpness conjecture. For any , there exists an integer constant such that for all sufficiently large, if
then
The conjecture asserts that the connectivity transition has a uniformly bounded-width sharp threshold in . The paper states that it proves this conjecture.
Sources & referencesView supporting material
Primary source
Victor Falgas-Ravry and Mark Walters, “Sharpness in the k-nearest neighbours random geometric graph model”, arXiv:1101.3083 (2011).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.