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?
Does the infinite graph of diagonals have an infinite component?
graph theory
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.)