The signed triangle detection conjecture for random geometric graphs
The signed triangle detection conjecture for random geometric graphs
Let be positive parameters, let , and consider testing
against
Assume . The signed triangle test is the signed subgraph-count test based on the triangle . Signed triangle detection conjecture. The signed triangle test has the following behavior:
- If , it succeeds with high probability when and fails with high probability when .
- If , it succeeds with high probability when and fails with high probability when .
This conjecture extrapolates the signed-triangle behavior known at the endpoint regimes and ; the supplied source does not resolve the asserted transition behavior.
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.