# Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding until reaching a Manhattan distance $L/2$ from it, according to the following rules:

At each step $n=0,\dots,L/2-1$, visit all the vertices at Manhattan distance $n$ from the origin. If the current vertex is connected to the tree, then with probability $p$ connect to it its two neighboring vertices at Manhattan distance $n+1$ from the origin, and with probability $1-p$ connect only one of the two. Skip adding edges that create a cycle (i.e., an edge to a neighbor that has already been added to the tree).

Question: how does the order of the tree grown by this process scale with $L$ depending on the choice of $p$?

It is clear that limiting cases are $O(L)$ and $O(L^2)$, but I am wondering whether there is also some sort of intermediate "fractal" dimension.

• just to be sure I get your with model : this algorithm you actually get a DAG, since the vertex (2,2) for instance can be linked to the root by different paths. Sep 1, 2018 at 17:17
• Either that, or if you find that you are about to add an edge that would create a cycle (i.e., an edge to an already connected vertex), then skip adding that edge. Thanks for pointing that out. Sep 1, 2018 at 21:35
• One of the two at random, with equal probability. Sep 5, 2018 at 14:01
• "with probability 1−p connect only one of the two" --- Which one of the two? (E.g., one of the two at random? The upper-most of the two?) A-priori, it could change the answer. Sep 5, 2018 at 14:51
• Do you have in mind that p is fixed, and then L tends to infinity? Sep 5, 2018 at 14:53