  This paper deals with the problem of detecting non-isotropic high-dimensional
geometric structure in random graphs. Namely, we study a model of a random
geometric graph in which vertices correspond to points generated randomly and
independently from a non-isotropic $d$-dimensional Gaussian distribution, and
two vertices are connected if the distance between them is smaller than some
pre-specified threshold. We derive new notions of dimensionality which depend
upon the eigenvalues of the covariance of the Gaussian distribution. If
$\alpha$ denotes the vector of eigenvalues, and $n$ is the number of vertices,
then the quantities $\left(\frac{||\alpha||_2}{||\alpha||_3}\right)^6/n^3$ and
$\left(\frac{||\alpha||_2}{||\alpha||_4}\right)^4/n^3$ determine upper and
lower bounds for the possibility of detection. This generalizes a recent result
by Bubeck, Ding, R\'acz and the first named author from [BDER14] which shows
that the quantity $d/n^3$ determines the boundary of detection for isotropic
geometry. Our methods involve Fourier analysis and the theory of characteristic
functions to investigate the underlying probabilities of the model. The proof
of the lower bound uses information theoretic tools, based on the method
presented in [BG15].
