7
$\begingroup$

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way.

Start with a set $S$ which contains only the vertex at the top left corner of the grid graph (i.e location $(0,0)$), and an empty set $T$ which will contain our spanning tree.
Now pick an edge at random (with equal probability) from the set of edges $(p,q)\in E(G)$ such that $p \in S$ and $q \not \in S$.
Add this edge to our set $T$ and add $q$ to set $S$, repeat this process until we obtain a spanning tree.

Now, the problem is this:
What is the probability that a given vertex of the grid graph at location $(x,y)$ is a leaf in our spanning tree? In general, what is the expected number of leafs in a spanning tree constructed in this way? If this problem is too difficult, what can we say about a smaller grid? For example if we consider an $N$ x $2$, $N$ x $3$, ... e.t.c grid graph

Note:
This was inspired by a more general question asked by Nick Wu on Quora

$\endgroup$
  • 1
    $\begingroup$ Are all edges $(p, q)$ equiprobable? $\endgroup$ – Smylic Nov 21 '13 at 6:39
  • $\begingroup$ Yes, all edges $(p,q)$ where $p \in S$ and $q \not \in S$ are equally likely to be chosen at any given instance. $\endgroup$ – Obinna Okechukwu Nov 21 '13 at 7:02
  • 2
    $\begingroup$ My only issue with the example of the $N \times N$ grid is that all the vertices will be slightly different. The torus $\mathbb{Z}_n \times \mathbb{Z}_n$ would be simpler... is that acceptable? $\endgroup$ – cactus314 Nov 27 '13 at 14:21
  • $\begingroup$ Yes, that would be interesting, I'm basically trying to see if there are known techniques for solving problems of this nature. $\endgroup$ – Obinna Okechukwu Nov 27 '13 at 16:46
2
$\begingroup$

I used a computer to compute the probabilities on small grids.

For $2x2$ :

$$\begin{array}{|c|c|}\hline\frac{1}{4}&\frac{1}{2}\\\hline\frac{1}{2}&\frac{3}{4}\\\hline\end{array}=\begin{array}{|c|c|}\hline \frac{ 1}{4 } & \frac{ 2}{4 } \\\hline \frac{ 2}{4 } & \frac{ 3}{4 } \\\hline \end{array}$$

For $3x2$ :

$$\begin{array}{|c|c|}\hline \frac{7}{27}&\frac{19}{144}&\frac{5}{8}\\\hline \frac{14}{27}&\frac{7}{24}&\frac{161}{216}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{112}{432} & \frac{57}{432} & \frac{270}{432} \\\hline \frac{224}{432} & \frac{126}{432} & \frac{322}{432} \\\hline \end{array} $$

For $4x2$ : $$\begin{array}{|c|c|}\hline \frac{299}{1152}&\frac{4261}{31104}&\frac{1949}{10368}&\frac{41491}{62208}\\\hline \frac{7177}{13824}&\frac{6283}{20736}&\frac{1829}{6912}&\frac{29843}{41472}\\\hline\end{array}= \begin{array}{|c|c|}\hline \frac{32292}{124416} & \frac{17044}{124416} & \frac{23388}{124416} & \frac{82982}{124416} \\\hline \frac{64593}{124416} & \frac{37698}{124416} & \frac{32922}{124416} & \frac{89529}{124416} \\\hline \end{array}$$

For $3x3$ :

$$\begin{array}{|c|c|}\hline \frac{1459}{5400} & \frac{6359}{43200} & \frac{143129}{216000} \\\hline \frac{6359}{43200} & \frac{153293}{972000} & \frac{483341}{1296000} \\\hline \frac{143129}{216000} & \frac{483341}{1296000} & \frac{1217}{1500} \\\hline \end{array}$$

For larger grids, numerators and denominators don't fit in 64 bits integers, and computations become slow. But those results seem to show that there is no obvious answer to your question.

$\endgroup$
  • $\begingroup$ Would you mind if I can know the details of how you computed these probabilities? Did you just count the number of times a cell is leaf and divide by the total number of trees? The algorithmic details might be a little useful. I really don't care about the programming language it was written in. Thanks! $\endgroup$ – Obinna Okechukwu Nov 22 '13 at 14:33
  • $\begingroup$ I already computed a few but wasn't sure of how to keep track of generated spanning trees without using up too much memory in the computer. That's why the algorithmic details might be useful. $\endgroup$ – Obinna Okechukwu Nov 22 '13 at 14:36
  • 1
    $\begingroup$ I used maps over balanced binary trees to keep track of the partial spanning trees and the probability to obtain them (because one spanning tree can be obtained from several different choices path). Once each spanning tree is computed with its probability, I just sum the probabilities of all such trees where one specific node is a leaf to obtain the probability of this node. $\endgroup$ – Xoff Nov 22 '13 at 14:46
  • 1
    $\begingroup$ Consider the grid $3\times 2$ with $$\begin{array}{|c|c|c|}\hline A&B&C\\ \hline D&E&F\\ \hline\end{array}$$ The tree $A-B-C-F-E-D$ can only be obtain from the choice $A-B$ ($p=\frac{1}{2}$ among $(A-B)$, $(A-D)$), then $B-C$ ($p=\frac{1}{3}$ among $(A-D)$, $(B-C)$, $(B-E)$) then $C-F$ ($p=\frac{1}{3}$), then $(F-E)$ $p=\frac{1}{3}$, then $E-D$ $p=\frac{1}{2}$. So the probability of this tree is $\frac{1}{2^2.3^3}$. $\endgroup$ – Xoff Nov 24 '13 at 13:25
  • 1
    $\begingroup$ It must be 1, because at each step, if you have $n$ possible edges, each edges has $p=\frac{1}{n}$. So the sum is always 1 at each step. But you must take into account that some trees can be obtained from different choices order. $\endgroup$ – Xoff Nov 24 '13 at 13:35
