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.
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.