Random geometric graphs and spanners

2010-06-16T23:29:40Z

I would grateful to learn of work mixing random geometric graphs with random graphs under the Erdős-Renyi model, and in particular concerning spanners.

Select $n$ points uniformly at random from the unit square, and then form a graph $G=G(n,p)$ by connecting points by adding edges with probablity $p$. If $p_1$ is the threshhold for the formation of the giant component $C$, is $C$ almost surely a geometric spanner for the points it connects for $p=p_1 + \epsilon$? (My guess is: No.) One could ask a similar question about the threshold $p_2$ for complete connection of the point set. (Here perhaps the answer is: Yes?)

A geometric spanner has the property that, between any pair of points, there is path whose length is not much longer than (no more than some constant times) the Euclidean distance between those points.

Answer by Roberto Imbuzeiro Oliveira for Random geometric graphs and spanners

2010-09-01T16:21:10Z

I assume you meant $p=(1+\varepsilon)p_1$ in the first question, in which case the answer seems to be "no".

To see this, we note that, with high probability:

(i) The size of $C$ is $\Theta(n)$ (this is the classical result);

(ii) The average graph-theoretic distance $d_G(x,y)$ between two randomly chosen vertices $x,y\in C$ is concentrated around $c\ln n$ for some $c>0$ (this is proven in eg. Durrett's Random Graph Dynamics);

(iii) All points $p$ in the square are such that the ball of radius $r$ around $p$ contains $\Theta(r^2 n)$ points of $C$, simultaneously for all $r\gg \ln^2n/n$. (To see this, notice that the positions of points in the square are independent from their being or not in the giant component, then apply a VC dimension argument + part (i)).

Now let $\varepsilon>0$ be small (and fixed) and let $n$ grow. By item (ii), there is a high probability that one can find a point $p\in C$ such that the set $$P(p)\equiv {\mbox{all points $q$ in $C$ with }\frac{d_G(p,q)}{c\ln n}\in [1/2,1]}$$ has size $\geq (1-\varepsilon^2)|C|$. By part (iii), there is a high probability that at least one point $q_0\in P(p)$ with $|p-q_0|\leq \varepsilon$ and at least one point $q_1\in P(p)$ with $q_1\geq 1/3$. Since $d_G(p,q_0),d_G(p,q_1)=O(\ln n)$, this shows that: $$\frac{d_G(p,q_0)}{|p-q_0|}\geq \Omega\left(\frac{1}{\varepsilon}\right)\frac{d_G(p,q_1)}{|p-q_1|}.$$

Random geometric graphs and spanners - MathOverflow

Random geometric graphs and spanners

Answer by Roberto Imbuzeiro Oliveira for Random geometric graphs and spanners