Phase transitions for detecting latent geometry in random graphs (Q2210754)

This paper considers the problem of distinguishing a random graph with an underlying geometry, from which its vertices are sampled, from a binomial random graph \(G(n,p)\). The analysis focuses on two models: the random intersection graph and the random geometric graph. The former is formed out of a set of size \(d\) where \(n\) subsets are sampled \(S_1,\ldots, S_n\), and \(S_i\) is formed after sampling each element independently with probability \(\delta\). These sets form the vertex set of the random graph and \(S_i\) is adjacent to \(S_j\), if \(|S_i \cap S_j| \geq \tau\), for some \(\tau\geq 1\). (The latter is a parameter of the model.) Firstly, for \(\tau=1\), the authors show that if \(d \gg n^3\) (with a certain multiplicative function depending on \(p\)) the total variation distance between this random intersection graph and \(G(n,p)\) tends to 0 as \(n\to \infty\). However, if \(d=o(n^3)\) but also \(d\gg n^2\) and either \(p= \Theta(1)\), but \(1-p = \Omega (1)\), or \(p=\Theta (1/n)\), then the total variation distance tends to 1 as \(n\to \infty\). For the supercritical regime, they obtain a strong result about the \(n \times n\) matrix that contains the intersections of the sets \(S_i\), showing that these are essentially independent Poisson-distributed. More general results are also obtained for \(\tau >1\). Similar results are obtained for the random geometric graph formed by \(n\) points that are sampled uniformly on the \(d-1\)-dimensional unit sphere, where any two of them are joined by an edge if their inner product exceeds some parameter \(t_{p,d}\). (This is such that \(\mathbb{P} (\langle X_1, X_2 \rangle > t_{p,d}) = p\).) If \(d\) asymptotically exceeds a certain function of \(n,p\), then the random geometric graph is close in total variation distance from \(G(n,p)\).