| Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0, 1]d, and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds and also present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. In fact, we prove that a random geometric graph is shown is a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.; Our second result is that the spectral measure of the transition matrix of the simple random walk (SRW) on G( Xn ; r(n)) is concentrated, and in fact converges to that of the graph on the deterministic grid. This permits the approximation of various random walk based functionals on the random graph by their values on the graph on the grid. Conventional approaches from random matrix theory are inapplicable in this case because the entries are not independent. We have a novel approach to derive spectral concentration via proving concentration of the matrices in the Hilbert-Schmidt norm. |
