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

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/logd)q=o(d/\log d) and dq=ω(n2)dq=\omega(n^2);
  2. q=Ω(d/logd)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.

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.