The authors investigate the problem of detecting geometric structures in large random graphs. In the present article, they continue a line of investigation started in [S. Bubeck et al., Random Struct. Algorithms 49, No. 3, 503–532 (2016; Zbl 1349.05315)], where it was shown that \[ d_{TV}\left(G(n,p),G(n,p,d)\right)\to\begin{cases}1, &\text{ if }d/n^3\to 0,\\ 0, &\text{ if }d/n^3\to\infty.\end{cases}\tag{1} \] Here, \(d_{TV}\) denotes total variation distance, \(G(n,p)\) is the law of a dense Erdős-Rényi random graph on \(n\) vertices with \(p\in(0,1)\) and \(G(n,p,d)\) is the law of the isotropic random geometric graph obtained by generating a sample \(X_1,\dots,X_n\) of \(n\) i.i.d.vertices drawn from the standard normal distribution in \(\mathbb{R}^d\) and connecting \(X_i\), \(X_j\) by an edge if their scalar product exceeds the threshold value \(t_p\) determined by the edge density condition \(\mathbb{P}(\langle X_i, X_j\rangle\geq t_p)=p.\) Since the coordinates of a data point tend to represent different features which may influence the network formation in different ways, it is natural to replace the model \(G(n,p,d)\) by the anisotropic model \(G(n,p,\alpha)\) in which the vertex positions follow a normal law determined by a more general covariance matrix \(D_\alpha\). In particular, the authors investigate the case in which \(D_\alpha\) is a diagonal matrix with non-negative diagonal entries given by \(\alpha=(\alpha_1,\dots,\alpha_d)\in \mathbb{R}_{\geq 0}^d.\) The main result of the paper is that \[ d_{TV}\left(G(n,p),G(n,p,\alpha)\right)\to\begin{cases}1, &\text{ if }\left(\frac{||\alpha||_2}{||\alpha||_3}\right)^6/n^3\to 0,\\ 0, &\text{ if }\left(\frac{||\alpha||_2}{||\alpha||_4}\right)^4/n^3\to\infty,\end{cases}\tag{2} \] which generalises (1). However, unlike in the isotropic case, the dichotomy in (2) is not quite exclusive and the authors conjecture that in fact \[ d_{TV}\left(G(n,p),G(n,p,\alpha)\right)\to 0, \text{ whenever }\left(\frac{||\alpha||_2}{||\alpha||_3}\right)^6/n^3\to \infty.\tag{3} \] The main tool employed to differentiate \(G(n,p)\) from \(G(n,p,\alpha)\) are triangle counts: \(G(n,p)\) has in expectation \(p^3 \binom{n}{3}\) triangles. In the isotropic geometric model \(G(n,p,d)\), there are in expectation about \(1+1/d^{1/2}\) times as many triangles present as in \(G(n,p)\) and this observation, together with variance estimates, can be leveraged to obtain bound on the total variation distance between the models. In fact, to obtain sharp variance estimates it turned out in [V. Bentkus, Theory Probab. Appl. 49, No. 2, 311–323 (2004; Zbl 1090.60019); translation from Teor. Veroyatn. Primen. 49, No. 2, 400–410 (2004)], that the correct quantity to consider is a count of signed triangles. Analysing the variance of signed triangles in \(G(n,p,\alpha)\) yields \(\left(\frac{||\alpha||_2}{||\alpha||_3}\right)^6/n^3\) as the crucial quantity in distinguishing \(G(n,p,\alpha)\) from \(G(n,p)\) and this forms the basis of the conjecture (3).
For the entire collection see [Zbl 1446.00029].