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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.