The signed four-cycle detection conjecture for random geometric graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.