Let $G_n$ be the $4$-regular tree of depth $n$, that is to say the finite graph given by the ball of radius $n$ in the Cayley graph of the free group on two generators. By the root I mean the vertex at the center. If I choose vertices uniformly at random from $G_n$, what is the probability that when I choose the root it will be connected to the boundary of the graph by a path through vertices I have chosen already? Equivalently, if I take a random ordering of the vertices of $G_n$, what is the probability that the segment preceding the root will contain a path to the boundary? More precisely, I would like to know whether this probability approaches $0$ as $n$ goes to infinity.


It converges to a strictly positive limit.

Perhaps easiest to think about it in this way; assign every vertex an independent time which is uniform on $[0,1]$. If the vertices of $G_n$ are added in increasing order of their times, then this is equivalent to adding them one by one uniformly as you describe. But this way we can easily think about all the vertices in the infinite graph simultaneously.

Now condition on the time of the root. Given that this time is $p$, the set of vertices preceding the root contains each other vertex independently with probability $p$. Call this the set of open vertices. Effectively this is percolation with a random probability $p$ (itself chosen uniformly on $[0,1]$).

If we do percolation with probability $p$, then there exists an infinite open path starting from the root with positive probability iff $p>1/3$. This is almost the same as the probability of survival of a Galton-Watson branching process whose offspring distribution is Binomial($3,p$); the difference is that here the root has $4$ possible offspring, while each other vertex has only $3$. The probability (as a fuction of $p$) can be quite easily obtained as the solution of a recursive equation. To get the probability that the set of open vertices contains an infinite path from the root, integrate over $p$ from $1/3$ to $1$.

The limit as $n\to\infty$ of the probability that the set of open vertices contains a path from the root to distance $n$ is then just this probability that the set of open vertices contains an infinite path from the root.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.