Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$?

share|improve this question
1  
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. –  Boris Bukh Jan 6 '10 at 14:38
    
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. –  Konrad Swanepoel Jan 6 '10 at 22:23

4 Answers 4

up vote 6 down vote accepted

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).

share|improve this answer
1  
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. –  Martin Rubey Jan 7 '10 at 12:46
    
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. –  Konrad Swanepoel Jan 7 '10 at 20:56

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.

share|improve this answer
    
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.) –  Konrad Swanepoel Dec 11 '09 at 11:54

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)$.

share|improve this answer
    
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))$. –  Konrad Swanepoel Jan 6 '10 at 21:35
    
So this shows that the asymptotics is in fact exponential in the number of vertices $n^2$. –  Konrad Swanepoel Jan 6 '10 at 21:37
    
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? –  Michael Lugo Jan 6 '10 at 22:13
1  
The two constants are not the same, but Konrad's answer is for the square grid. See the updated version of Martin's answer. –  David Speyer Jan 7 '10 at 13:43

You might try looking at:

http://arxiv.org/pdf/0809.2551

share|improve this answer
    
An interesting reference. Unfortunately they do not really look at the asymptotics as both hieght and width go to infinity. –  Konrad Swanepoel Jan 6 '10 at 22:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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