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

<ol>
<li>If this graph has an infinitely large connected component, by König's infinity lemma, it has an infinite simple path.</li>
<li>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.</li>
</ol>

<p>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 <em>infinite</em> path with probability one.</p>

CC BY-SA 3.0
2015-08-20T13:10:12.733Z
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.)
Emil Jeřábek
CC BY-SA 3.0
2015-08-20T12:05:31.673Z
2015-08-20T12:05:31.673Z
Joe Bebel
<p>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).</p>

<p>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.</p>

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

<p>Code here: <a href="https://gist.github.com/girving/16a0ffa1f0abb08934c2" rel="nofollow noreferrer">https://gist.github.com/girving/16a0ffa1f0abb08934c2</a></p>

<p><a href="https://i.sstatic.net/zQc1T.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zQc1T.png" alt="reachability vs. $n$"></a></p>

CC BY-SA 3.0
2015-08-20T23:47:27.530Z
2015-08-20T23:47:27.530Z
Geoffrey Irving
<p><strong>Update:</strong> 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.</p>

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

<p><strong>Lemma:</strong> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-08-21T21:18:43.690Z
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?
Mathias Rav
CC BY-SA 3.0
2015-08-21T22:03:48.817Z
Very true, Koenig does not apply after all.
Geoffrey Irving
CC BY-SA 3.0
2015-08-21T22:09:11.963Z
Specifically, I believe the lemma still holds, but of course does not imply the desired result.
Geoffrey Irving
CC BY-SA 3.0
2015-08-21T00:20:21.773Z
2015-08-21T22:11:05.693Z
2015-08-21T22:11:05.693Z
Geoffrey Irving
<p>The probability is 0.</p>

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

<p><strong>Theorem</strong> 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.</p>

<p>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$.). </p>

<p>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.</p>

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

CC BY-SA 3.0
2015-08-26T15:30:32.723Z
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](http://arxiv.org/abs/math/0410359), rotated 45 degrees.
Mathias Rav
CC BY-SA 3.0
2015-08-26T14:14:57.590Z
2015-08-26T14:21:59.390Z
2015-08-26T14:21:59.390Z
Holden Lee
<p>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$.</p>

<p>(Inspired by the title and cover of <a href="http://10print.org/">this book</a>.)</p>

<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2015-08-19T15:48:33.507Z
AFAICS, the [dual graph](https://en.wikipedia.org/wiki/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?
Emil Jeřábek
CC BY-SA 3.0
2015-08-19T16:12:23.727Z
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).
Klaus Draeger
CC BY-SA 3.0
2015-08-20T18:30:35.563Z
@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.
Mathias Rav
<graph-theory>
Does the infinite graph of diagonals have an infinite component?
Mathias Rav
# Does the infinite graph of diagonals have an infinite component?

(Asked by: username_0 on 2015-08-19)

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](http://10print.org/).)

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?

**Tags:** graph-theory

> **Comments:**
> **username_1**: AFAICS, the [dual graph](https://en.wikipedia.org/wiki/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?  
> **username_2**: 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).  
> **username_0**: @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.  

---

## 4 answers

### Answer by username_5 on 2015-08-26. Score: 9 | Accepted answer

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

> **Comments:**
> **username_0**: 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](http://arxiv.org/abs/math/0410359), rotated 45 degrees.  

---

### Answer by username_3 on 2015-08-20. Score: 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.

> **Comments:**
> **username_1**: 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.)  

---

### Answer by username_4 on 2015-08-20. Score: 1

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$](https://i.sstatic.net/zQc1T.png)](https://i.sstatic.net/zQc1T.png)


---

### Answer by username_4 on 2015-08-21. Score: 1

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

> **Comments:**
> **username_0**: 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?  
> **username_4**: Very true, Koenig does not apply after all.  
> **username_4**: Specifically, I believe the lemma still holds, but of course does not imply the desired result.  

---

