Suppose we connect the points of $V = \mathbb{Z}^2$ using the set of undirected edges $E$ such that either $(i, j)$ is connected to $(i + 1, j + 1)$, or $(i + 1, j)$ is connected to $(i, j + 1)$, independently and uniformly at random for all $i, j$.

(Inspired by the title and cover of this book.)

What is the probability that this graph has an infinitely large connected component? Similarly, consider $\mathbb{R}^2 \setminus G$, the complement of the planar embedding of the graph. What is the probability that the complement has an infinite connected component?

Clearly, if all the diagonals point the same way, both the graph and its complement have an infinite component. How about a uniform random graph of the above kind?

  • 2
    $\begingroup$ AFAICS, the dual graph of any planar graph is connected, so is your second question really whether the dual graph is infinite? Or are you talking about a different notion of dual graphs? $\endgroup$ – Emil Jeřábek Aug 19 '15 at 15:48
  • 2
    $\begingroup$ As for finiteness: while cycles are notably absent from the illustration inspiring this question, the expected number is infinite (for each $i,j$, the edges in squares $(2i,2j),(2i,2j+1),(2i+1,2j),(2i+1,2j+1)$ form a cycle with probability $1/16$, independently). $\endgroup$ – Klaus Draeger Aug 19 '15 at 16:12
  • $\begingroup$ @EmilJeřábek Sorry, I do not mean dual in the classical sense -- I've edited to clarify that I mean the complement of the planar embedding. $\endgroup$ – Mathias Rav Aug 20 '15 at 18:30

The probability is 0.

This follows from the following theorem (see Theorem 5.33 in Grimmett's Probability on Graphs, http://www.statslab.cam.ac.uk/~grg/books/USpgs-rev3.pdf):

Theorem Consider bond percolation on $\mathbb Z^2$, where each edge between lattice points is open with probability $\frac12$. The probability that the origin is in an infinite connected component is 0.

We can reduce from our problem to this problem: basically it is just 2 disjoint (but dependent) copies of bond percolation on $\mathbb Z^2$. Consider the configuration $D_1$ where the edges form an infinite lattice of diamonds containing the origin. If we flip all edges, we get another infinite lattice of diamonds $D_2$. Consider the intersection of the actual configuration with $D_1$ and with $D_2$. Each of these is exactly the model of bond percolation on $\mathbb Z^2$, just rotated $45^{\circ}$. The probability that any point is in the infinite cluster is hence 0 (No edge in $D_1$ can be connected to an edge in $D_2$.).

To conclude, note that the sum of a countable number of events with probability 0 has probability 0; sum over the probability that any lattice point is in an infinite cluster.

(The existence of arbitrarily large components is a red herring. One should fix a point, and ask if it's in an unbounded component.)

  • $\begingroup$ If we fix the origin and ask if it is in an unbounded component, then we can disregard all edges in $D_2$ and we remain with a single instance of bond percolation on $\mathbb{Z}^2$ with the edges in $D_1$. A useful illustration is Bollobás and Riordan 2008, Figure 2, rotated 45 degrees. $\endgroup$ – Mathias Rav Aug 26 '15 at 15:30

Hmm, well, here's one first attempt. Let's observe two important things:

  1. If this graph has an infinitely large connected component, by König's infinity lemma, it has an infinite simple path.
  2. The event that the graph has an infinite simple path is independent of each individual choice of edge orientation (and thus, every finite set of edge choices). Therefore it is a tail event and by Kolmogorov's zero-one law the probability is either zero or one.

So, is it zero or one? It's not immediately clear, though we can make a guess, since by the "infinite monkeys with typewriters" theorem, this graph contain simple paths of arbitrarily large length with probability one. Of course, more is needed to rigorously prove that it actually has an infinite path with probability one.

  • 3
    $\begingroup$ It’s also a good idea to observe 0. The event that the graph has an infinite connected component is Borel, hence measurable, hence the question makes sense in the first place. (This is not obvious when restated with infinite simple paths.) $\endgroup$ – Emil Jeřábek Aug 20 '15 at 13:10

Here's some weak empirical evidence that the answer is yes. Let $G_n$ be a random graph on the $2n+1 \times 2n+1$ lattice defined by picking each diagonal randomly. Here's a plot of reachability probability estimates vs. $n$ (ignoring the vertices which are always unreachable due to parity).

If we rescale the square to $[0,1]^2$, the probability appears to converge to a smooth function independent of scale, which would mean even more: that the probability of the origin reaching infinity is positive.

However, it's also possible that I haven't computed far enough out to see the downwards trend (the $n = 800$ plot does seem a little smaller than the others).

Code here: https://gist.github.com/girving/16a0ffa1f0abb08934c2

reachability vs. $n$


Update: As pointed out in the comments, the lemma does not imply infinite paths after all, so this answer overall is wrong. Not sure if it can be used in another probabilistic way.

The answer is yes: an infinite path exists. Indeed, an infinite path exists for every such graph; probability is not required.

Lemma: Let $G$ be any diagonal graph on the $n \times n$ lattice, with $n \ge 2$. Then there is either a path from left to the right through even parity vertices or a path from the top to the bottom through odd parity vertices.

Proof sketch: This is essentially the determinacy theorem in Hex on a different graph. The even and odd parity halves of $G$ are locally dual, so an obstruction in one parity is a connection in the other. However, I will omit the details since they're hard to write down without pictures and/or case analysis.

If the lemma is true, the infinite version follows from König as noted by Joe. (Update: Wrong, see comments)

  • 2
    $\begingroup$ I think the following graph consisting of nested diamonds contradicts your claim that every such graph has an infinite path: Connecting $(-n, 0)$ to $(0, n)$, $(0, n)$ to $(n, 0)$, $(n, 0)$ to $(0, -n)$ and $(0, -n)$ to $(-n, 0)$ by straight lines for all $n > 0$. This graph has components of arbitrarily large length, but it has no infinite components, since any point is in a finite component of size proportional to its L1 norm. How does your proof sketch handle this graph? $\endgroup$ – Mathias Rav Aug 21 '15 at 21:18
  • $\begingroup$ Very true, Koenig does not apply after all. $\endgroup$ – Geoffrey Irving Aug 21 '15 at 22:03
  • 2
    $\begingroup$ Specifically, I believe the lemma still holds, but of course does not imply the desired result. $\endgroup$ – Geoffrey Irving Aug 21 '15 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.