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.

  • $\begingroup$ 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. $\endgroup$
    – Denis
    Sep 1, 2018 at 17:17
  • $\begingroup$ 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. $\endgroup$
    – delete000
    Sep 1, 2018 at 21:35
  • $\begingroup$ One of the two at random, with equal probability. $\endgroup$
    – delete000
    Sep 5, 2018 at 14:01
  • $\begingroup$ "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. $\endgroup$
    – Neal Young
    Sep 5, 2018 at 14:51
  • $\begingroup$ Do you have in mind that p is fixed, and then L tends to infinity? $\endgroup$
    – Neal Young
    Sep 5, 2018 at 14:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.