The signed four-cycle 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).

Here the signed four-cycle test is the signed subgraph-count test based on the four-cycle C4C_4. Signed four-cycle detection conjecture. The signed four-cycle test distinguishes the two hypotheses with high probability in either of the following regimes:

  1. q=o(d/log⁡d)q=o(d/\log d) and dq=ω(n2)dq=\omega(n^2);
  2. q=Ω(d/log⁡d)q=\Omega(d/\log d) and d=ω~(n)d=\tilde{\omega}(n).

The conjecture extrapolates the expected orders of the signed four-cycle count from the endpoint cases q=2q=2 and q=∞q=\infty. Its status is not resolved in the supplied source.

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.