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

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

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

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

CC BY-SA 4.0
2018-09-01T17:17:13.820Z
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.
Denis
CC BY-SA 4.0
2018-09-01T21:35:18.110Z
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.
delete000
CC BY-SA 4.0
2018-09-05T14:01:29.567Z
One of the two at random, with equal probability.
delete000
CC BY-SA 4.0
2018-09-05T14:51:18.047Z
*"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.
Neal Young
CC BY-SA 4.0
2018-09-05T14:53:56.063Z
Do you have in mind that p is fixed, and then L tends to infinity?
Neal Young
CC BY-SA 4.0
2018-09-05T16:49:39.783Z
Yup, an asymptotic limit would do.
delete000
CC BY-SA 4.0
2018-09-07T11:46:47.140Z
Maybe look for something related in the literature on https://en.wikipedia.org/wiki/Percolation_theory ?
Neal Young
CC BY-SA 4.0
2018-09-07T12:42:45.400Z
A colleague of mine is a living encyclopedia of these percolation / attachment / growth problems. He told me this one is a toughie. I was wondering whether it had cropped up in some field. Maybe there are some numerics on it somewhere, but I don't even know how to search for relevant results....
delete000
CC BY-SA 4.0
2018-09-07T14:02:41.050Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/82868/discussion-between-neal-young-and-delete000).
Neal Young
<co.combinatorics><tree><statistical-physics><asymptotics>
Growth of random square lattice trees
delete000
# Growth of random square lattice trees

(Asked by: username_0 on 2018-08-31)

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.

**Tags:** co.combinatorics, tree, statistical-physics, asymptotics
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: One of the two at random, with equal probability.  
> **username_2**: *"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.  
> **username_2**: Do you have in mind that p is fixed, and then L tends to infinity?  
> **username_0**: Yup, an asymptotic limit would do.  
> **username_2**: Maybe look for something related in the literature on https://en.wikipedia.org/wiki/Percolation_theory ?  
> **username_0**: A colleague of mine is a living encyclopedia of these percolation / attachment / growth problems. He told me this one is a toughie. I was wondering whether it had cropped up in some field. Maybe there are some numerics on it somewhere, but I don't even know how to search for relevant results....  
> **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/82868/discussion-between-neal-young-and-delete000).  

---

## 0 answers

