Exact-recovery phase-transition conjecture for logarithmic-degree Euclidean random graphs

For any λ>0\lambda>0, dNd\in\mathbb{N}, and 0b<a10\leq b<a\leq 1, let νd\nu_d denote the volume of the unit Euclidean ball in dd dimensions, and let GnGn(λn,a,b,d)G_n\sim\mathcal{G}_n(\lambda n,a,b,d) be the graph model whose connection functions are fin(n)(r)=a1rlog(n)1/df_{in}^{(n)}(r)=a\mathbf{1}_{r\leq\log(n)^{1/d}} and fout(n)(r)=b1rlog(n)1/df_{out}^{(n)}(r)=b\mathbf{1}_{r\leq\log(n)^{1/d}}. Exact-recovery phase-transition conjecture. If

λνd(1ab(1a)(1b))>1,\lambda\nu_d\left(1-\sqrt{ab}-\sqrt{(1-a)(1-b)}\right)>1,

then Exact-Recovery of GnG_n is solvable. The preceding theorem establishes impossibility when the same expression is less than 11, so this conjecture identifies the threshold for Exact-Recovery in this simplest logarithmic-degree instance of the model; the authors state that they do not pursue a proof.

Sources & referencesView supporting material

Primary source

Emmanuel Abbe, Francois Baccelli and Abishek Sankararaman, “Community Detection on Euclidean Random Graphs”, arXiv:1706.09942 (2020).

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.