Does the infinite graph of diagonals have an infinite component?

Question

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?

Answer 1

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.)

Answer 2

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.

Answer 3

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

Answer 4

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)