The signed four-cycle detection conjecture for random geometric graphs
Let be positive parameters, let , and consider testing
against
Here the signed four-cycle test is the signed subgraph-count test based on the four-cycle . Signed four-cycle detection conjecture. The signed four-cycle test distinguishes the two hypotheses with high probability in either of the following regimes:
- and ;
- and .
The conjecture extrapolates the expected orders of the signed four-cycle count from the endpoint cases and . 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
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.