7
$\begingroup$

Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (asymptotically as $n\to\infty$)?

Can you also say something about the triangular grid generated by $(1,0)$ and $(1/2,\sqrt{3}/2)$?

$\endgroup$
2
  • 1
    $\begingroup$ The cause of beauty forces me to change the problem to the toroidal grid. Then you will have an action of $Z_m^2$ to simplify your calculations. I do not see how to show that tweaking the problem in this manner introduces only an insignificant error, though. $\endgroup$
    – Boris Bukh
    Jan 6, 2010 at 14:38
  • $\begingroup$ The triangular grid could also be changed to a torus by identifying opposite edges of a hexagonal piece. It's possible that one gets significantly more spanning trees in this way, but I have no proof either way. $\endgroup$ Jan 6, 2010 at 22:23

4 Answers 4

9
$\begingroup$

I think the best way to deal with grids is to find the general eigenfunction of the infinite grid, and then apply appropriate boundary conditions. This is an idea of Kenyon, Propp and Wilson, you can find an outline in the very last section of my Diplomarbeit link text

They only do it for the square grid, as far as I remember, but I wouldn't be surprised if the very same Ansatz works with the triangular grid.

I think that Richard Kenyon also shows how to compute the asymptotics in "Long-range properties of spanning trees in Z^2" (you can find it on his homepage) but I didn't check.

A second trick that might be useful for the triangular grid (due to Knuth), is to observe that the dual of the grid is "almost" regular. You can choose to delete the vertex corresponding to the outer face in the Laplacian when applying the matrix tree theorem, and will get a very nice matrix, I suppose.

update:

I just found a reference which proves the asymptotics for the triangular grid: On the entropy of spanning trees on a large triangular lattice. The formulas are gorgeous...

I should have remarked that the given reference contains (exact) expressions for the asymptotics of both lattices: the limit of $1/n \ln \tau(G_n)$, where $\tau(G_n)$ is the number of spanning trees of the graph with $n$ vertices, is

$$4/\pi\sum_{n\geq1} \sin(n\pi/2)/n^2 = 1.166 243 616\dots$$

for the square grid (due to Temperly 1972), and

$$5/\pi\sum_{n\geq1} \sin(n\pi/3)/n^2 = 1.615 329 736 097\dots$$

for the triangular grid (proved in the reference).

$\endgroup$
2
  • 1
    $\begingroup$ would be nice if somebody had the energy to work out a nice formula for the number of spanning trees in a triangular region of the triangular grid. $\endgroup$ Jan 7, 2010 at 12:46
  • $\begingroup$ Or for a regular hexagonal region. This should be the shape giving the largest number of minimal spanning trees for n points in the triangular lattice. I'm not so sure about the square lattice, but here the maximum number of spanning trees among n points is probably for square shapes. $\endgroup$ Jan 7, 2010 at 20:56
8
$\begingroup$

You can (write a program to) form the graph Laplacian (for n reasonably small) and use the matrix-tree theorem to get the number of spanning trees. See

http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

The triangular grid is a bit trickier to handle both on paper or on a computer; you may find techniques for the graded lexicographic index described at

http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/

and subsequent posts helpful in dealing with the triangular lattice.

EDIT: The answer is at http://www.oeis.org/A007341.

$\endgroup$
1
  • $\begingroup$ A computer won't help with asymptotics. But your link contains an exact formula, from which the asymptotics could be calculated. (I guess it is exponential.) $\endgroup$ Dec 11, 2009 at 11:54
4
$\begingroup$

Expanding on Steve Huntsman's answer, call the product which appears in A007341 f(n). That is,

$$f(n) = \prod_{k=0}^{n-1} {\prod_{l=0}^{n-1}}^\prime \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right)$$

where the $\prime$ on the second product indicates that we start at $l=1$ in the case $k = 0$. The number of interest here is $a(n) = 2^{n^2-1} f(n)/n^2$ .

The product is the exponential of a sum, so

$$\log f(n) = \sum_{k=0}^{n-1} {\sum_{l=0}^{n-1}}^\prime \log \left(2 - \cos {\pi k \over n} - \cos {\pi l \over n } \right).$$

This sum is, in turn, $n^2$ times a Riemann sum for the integral

$$ C = \int_0^1 \int_0^1 \log(2-\cos x\pi - \cos y\pi) \: dx \: dy $$

which I believe converges, although actually evaluating it numerically is tricky. If you believe that, then $\log f(n) \sim Cn^2$ as $n \to \infty$, and $\log a(n) \sim (C+\log 2) n^2$ as $n \to \infty$. From evaluating $f(n)$ for various $n$, it appears that $C$ is near $0.473$, $e^C$ is near $1.605$ and so we have

$$ a(n) \approx 3.21^{n^2} $$

where I write $p(n) \approx q(n)$ for $\log p(n)/\log q(n) \to 1 $ as $n \to \infty$, i. e. $\log p(n) \sim \log q(n)$.

$\endgroup$
4
  • $\begingroup$ According to the paper by Glasser and Wu cited in Martin's answer, the constant near 3.21 is in fact exactly $\exp(\frac{4}{\pi}(1-1/3^2+1/5^2-1/7^2+\dots))$. $\endgroup$ Jan 6, 2010 at 21:35
  • $\begingroup$ So this shows that the asymptotics is in fact exponential in the number of vertices $n^2$. $\endgroup$ Jan 6, 2010 at 21:37
  • $\begingroup$ But the Glasser-Wu paper is working over the triangular lattice; this is for the square lattice. Is there some reason the constants for the two lattices should be equal? $\endgroup$ Jan 6, 2010 at 22:13
  • 1
    $\begingroup$ The two constants are not the same, but Konrad's answer is for the square grid. See the updated version of Martin's answer. $\endgroup$ Jan 7, 2010 at 13:43
1
$\begingroup$

You might try looking at:

http://arxiv.org/pdf/0809.2551

$\endgroup$
1
  • $\begingroup$ An interesting reference. Unfortunately they do not really look at the asymptotics as both hieght and width go to infinity. $\endgroup$ Jan 6, 2010 at 22:17

Your Answer

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

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