Connectivity of points sampled in a grid Suppose that I partition an $n\times n$ square into $n^2$ squares $S_1 ,\dots, S_{n^2}$ each of area $1$, and then I sample a point $X_i$ uniformly at random in each $S_{i}$.  Now fix a radius $r$ and make a graph $G$ with $n^2$ nodes in it, where nodes $i$ and $j$ are connected if $\|X_i - X_j\|\leq r$.  Is there a way to approximately calculate (or bound) the probability that $G$ is connected, as a function of $r$?  Obviously, $G$ must be connected if $r\geq2\sqrt{2}$, but how does this probability decrease as $r\rightarrow0$?.
 A: This expands on the remark of "The Masked Avenger".
If $r\geq\sqrt{5}$ the graph is certainly connected, because all directly neighboring squares are connected.
If $r<\sqrt{5}$ the probability to find a disconnected 4-component in $G$ approaches 1 with $n\to\infty$.
For $r=\sqrt{5}-\epsilon$
consider a $4\times 4$ square $S$ consisting of sixteen $1\times 1$ squares.
In the inner $2\times 2$ square  the probability $p_1$ that all four points lie within a circle 
around the centre with radius $\epsilon/2$ is larger than   $ c_1 \,\epsilon^8$, for a constant $c_1>0$,
while the probability $p_2$ for the points in the outer 8 squares with a common side with the inner 
$2\times 2$ square to lie outside a circle around the centre with radius $\sqrt{5}-\epsilon/2$
is larger than   $ c_2\,\epsilon^{16}$, for a constant $c_2>0$. The probability 
for the four corner squares to have their points outside this circle is finite and larger than some constant $q>0$.
Thus the probability to find a disconnected 4-component in an $n\times n$ square is at least
$\left( 1-\left( 1-q^4\,c_1\,c_2\,\epsilon^{24} \right)^{\lfloor \frac{n}{4}\rfloor^2}\right) $.
A: If $r < \frac{1}{3}$, then the graph cannot possibly be connected. Indeed, the largest possible connected components are of four points clustered around one of the lattice points.
Proof: Suppose we have a point $A$ connected to at least two other points $B,C$. Then $A$ must be within a distance of $\frac{1}{3}$ to at least two edges of the grid, so $A$ must be within a Chebyshev ($L_{\infty}$) distance of $\frac{1}{3}$ from a lattice point. Similarly, $B$ and $C$ must also be within a Chebyshev distance of $\frac{1}{3}$ from the same lattice point.
Hence, by induction, if two points belong to a connected component of at least $3$ points, they must both be within a Chebyshev distance of $\frac{1}{3}$ from the same lattice point. But we can clearly have at most four points near a given lattice point.
