Automatic Generation of Generating Functions for the Number of Spanning Trees for Grid Graphs (and Much More General Creatures) of Fixed (but arbitrary!) Width

By Shalosh B. EKHAD and Doron ZEILBERGER

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger:

http://www.math.rutgers.edu/~zeilberg/pj.html. Written: April 2, 2011.

Very Important: This article comments on the Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/KamaEtzim. Some sample input and out-

put can be gotten from the “front” of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/etzim.html .

This work extends the beautiful work of Paul Raff[1], that in turn, extended pioneering work of Frans Faase[2] and others (see the references of [1]) about counting spanning trees in grid graphs and more general creatures. However, our approach is very naive (in a good way!) .

For a graph G, let T (G) be its number of spanning trees. Also let P_{n} be the path-graph of length n: 1 − 2 − … − n. It is fairly easy to see that for a fixed m, the generating function

F_{m}(z) = ∑_{n=0}^{∞} T (P_{n} × P_{m})z^{n}

is a rational function of z. The Maple package KamaEtzim automatically computes F_{m}(z) for any inputted numeric m. (See procedure GFrect(m,z) of KamaEtzim). In fact, we do something much more general. For any graph G, KamaEtzim can (explicitly!) compute

F_{G}(z) = ∑_{n=0}^{∞} T (P_{n} × G)z^{n} .

(See procedure GFG(G,m,z,K) in KamaEtzim) .

In fact we do something even more general! For any graph G, on m vertices, and for any bipartite (m, m) graph C, let M_{n}(G, C) be the graph on mn vertices where the edges among

1 + im , 2 + im , ... , m + im

mimic the graph G (for i = 0, …, n − 1), and in addition the edges between

1 + im , 2 + im , ... , m + im

and

1 + (i + 1)m , 2 + (i + 1)m , ... , m + (i + 1)m

(0 ≤ i < n − 1) mimic the edges of C, given as a set of (up to m^{2}) ordered pairs {[α, β]}. [α, β] ∈ C means that there is an edge between vertex α + im and vertex β + (i + 1)m for 0 ≤ i < n − 1. Note that when C is the monogamy bipartite graph {[1, 1], …, [m, m]}, where Mr i is connected to Mrs i (but no cheating!), then M_{n}(G, C) reduces to the Cartesian product G × P_{n}.

KamaEtzim can (explicitly!) compute the rational function (of z):

F_{G,C}(z) = ∑_{n=0} T (M_{n}(G, C))z^{n} .

(See procedure FGt(G,C,m,z,K) in KamaEtzim.)

The output: For the (already known [1][2]) generating functions for the number of spanning trees on grid graphs P_{m} × P_{n} (resp. cylinder graphs C_{m} × P_{n}) for 2 ≤ m ≤ 6 see:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oKamaEtzim1
(resp. http://www.math.rutgers.edu/~zeilberg/tokhniot/oKamaEtzim2) .

For the brand-new generating function, for the number of spanning trees on grid graphs P_{7} × P_{n}

see: http://www.math.rutgers.edu/~zeilberg/tokhniot/oKamaEtzim3 .

The Method

The computer first constructs the graphs M_{n}(G, C) for sufficiently many n, then finds the adjacency matrices, and then uses the matrix tree theorem (see wikipedia or any combinatorics textbook) to compute the sequence, and finally guesses a rational function describing this sequence. Voilà tout!

References

1. Paul Raff, Spanning Trees in Grid Graphs, arXiv:0809.2551v1 , 15 Sept. 2008. (Note that some of the entries in the table of p. 9 are in error (they correctly represent something else, namely the cylinder graphs).

2. Frans Faase, On the number of specific spanning subgraphs g ×p_{n}, Ars Combinatorica 49 (1998), 129-154.

Shalosh B. Ekhad and Doron Zeilberger, Department of Mathematics, Hill Center-Busch Campus, Rugters University, 110 Frelinghuysen Rd, Piscataway, NJ 08544, USA.

Email: [c/o zeilberg zeilberg]@math.rutgers.edu .