uniform spanning tree of $2 \times n$ graph

165 Views Asked by At

In Probability on Trees and Networks Chapter 1 study the uniform spanning tree on the ladder graph:

 _
|_|
|_|
|_|
...
|_|
|_|

The probability the bottom rung appears in a uniform spanning tree of this graph is $\sqrt{3}-1$ and for finite ladders, the probabilities are continued fraction convergents.

 _    _   
| |  |_  |_|
| |  |_  |_
 _|  | |  _|
 _|  |_  |
 _|  | | |_|

Why is the limit $\sqrt{3}-1$ and why do continued fractions appear here?


Here is a uniform spanning tree of a ladder graph and indeed, you get the bottom rung 7 in 10 times.

enter image description here


Maybe the identity $\frac{1}{\sqrt{3}-1} = \frac{\sqrt{3}+1}{2}$ may be useful.