The signed triangle detection conjecture for LqL_q random geometric graphs

About 3 years old · traced to

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/log⁡d)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/log⁡d)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.

References

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).

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.