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$?.
2
-
1$\begingroup$ Roughly speaking, if $n$ is large, this problem would be related to the following: Let $G$ be a graph whose nodes are the $n\times n$ integer lattice, and connect each point $(i,j)$ to its four neighbors independently with probability $p$. This lecture says that if $p\geq 1/2$, then the probability that $G$ is connected goes to 1: cs.cornell.edu/courses/cs683/2008sp/lecture%20notes/… This is different from your problem because the connection probabilities are not independent, as in this model, but this might be a direction to look in. $\endgroup$– John Gunnar CarlssonCommented Jul 5, 2014 at 9:31
-
1$\begingroup$ The only way neighboring squares are disconnected is if $r \lt \sqrt{5}$, with the probability only becoming substantial when $r$ is significantly less than 2. When a point is chosen from a square with four neighboring squares (I'm ignoring the diagonal), that square is disconnected from its neighbors only when $r \lt \sqrt{5/2}$. The most likely case is a disconnected corner square, for which it should be straightforward to compute a probability given r. $\endgroup$– The Masked AvengerCommented Jul 5, 2014 at 18:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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) $.
$\begingroup$
$\endgroup$
2
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.
answered Jul 5, 2014 at 18:59
-
$\begingroup$ Similarly, considering disks of radius 1/2, connected components can't have more than 6 points. It may be that this kind of analysis will yield c_n and r_n such that a radius of r_n implies connected components have at most c_n points inside an n by n domain. Gerhard "Roundly Thinking About This Problem" Paseman, 2014.07.05 $\endgroup$ Commented Jul 5, 2014 at 20:28
-
$\begingroup$ It seems I underestimated the power of the inscribable disk. Nevertheless, I think one cannot have 8 points in a connected configuration using r = 1/2. I still think this kind of analysis will be useful for r less than .707 . Gerhard "Going In Circles Over This" Paseman, 2014.07.05 $\endgroup$ Commented Jul 5, 2014 at 20:35