The signed triangle detection conjecture for LqL_q random geometric graphs

From papers

Let n,dn,d be positive parameters, let q[1,]q\in[1,\infty], and consider testing

H0:G(n,1/2)H_0:\mathsf{G}(n,1/2)

against

H1:RGG(n,Td,Unif,σ1/2q,1/2).H_1:\mathsf{RGG}(n,\mathbb{T}^{d},\mathsf{Unif},\sigma^q_{1/2},1/2).

Assume dq3=ω(n3)dq^3=\omega(n^3). The signed triangle test is the signed subgraph-count test based on the triangle C3C_3. Signed triangle detection conjecture. The signed triangle test has the following behavior:

  1. If q=o(d/logd)q=o(d/\log d), it succeeds with high probability when dq3=o(n3)dq^3=o(n^3) and fails with high probability when dq3=ω(n3)dq^3=\omega(n^3).
  2. If q=Ω(d/logd)q=\Omega(d/\log d), it succeeds with high probability when d=o~(n3/4)d=\tilde{o}(n^{3/4}) and fails with high probability when d3=ω~(n3/4)d^3=\tilde{\omega}(n^{3/4}).

This conjecture extrapolates the signed-triangle behavior known at the endpoint regimes q=2q=2 and q=q=\infty; the supplied source does not resolve the asserted transition behavior.

Progress summary

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

Sources & referencesView supporting material

Primary source

Kiril Bangachev and Guy Bresler, “Detection of L_Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion”, arXiv:2310.14501 (2023).

Solutions 0

No solutions have been posted yet.