A note on estimating the dimension from a random geometric graph

Let G(n) be a random geometric graph with vertex set [n] based on n i.i.d. random vectors X-1,& mldr;,X-n drawn from an unknown density f on R-d. An edge (i,j) is present when parallel to X-i-X-j parallel to <= r(n), for a given threshold r(n) possibly depending upon n, where parallel to & sdot;parallel to denotes Euclidean distance. We study the problem of estimating the dimension d of the underlying space when we have access to the adjacency matrix of the graph but do not know r(n) or the vectors X-i. The main result of the paper is that there exists an estimator of d that converges to d in probability as n ->infinity for all densities with integral f(5)infinity and r(n)=o(1). The conditions allow very sparse graphs since when n(3/2)r(n)(d)-> 0, the graph contains isolated edges only, with high probability. We also show that, without any condition on the density, a consistent estimator of d exists when nr(n)(d)->infinity and r(n)=o(1).