8
$\begingroup$

This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares.

The result is a kind of maze in the 45° rotated grid of $\sqrt2 \times \sqrt2$ squares (which I'll now consider as new unit cells $-$ more precisely, the grid cells would be in fact $\frac{\sqrt2}2 \times \frac{\sqrt2}2 $, as the width of the labyrinth paths is $\frac{\sqrt2}2 $). I was wondering about the sizes of the connected components of such a labyrinth, and so I took Joseph O'Rourke's sample illustration and colored everything bigger than $1 \times 1$ and $1 \times 2$, which yields the following outcome:

enter image description here

For the two light blue regions and the big pink one between them, I have cheated a bit in coloring, as all three have tiny "leaks" into the infinite (yellow) part outside. In a strict sense, those three big regions would have to be yellow, but I think it makes sense to consider the infinite part as essentially linked to boundary effects only.
Asking about the average area of a connected region for big $n$ may thus be an ill-defined question, and even if we only consider the "completely interior" components (i. e. here all red, green, dark blue and white ones), I guess that such a question is way too hard to be feasible. But the following should be rather easy, as it only concerns local neighborhoods:

  • What is the average proportion of components consisting of a $1 \times 1$ cell (not among all components, rather as a fraction of $n^2$, neglecting boundary effects) ?
  • Same question for $1 \times 2$ components.

Of course, the probability to obtain such a unit component inside a given $2 \times 2$ subsquare of the original grid is simply $\frac1{16}$, but we cannot conclude from this that there are a total of $\frac{n^2}{32}$ (or $\frac{n^2}{16}$?) of them in average, as the $2 \times 2$ subsquares of the original grid can overlap. It may just need a simple inclusion-exclusion approach, but I don't see how, especially for the $1 \times 2$ components.

$\endgroup$
  • $\begingroup$ I think you were right to not let the pink and blue bleed to infinity. Probably both would become finite if the grid was enlarged and more random choices made. It seems plausible that the yellow region would similarly resolve to be a number of finite regions with enough expansion. $\endgroup$ – Aaron Meyerowitz May 19 at 20:03
  • $\begingroup$ @AaronMeyerowitz That's exactly why I have said several times that $n$ should be big enough. As you say, "with enough expansion" :) BTW "bleed to infinity" I love that even though it sounds sad! $\endgroup$ – Wolfgang May 19 at 20:56
1
$\begingroup$

There are many interesting questions here, and one can probably answer some asymptotically, e.g. the tail behavior of the size of the connected component assuming it is finite (i.e., probability that the diameter is larger than $L$ for $L$ large, conditioned on being finite), or the question of percolation i.e is there a positive probability that the cluster of the origin is infinite (the cluster contains by coupling the percolation cluster of $p=1/2$ bond percolation on the 2D lattice, which is finite a.s., so I do not see a simple domination argument).

However the specific question you asked is indeed I believe easier. Here is an attempt.

Edit: Note that the question "is a vertex the center of a component of size 1" has a simple answer - it is $p_1=(1/2)^4$ (since it is determined by the neighboring squares, i.e. by 4 independent diagonals). Now apply the ergodic theorem to conclude that the asymptotic fraction of such squares is $p_1$. The reason this does not answer your question is that you asked for the asymptotic number of components, but it does give a lower bound on the fraction you asked about.

To get the answer to your question, repeat the computation for all 2x1 components, 3x1, 3x2, etc that contain the origin. That is, for a shape $Q$, compute $p_Q=P(C(0)\sim Q)$ where $C(0)$ is the shape containing $0$ and $\sim$ is up to translation of the shape. Then the events in the definition of $p_Q$ are disjoint, and $\sum p_Q\leq 1$. Now the fraction you ask about is $p_1/\sum_Q(p_Q/|Q|)$, where $|Q|$ is the number of vertices contained in the interior of $Q$.

(Former version, which looked at a somewhat different notion of component and answered a different notion of component, had: Note that the question "is the square A having (0,0) and (1,1) as vertices a component" has a simple answer - it is $p_1=(1/2)^{6}$ (since it is determined by the neighboring squares, and for a given orientation of the diagonal in $A$, only 6 of these neighbors are relevant).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I have a hard time understanding several details. E.g. "the tail behavior of the size of the connected component ": What do you mean by "THE connected component"? The biggest one, which would be the pink one above? (very fishy) Or the average size? Do we even have the same idea of "component"? For me, each colored region is one component. And then "is the square A having (0,0) and (1,1) as vertices a component" ?? The (what I call) components are rotated by 45° and composed of 4, 8, 12, ... triangles each "half of A", so I don't understand what you mean. $\endgroup$ – Wolfgang May 20 at 8:54
  • $\begingroup$ Sure my wording may be a bit unfortunate. It is meant not to mix up those small "unit squares" (of the initial $n\times n$) with what I call "cells" (i.e. the small rotated white squares). $\endgroup$ – Wolfgang May 20 at 9:00
  • $\begingroup$ @Wolfgang There is only one connected component that contains the origin (I think of your nxn grid as centered around the origin, think of a box of side n/2). This is what I called "THE" connected component. It is a random variable, and I was discussing its tail. $\endgroup$ – ofer zeitouni May 20 at 10:05
  • $\begingroup$ OK thanks for the clarification! A question like that had not at all come to my mind! $\endgroup$ – Wolfgang May 20 at 10:06
  • $\begingroup$ @Wolfgang concerning your second comment, I understood what you meant, and my answer refers to it. You can think of the diagonals as forming a path, and I am counting how many cells of the original lattice are contained in each component. BTW, this model is not far from percolation models (except that there is some dependence here compared to the standard percolation model). $\endgroup$ – ofer zeitouni May 20 at 10:07

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.