pr.probability - Random geometric graphs and spanners

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,yin C$ is concentrated around $cln 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 $rgg 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 $pin C$ such that the set

$$P(p)equiv {mbox{all points $q$ in $C$ with }frac{d_G(p,q)}{cln 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_0in P(p)$ with $|p-q_0|leq varepsilon$ and at least one point $q_1in P(p)$ with $q_1geq 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 Omegaleft(frac{1}{varepsilon}right)frac{d_G(p,q_1)}{|p-q_1|}.$$

• Next ag.algebraic geometry - How do you define the Euler Characteristic of a scheme?
• Previous ag.algebraic geometry - Minimal number of generators of a homogeneous ideal (exercise in Harsthorne)