Detection of $L_{\infty }$ Geometry in Random Geometric Graphs: Suboptimality of Triangles and Cluster Expansion

Kiril Bangachev, Guy Bresler

In this paper we study the random geometric graph $\mathsf{RGG}(n,{\mathbb{T}}^d,\mathsf{Unif},{\sigma }_p^q,p)$ with $L_q$ distance where each vertex is sampled uniformly from the $d$-dimen…