1
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\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

0

Reset to default

Your Answer

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