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$
  • 2
    $\begingroup$ Online Encyclopedia of Integer Sequences The exact formulas don't look easy to derive. $\endgroup$ – Peter Shor 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$ – john mangual 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$ – Peter Shor 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$
  • $\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$ – Lorenzo 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$ – David Eppstein Jul 30 '18 at 7:30
  • $\begingroup$ It was published in Acta Math 185 (2000) no. 2, 239-286. $\endgroup$ – Lorenzo 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$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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