1
$\begingroup$

You asked some questions related to the Uniform Spanning Tree model in Statistical Mechanics and Combinatorics. Let's try to address your first question:

What's the probability a given vertex of the grid $(x,y) \in N \times N$ is a leaf in our spanning tree?

First, we need to count all the spanning trees of the $N \times N$ grid. This is in the Online Encyclopedia of Integer Sequences A007341

1, 4, 192, 100352, 557568000, ...

This number grows large very quickly. And we have an exact formula:

$$ a_n = \frac{2^{n^2-1} }{n^2} \prod_{m_1, m_2 =1}^{n-1} \left(2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}\right) \in \mathbb{Z}$$

One way to check this is an integer is to verify this is invariant under the Galois group of $\mathbb{Q}[\omega]$ with $\omega^n = 1$ is a root of unity.

We can also tell that from the $2^{n^2}$ factor that we need $n^2$ bits in order to uniquely describe our spanning tree.

This formula is disccussed on MathOverflow: https://mathoverflow.net/questions/8497/number-of-spanning-trees-in-a-grid

Deriving the Product Formula for the Number of Spanning Trees

We can use the Matrix Tree Theorem which states that number of trees of any graph - in our case the $N \times N$ grid - is equal to the determinant of the Laplacian of the grid.

$$ \# \{ \text{spanning trees}\} = \det \Delta_G = \frac{1}{n}\lambda_1\dots \lambda_{n-1}$$

In the case of the $\{ 1, 2, \dots n \} \times \{ 1, 2, \dots n \}$ we can write down explicit eigenfunctions so that

$$ \lambda \; f(x,y) = \frac{1}{4} \big[ f(x+1,y) + f(x-1,y) + f(x,y+1) + f(x,y-1)\big] $$

The functions we get are $(x,y) \mapsto \exp\left(\frac{\pi m_1 x}{n}\right)\exp\left(\frac{\pi m_2 x}{n}\right) $ with eigenvalues $\lambda = 2 - \cos \frac{\pi m_1}{n} - \cos \frac{\pi m_2}{n}$.

So, the number of spanning trees on the grid has something to do with Harmonic analysis on $\mathbb{Z}_N^2$, random walks and the roots of unity.

$\endgroup$
  • $\begingroup$ Thanks! But the random spanning tree generated isn't a uniform spanning tree. Intuitively, we see that more trees are likely to have the lower right vertex as a leaf. $\endgroup$ – Obinna Okechukwu Nov 29 '13 at 19:19
  • $\begingroup$ In fact, we can say that the probability that the lower right vertex is a leaf is greater than the probability that the top left vertex is a leaf. If the trees generated were uniform then they would be equal by symetry since we can simply rotate (and/or reflect) every tree which has the lower right as a leaf to form a tree with the top left as a leaf (and vice versa). $\endgroup$ – Obinna Okechukwu Nov 29 '13 at 19:27
  • 1
    $\begingroup$ I see. Judging from your link to Quora, you are interested in comparing Prim's algorithm and Kruskal's algorithm on $\mathbb{Z_m} \times \mathbb{Z}_m$. Even if this model isn't the same, the strategy should apply... $\endgroup$ – cactus314 Nov 29 '13 at 22:16
  • 1
    $\begingroup$ Prim's algorithm in this case may be related to Diffusion Limited Aggregation $\endgroup$ – cactus314 Nov 29 '13 at 23:38
  • $\begingroup$ ^ That's interesting. I'll look into that. Thanks! $\endgroup$ – Obinna Okechukwu Nov 30 '13 at 1:43
0
$\begingroup$

Not sure if it helps and it's a bit late but for the case of the $N\times N$ grid in the limit of $N\rightarrow \infty$ the following exact result for the leaf-probability has been derived here based on an equivalence to the Abelian sandpile model:

$$\frac{8}{\pi^2}\left( 1 - \frac{2}{\pi}\right) \approx 0.29454$$

$\endgroup$

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.