Balister–Bollobás–Sarkar–Walters sharpness conjecture for k-nearest-neighbour graphs

Let Sn=[0,n]×[0,n]R2S_n=[0,\sqrt{n}]\times[0,\sqrt{n}]\subset\mathbb{R}^2, place points in SnS_n according to a Poisson process of intensity 11, and join each point to its kk nearest neighbours to obtain the random geometric graph Sn,kS_{n,k}. Balister–Bollobás–Sarkar–Walters' sharpness conjecture. For any 0<ε<10<\varepsilon<1, there exists an integer constant C(ε)C(\varepsilon) such that for all nn sufficiently large, if

P(Sn,k is connected)ε,\mathbb{P}(S_{n,k}\text{ is connected})\geq\varepsilon,

then

P(Sn,k+C(ε) is connected)>1ε.\mathbb{P}(S_{n,k+C(\varepsilon)}\text{ is connected})>1-\varepsilon.

The conjecture asserts that the connectivity transition has a uniformly bounded-width sharp threshold in kk. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.