The signed-triangle threshold conjecture for spherical random geometric graphs

Let τp,d\tau_{p,d} be chosen so that the spherical threshold connection Tp(x,y)=1[cobreakx,yτp,d]{\boldsymbol T}_p(\boldsymbol{x},\boldsymbol{y})=\boldsymbol{1}[cobreak\langle\boldsymbol{x},\boldsymbol{y}\rangle\geq\tau_{p,d}] has edge probability pp, and let cobreakRGG(n,Sd1,Unif,p,Tp)cobreak\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,\boldsymbol{T}_p) denote the corresponding random geometric graph. The signed-triangle threshold conjecture. The total variation distance satisfies

TV(G(n,p),RGG(n,Sd1,Unif,p,Tp))=on(1)\mathsf{TV}\Big(\mathsf{G}(n,p),\mathsf{RGG}(n,\mathbb{S}^{d-1},\mathsf{Unif},p,\boldsymbol{T}_p)\Big)=o_n(1)

when d=Ω~(n3p3)d=\widetilde{\Omega}(n^3p^3) for p=Ω(1/n)p=\Omega(1/n). The signed-triangle statistic is believed to give the tight indistinguishability threshold, but the source does not provide a resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Kiril Bangachev and Guy Bresler, “Random Algebraic Graphs and Their Convergence to Erdos-Renyi”, arXiv:2305.04802 (2023).

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.