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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Online Encyclopedia of Integer Sequences The exact formulas don't look easy to derive. $\endgroup$
    – Peter Shor
    Jul 11, 2015 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$
    – john mangual
    Jul 11, 2015 at 11:06
  • $\begingroup$ They cover a lot of different objects, including the quadrillage planaire, which is the $m \times n$ grid. $\endgroup$
    – Peter Shor
    Jul 11, 2015 at 11:17

2 Answers 2

Reset to default
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.

Improve this answer
$\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$
    – Areaperson
    Jul 29, 2018 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$
    – David Eppstein
    Jul 30, 2018 at 7:30
  • $\begingroup$ It was published in Acta Math 185 (2000) no. 2, 239-286. $\endgroup$
    – Areaperson
    Jul 31, 2018 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.

Improve this answer
$\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, 2015 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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