10
$\begingroup$

This blog talks about generating "twisty little mazes" using a computer an enumerating them. The enumeration can be done using Wilson's algorithm to get the UST, but I don't remember the formula for how many there.

http://strangelyconsistent.org/blog/youre-in-a-space-of-twisty-little-mazes-all-alike

In principle the Matrix Tree Theorem states the number of spanning trees of a graph is equal to the determinant of the Laplacian matrix of the graph. Let $G= (E,V)$ be the graph and $A$ be the adjacency matrix, $D$ be the degree matrix, then $\Delta = D - A$ with eigenvalues $\lambda$, then:

$$ k(G) = \frac{1}{n} \prod_{k=1}^{n-1} \lambda_k $$

In the case of an $m \times n$ rectangle both $A$ and the eigenvalues should take a particularly simple form, which I can't find.

What is the exact formula (and asymptotics) for the # of spanning trees of an $m \times n$ rectangle?

enter image description here

Here is a pretty example of Wilson's algorithm in action.

$\endgroup$
3
  • 2
    $\begingroup$ Online Encyclopedia of Integer Sequences The exact formulas don't look easy to derive. $\endgroup$ Jul 11 '15 at 2:16
  • $\begingroup$ @PeterShor OEIS cites: Germain Kreweras, Complexite et circuits Euleriens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. He is the same objects as us right? $\endgroup$ Jul 11 '15 at 11:06
  • $\begingroup$ They cover a lot of different objects, including the quadrillage planaire, which is the $m \times n$ grid. $\endgroup$ Jul 11 '15 at 11:17
9
$\begingroup$

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known.

According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to $$\exp (z_{\mathrm{sq}}mn)$$ where $$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$ but I'm not sure whether this is a rigorous bound or the result of heuristic physics-based reasoning. The same paper also gives asymptotic formulas of similar type when $m$ is fixed to a small constant and $n$ is large.

$\endgroup$
3
  • $\begingroup$ There are precise asymptotic formulas for the number of spanning trees in a rectangle (and more general sequences of subgraphs described by rectilinear polygons) given here: arxiv.org/pdf/math-ph/0011042.pdf (specifically, corollary 2 and proposition 13) $\endgroup$
    – Elle Najt
    Jul 29 '18 at 1:01
  • $\begingroup$ Again, that's in a mathematical physics repository. Do they prove the asymptotic formulas rigorously or do they just use physics-like ansatz reasoning? $\endgroup$ Jul 30 '18 at 7:30
  • $\begingroup$ It was published in Acta Math 185 (2000) no. 2, 239-286. $\endgroup$
    – Elle Najt
    Jul 31 '18 at 16:16
0
$\begingroup$

The eigenvalues of the m-by-n rectangle graph can be used to obtain an expression for the number of perfect matchings in such graphs. See the Wikipedia article on domino tilings.

$\endgroup$
1
  • $\begingroup$ This is interesting, but can you elaborate how this adresses the question? Is there any kind of mapping between perfect matchings and spanning trees in this particular case? $\endgroup$
    – Saeed
    Jul 12 '15 at 9:14

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.