FACTORIZATIONS OF SOME WEIGHTED SPANNING TREE ENUMERATORS

JEREMY L. MARTIN AND VICTOR REINER

Abstract. We give factorizations for weighted spanning tree enumerators of Cartesian products of complete graphs, keeping track of fine weights related to degree sequences and edge directions. Our methods combine Kirchhoff’s Matrix-Tree Theorem with the technique of identification of factors.

1. Introduction

Cayley’s celebrated formula n^{n−2} for the number of spanning trees in the complete graph K_{n} has many generalizations (see [5]). Among them is the following well-known factorization for the enumerator of the spanning trees according to their degree sequence, which is a model for our results.

Cayley-Prüfer Theorem.

∑_{T ∈Tree(K_{n})} x^{deg(T)} = x_{1}x_{2} ⋯ x_{n}(x_{1} + ⋯ + x_{n})^{n−2}

where Tree(K_{n}) is the set of all spanning trees and x^{deg(T)} := ∏_{i=1}^{n} x_{i}^{deg_{T} (i)}.

Although this is most often deduced from the bijective proof of Cayley’s formula that uses Prüfer coding (see, e.g., [5, pp. 4-6]), we do not know of such a bijective proof for most of our later results. Section 2 gives a quick proof (modelling those that will follow) using a standard weighted version of Kirchhoff’s Matrix-Tree Theorem, along with the method of identification of factors.

We generalize the Cayley-Prüfer Theorem to Cartesian products of complete graphs G = K_{n_{1}} × ⋯ × K_{n_{r}}. The number of spanning trees for such product graphs can be computed using Laplacian eigenvalues. Section 3 generalizes this calculation to keep track of the directions of edges in the tree, as we now explain. Note that vertices in G are r-tuples (j_{1}, …, j_{r}) ∈ [n_{1}] × ⋯ × [n_{r}], and each edge connects two such r-tuples that differ in only one coordinate. Say that such an edge lies in direction i if its two endpoints differ in their i^{th} coordinate. Given a spanning tree T in G, define the direction monomial

q^{dir(T)} := ∏_{i=1}^{r} q_{i}^{|{edges in T in direction i}|}.

Key words and phrases. Graph Laplacian, spanning tree, Matrix-Tree Theorem.

First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-9877047.

Theorem 1.

\begin{aligned}∑_{T ∈Tree(K_{n_{1}} ×···×K_{nr})} q^{dir(T)} & = \frac{1}{n_{1} ⋯ n_{r}} ∏_{∅≠A⊂[r]} (∑_{i∈A} q_{i}n_{i})^{∏_{i∈A}(n_{i}−1)} \\ & = ∏_{i=1}^{r} q_{i}^{n_{i}−1}n_{i}^{n_{i}−2} ∏_{\begin{matrix}A⊂[r] \\ |A|≥2 \end{matrix}} (∑_{i∈A} q_{i}n_{i})^{∏_{i∈A}(n_{i}−1)} . \end{aligned}

One might hope to generalize the previous result by keeping track of edge directions and vertex degrees simultaneously. Empirically, however, such generating functions do not appear to factor nicely. Nevertheless, if one “decouples” the vertex degrees in a certain way that we now explain, nice factorizations occur. Create a variable x_{j}^{(i)} for each pair (i, j) in which i ∈ {1, 2, …, r} is a direction and j is in the range 1, 2, …, n_{i}. In other words, there are r sets of variables, with n_{i} variables x_{1}^{(i)}, x_{2}^{(i)}, …, x_{n_{i}}^{(i)} in the i^{th} set. Given a spanning tree T of G, define the decoupled degree monomial

x^{dd(T)} := ∏_{v=(j_{1},...,j_{r}) ∈ [n_{1}]×···×[n_{r}]} (x_{j_{1}}^{(1)} ⋯ x_{j_{r}}^{(r)})^{deg_{T} (v)} .  (1)

In Section 3, we prove the following generalization of the Cayley-Prüfer Theorem. Theorem 2. The spanning tree enumerator

f_{n_{1},...,n_{r}}(q, x) := ∑_{T ∈Tree(K_{n_{1}} ×···×K_{nr})} q^{dir(T)}x^{dd(T)}

is divisible by

q_{i}^{n_{i}−1},

by

(x_{j}^{(i)})^{n_{1}···n_{i−1}n_{i+1}···n_{r}}

and by

(x_{1}^{(i)} + ⋯ + x_{n_{i}}^{(i)})^{n_{i}−2}

for each i ∈ [r] and j ∈ [n_{i}]. Conjecture. The quotient polynomial

\frac{f_{n_{1},...,n_{r}}(q, x)}{∏_{i=1}^{r} q_{i}^{n_{i}−1} (x_{1}^{(i)} ⋯ x_{n_{i}}^{(i)})^{n_{1}···n_{i−1}n_{i+1}···n_{r}} (x_{1}^{(i)} + ⋯ + x_{n_{i}}^{(i)})^{n_{i}−2}}

in Z[q_{i}, x_{j}^{(i)}] has non-negative coefficients.

Empirically, this quotient polynomial seems not to factor further in general, although when one examines the coefficient of particular “extreme” monomials in the q_{i}, the resulting polynomial in the x_{j}^{(i)} factors nicely. Such nice factorizations seem to fail for the coefficients of non-extreme monomials in q_{i} when there are at least two n_{i} ≥ 3.

Section 5 shows that when all n_{i} = 2, the spanning tree enumerator f_{n_{1},...,n_{r}}(q, x) factors beautifully. Here we consider the Cartesian product

Q_{n} := \underbrace{K_{2} × ⋯ × K_{2}}_{n times},

which is the 1-skeleton of the n-dimensional cube. For the sake of a cleaner statement, we make the following substitution of the 2n variables {x_{1}^{(i)}, x_{2}^{(i)}}_{i=1}^{n}:

\begin{aligned}x_{1}^{(i)} & = x_{i}^{− \frac{1}{2}} , \\ x_{2}^{(i)} & = xi^{\frac{1}{2}} . \end{aligned}  (2)

The substitution (2) is harmless, because it is immediate from (1) that the polynomial f_{2,...,2}(q, x) is homogeneous of total degree 2(2^{n} − 1) in each of the sets of two variables {x_{1}^{(i)}, x_{2}^{(i)}}. Our result may now be stated as follows:

Theorem 3.

[ ∑_{T ∈Tree(Q_{n})} q^{dir(T)}x^{dd(T)}]_{x_{1}^{(i)} = x_{i}^{− \frac{1}{2}} , x_{2}^{(i)} = x \frac{1}{2} ; i} = q_{1} ⋯ q_{n} ∏_{\begin{matrix}A⊂[n] \\ |A|≥2 \end{matrix}} ∑_{i∈A} q_{i} (x_{i}^{−1} + x_{i}) .

This result may shed light on the problem of finding a bijective proof for the known number of spanning trees in the n-cube (see [7, pp. 61-62]).

Section 6 proves a result (Theorem 4 below), generalizing the Cayley-Prüfer Theorem in two somewhat different directions. In one direction, it deals with threshold graphs, a well-behaved generalization of complete graphs. Threshold graphs have many equivalent definitions (see, e.g., [4, Chapters 7-8]), but one that is convenient for our purpose is the following. A graph G is threshold if, after labelling its vertices by [n] := {1, 2, …, n} in weakly decreasing order of their degrees, the degree sequence λ = (λ_{1} ≥ ⋯ ≥ λ_{n}) determines the graph completely by the rule that the neighbors of vertex i are the λ_{i} smallest members of [n] other than i itself. A result of Merris [3] implies the following generalization of Cayley’s formula to all threshold graphs. It uses the notion of the conjugate partition λ′ to the degree sequence λ, whose Ferrers diagram is obtained from that of λ by flipping across the diagonal.

Merris’ Theorem. Let G be a threshold graph with vertices [n] and degree sequence λ. Then the number of spanning trees in G is ∏_{r=2}^{n−1} λ′_{r}.

The natural vertex-ordering by degree for a threshold graph G induces a canonical edge orientation in any spanning tree T of G, by orienting the edge {i, j} from j to i if j > i. Thus given a spanning tree T and a vertex i, one can speak of its indegree indeg_{T} (i) and outdegree outdeg_{T} (i).

Theorem 4. Let G be a connected threshold graph with vertices [n] and degree sequence λ. Then

∑_{T ∈Tree(G)} ∏_{i=1}^{n} x_{i}^{indeg_{T} (i)}y_{i}^{outdeg_{T} (i)} = x_{1}y_{n} ∏_{r=2}^{n−1} (∑_{i=1}^{λ′_{r}} x_{min{i,r}}y_{max{i,r}}) .

In particular, setting y_{i} = x_{i} gives

∑_{T ∈Tree(G)} x^{deg(T)} = x_{1}x_{2} ⋯ x_{n} ∏_{r=2}^{n−1} (∑_{i=1}^{λ′_{r}} x_{i}) .

The proof, sketched in Section 6, proceeds by identification of factors. The authors thank M. Rubey and an anonymous referee for pointing out that it can also be deduced bijectively from a very special case of a recent encoding theorem of Remmel and Williamson [6].

2. Proof of Cayley-Prüfer Theorem: the model

The goal of this section is to review Kirchhoff’s Matrix-Tree Theorem, and use it to give a proof of the Cayley-Prüfer Theorem. Although this proof is surely known, we included it both because we were unable to find it in the literature, and because it will serve as a model for our other proofs.

Introduce a variable e_{ij} for each edge {i, j} in the complete graph K_{n}, with the conventions that e_{ij} = e_{ji} and e_{ii} = 0. Let L be the n × n weighted Laplacian matrix defined by

L_{ij} := \begin{cases}∑_{k=1}^{n} e_{ik} & for i = j \\ −e_{ij} & for i ≠ j. \end{cases}  (3)

Kirchhoff’s Matrix-Tree Theorem [5, §5.3] For any r, s ∈ [n],

∑_{T ∈Tree(K_{n})} ∏_{{i,j}∈T} e_{ij} = (−1)^{r+s} det L̂

where L̂ is the reduced Laplacian matrix obtained from L by removing row r and column s.

We now restate and prove the Cayley-Prüfer Theorem.

Cayley-Prüfer Theorem.

∑_{T ∈Tree(K_{n})} x^{deg(T)} = x_{1}x_{2} ⋯ x_{n}(x_{1} + ⋯ + x_{n})^{n−2}

where x^{deg(T)} := ∏_{i=1}^{n} x_{i}^{deg_{T} (i)}.

Proof. Apply the substitution e_{ij} = x_{i}x_{j} to the weighted Laplacian matrix L in Kirchhoff’s Theorem. Setting f := x_{1} + ⋯ + x_{n}, one has from (3)

L_{ij} = \begin{cases}(f − x_{i})x_{j} & for i = j \\ −x_{i}x_{j} & for i ≠ j. \end{cases}

By Kirchhoff’s Theorem, the left-hand side of the Cayley-Prüfer Theorem coincides with the determinant det L̂, where L̂ is the reduced Laplacian L̂ obtained from this substituted L by removing the last row and column. We wish to show that this determinant coincides with the right-hand-side of the Cayley-Prüfer Theorem. Note that both sides are polynomials in the x_{i} of degree 2n−2, and both have coefficient 1 in the monomial x_{1}^{n−1}x_{2}x_{3} ⋯ x_{n}. Therefore it suffices to show that the determinant is divisible by each of the variables x_{j}, and also by f^{n−2}. Divisibility by x_{j} is clear since x_{j} divides every entry in the j^{th} column of L (and hence also L̂). Divisibility by f follows from Lemma 5 below, once one notices that in the quotient ring Q[x_{1}, …, x_{n}]/(f), this weighted Laplacian L (and hence L̂) reduces to a rank one matrix of the form L = −v^{T} · v, where v is the row vector [x_{1} ⋯ x_{n}]. □

The following lemma, used in the preceding proof, is one of our main tools. It generalizes from one to several variables the usual statement on identification of factors in determinants over polynomial rings (see [2, §2.4]). Lemma 5. (Identification of factors) Let R be a Noetherian integral domain (e.g., a polynomial or Laurent ring in finitely many variables over a field). Let f ∈ R be a prime element, so that the quotient ring R/(f) is an integral domain, and let K denote the field of fractions of R/(f). Let A ∈ R^{n×n} be a square matrix. If the reduction Ā ∈ (R/(f))^{n×n} has K-nullspace of dimension at least d, then f^{d} divides det A in R.

Proof. Let {v̄_{i}}_{i=1}^{d} be d linearly independent vectors in K^{n} lying in the nullspace of Ā. Extend them to a basis {v̄_{i}}_{i=1}^{n} of K^{n}. By clearing denominators, one may assume that {v̄_{i}}_{i=1}^{n} lie in R/(f)^{n}, and then choose pre-images {v_{i}}_{i=1}^{n} in R.

Letting F denote the fraction field of R, we claim that {v_{i}}_{i=1}^{n} is a basis for F^{n}. To see this, assume not, so that there are scalars c_{i} ∈ F which are not all zero satisfying

∑_{i=1}^{n} c_{i}v_{i} = 0.  (4)

Clearing denominators, one may assume that c_{i} ∈ R for all i. If every c_{i} is divisible by f, one may divide the equation (4) through by f, and repeat this division until at least one of the c_{i} is not divisible by f. (This will happen after finitely many divisions because R is Noetherian.) But then reducing (4) modulo (f) leads to a nontrivial K-linear dependence among the vectors {v̄_{i}}_{i=1}^{n}, a contradiction.

Let P ∈ F^{n×n} be the matrix whose columns are the vectors v_{i}. Note that det P is not divisible by f, or else the reductions {v̄_{i}}_{i=1}^{n} would not form a K-basis in K^{n}. Therefore, by Cramer’s Rule, every entry of P^{−1} belongs to the localization R_{(f)} at the prime ideal (f). Note the following commutative diagram in which horizontal maps are inclusions and vertical maps are reductions modulo (f):

R ⟶ R_{(f)} ⟶ F
↓  ↓
R/(f) ⟶ K

Since P^{−1} has entries in R_{(f)}, so does P^{−1}AP. For each i ∈ [d], the reduction of Av_{i} vanishes in K, so every entry in the first d columns of P^{−1}AP lies in the ideal (f). Hence det P^{−1}AP = det A is divisible by f^{d} in R_{(f)}, thus also in R. □

The authors thank W. Messing for pointing out a more general result, deducible by a variation of the above proof that uses Nakayama’s Lemma: Lemma 6. Let S be a (not necessarily Noetherian) local ring, with maximal ideal 𝔪 and residue field K := S/𝔪. Let A ∈ S^{n×n} be a square matrix such that the reduction Ā has K-nullspace of dimension at least d. Then det A ∈ 𝔪^{d}.

Lemma 5 follows from this by taking S to be the localization R_{(f)}.

3. Proof of Theorem 1

We recall the statement of Theorem 1.

Theorem 1.

∑_{T ∈Tree(K_{n_{1}} ×···×K_{nr})} q^{dir(T)} = \frac{1}{n_{1} ⋯ n_{r}} ∏_{∅≠A⊂[r]} (∑_{i∈A} q_{i}n_{i})^{∏_{i∈A}(n_{i}−1)} .

As a prelude to the proof, we discuss some generalities about Laplacians and eigenvalues of Cartesian products of graphs. We should emphasize that all results in this section refer only to unweighted Laplacians, that is, one substitutes e_{ij} = 1 for i ≠ j in the usual weighted Laplacian L(G) defined in (3).

The Cartesian product G_{1} × ⋯ × G_{r} of graphs G_{i} with vertex sets V (G_{i}) and edge sets E(G_{i}) is defined as the graph with vertex set

V (G_{1} × ⋯ × G_{r}) = V (G_{1}) × ⋯ × V (G_{r})

and edge set

\begin{matrix}E(G_{1} × ⋯ × G_{r}) \\ = ⨆_{i=1}^{r} V (G_{1}) × ⋯ × V (G_{i−1}) × E(G_{i}) × V (G_{i+1}) × ⋯ × V (G_{r}). \end{matrix}

where ⨆ denotes a disjoint union. The following proposition follows easily from this description; we omit the proof. Proposition 7. If G_{1}, …, G_{r} are graphs with (unweighted) Laplacian matrices L(G_{i}), then

L(G_{1} × ⋯ × G_{r}) = ∑_{i=1}^{r} id ⊗ ⋯ id ⊗L(G_{i}) ⊗ id ⊗ ⋯ id

where id denotes the identity, and L(G_{i}) appears in the i^{th} tensor position.

As a consequence, a complete set of eigenvectors for L(G_{1} × ⋯ × G_{r}) can be chosen of the form v_{1} ⊗⋯⊗v_{r}, where v_{i} is an eigenvector for L(G_{i}). Furthermore, this eigenvector will have eigenvalue λ_{1} + ⋯ + λ_{r} if v_{i} has eigenvalue λ_{i} for L(G_{i}).

We also will make use of the following variation of the Matrix-Tree Theorem; see, e.g., [7, Theorem 5.6.8]. Theorem 8. If the (unweighted) Laplacian matrix L(G) has eigenvalues λ_{1}, …, λ_{n}, indexed so that λ_{n} = 0, then the number of spanning trees in G is

\frac{1}{n}λ_{1} ⋯ λ_{n−1}.

Proof of Theorem 1. Both sides in the theorem are polynomials in the q_{i}, and hence it suffices to show that they coincide whenever the q_{i} are all positive integers. In that case, the left-hand side of the theorem has the following interpretation. Let K_{n}^{(q)} denote the multigraph on vertex set [n] having q parallel copies of the edge {i, j} for every pair of vertices i, j. Then the left-hand side of Theorem 1 counts the number of spanning trees in the Cartesian product

K_{n_{1}}^{(q_{1})} × ⋯ × K_{n_{r}}^{(q_{r})},

as each spanning tree T in K_{n_{1}} × ⋯ × K_{n_{r}} gives rise in an obvious way to exactly q^{dir(T)} spanning trees in K_{n_{1}}^{(q_{1})} × ⋯ × K_{n_{r}}^{(q_{r})}. It is well-known that the (unweighted)

Laplacian L(K_{n}) has eigenvalues n, 0 with multiplicities n − 1, 1, respectively [7, Example 5.6.9]. Hence L(K_{n}^{(q)}) = qL(K_{n}) has eigenvalues qn, 0 with multiplicities n − 1, 1, respectively. By Proposition 7, L(K_{n_{1}}^{(q_{1})} × ⋯ × K_{n_{r}}^{(q_{r})}) has an eigenvalue ∑_{i∈A} q_{i}n_{i} for each subset A ⊂ [r], and this eigenvalue occurs with multiplicity ∏_{i∈A}(n_{i} − 1). As the zero eigenvalue arises (with multiplicity 1) only by taking A = ∅, Theorem 8 implies that the number of spanning trees in K_{n_{1}}^{(q_{1})} × ⋯ × K_{n_{r}}^{(q_{r})} is

\frac{1}{n_{1} ⋯ n_{r}} ∏_{∅≠A⊂[r]} (∑_{i∈A} q_{i}n_{i})^{∏_{i∈A}(n_{i}−1)} .  □

4. Proof of Theorem 2

We recall here the statement of Theorem 2. Theorem 2. The spanning tree enumerator

f_{n_{1},...,n_{r}}(q, x) := ∑_{T ∈Tree(K_{n_{1}} ×···×K_{nr})} q^{dir(T)}x^{dd(T)}

is divisible by

q_{i}^{n_{i}−1},

by

(x_{j}^{(i)})^{n_{1}···n_{i−1}n_{i+1}···n_{r}}

and by

(x_{1}^{(i)} + ⋯ + x_{n_{i}}^{(i)})^{n_{i}−2}

for each i ∈ [r] and j ∈ [n_{i}].

Proof. To see divisibility by q_{i}^{n_{i}−1}, note that every spanning tree in K_{n_{1}}×⋯×K_{n_{r}} is connected, and hence gives rise to a connected subgraph of K_{n_{i}} when one contracts out all edges not lying in direction i. This requires at least n_{i} − 1 edges in direction i in the original tree.

To see divisibility by (x_{j}^{(i)})^{n_{1}···n_{i−1}n_{i+1}···n_{r}}, note that every spanning tree has an edge incident to each vertex, and therefore to each of the n_{1} ⋯ n_{i−1}n_{i+1} ⋯ n_{r} different vertices which have i^{th} coordinate equal to some fixed value j ∈ [n_{i}].

Lastly, we check divisibility by (x_{1}^{(i)} + ⋯ + x_{n_{i}}^{(i)})^{n_{i}−2}. Starting with the weighted Laplacian matrix (3) for K_{n_{1}} × ⋯ × K_{n_{r}} (regarded as a subgraph of K_{n_{1}···n_{r}}), let L be the matrix obtained by the following substitution: if {k, l} represents an edge of K_{n_{1}} × ⋯ × K_{n_{r}} in direction i between the two vertices k = (k_{1}, …, k_{r}) and l = (l_{1}, …, l_{r}), then we set

e_{kl} = q_{i} · x_{k_{1}}^{(1)} ⋯ x_{k_{r}}^{(r)} · x_{l_{1}}^{(1)} ⋯ x_{l_{r}}^{(r)} ;  (5)

otherwise we set e_{kl} = 0. Then Kirchhoff’s Theorem says that f_{n_{1},...,n_{r}}(q, x) = ± det L̂ for any reduced matrix L̂ obtained from L by removing a row and column. Thus by Lemma 5, it suffices for us to show that L̂ has nullspace of dimension at least n_{i} − 2 modulo f^{(i)} := x_{1}^{(i)} + ⋯ + x_{n_{i}}^{(i)}. In fact, we will show that L itself has nullspace of dimension at least n_{i} − 1 in this quotient. To see this, one can check that, as in Proposition 7, the matrix L has the following simpler description, due to our “decoupling” substitution of variables:

L = ∑_{i=1}^{r} X^{(1)} ⊗ ⋯ ⊗ X^{(i−1)} ⊗ q_{i}L^{(i)} ⊗ X^{(i+1)} ⊗ ⋯ ⊗ X^{(r)},

where X^{(i)} is the diagonal matrix with entries (x_{1}^{(i)})^{2}, …, (x_{n_{i}}^{(i)})^{2}, and L^{(i)} is obtained by making the substitution e_{kl} = x_{k}^{(i)}x_{l}^{(i)} in the weighted Laplacian matrix for K_{n_{i}}. In the proof of the Cayley-Prüfer Theorem, we saw that L^{(i)} has rank 1 modulo (f^{(i)}), and thus a nullspace of dimension n_{i} − 1. If v is any nullvector for L^{(i)} modulo (f^{(i)}), then the following vector is a nullvector for L modulo (f^{(i)}):

1_{n_{1}} ⊗ ⋯ ⊗ 1_{n_{i−1}} ⊗ v ⊗ 1_{n_{i+1}} ⊗ ⋯ ⊗ 1_{n_{r}}

where 1_{m} represents a vector of length m with all entries equal to 1. Since varying v leads to n_{i} − 1 linearly independent such nullvectors, the proof is complete. □

5. Proof of Theorem 3

We recall here the statement of Theorem 3, using slightly different notation. Regard the vertex set of Q_{n} as the power set 2^{[n]}, so that vertices correspond to subsets of S ⊂ [n]. For any subset S ⊂ [n], let x_{S} := ∏_{i∈S} x_{i}. Write x^{wt(T)} for the decoupled degree monomial corresponding to a tree T under the substitution (2), that is,

x^{wt(T)} = ∏_{S⊂[n]} (\frac{x_{S}}{x_{[n]\S}} )^{\frac{1}{2} deg_{T} (S)}

= ∏_{edges \{S,R\} in T} \frac{x_{S}x_{R}}{x_{[n]}}

(6)

Theorem 3.

∑_{T ∈Tree(Q_{n})} q^{dir(T)}x^{wt(T)} = q_{1} ⋯ q_{n} ∏_{\begin{matrix}A⊂[n] \\ |A|≥2 \end{matrix}} ∑_{i∈A} q_{i} (x_{i}^{−1} + x_{i}) .

Proof. As before, regard the vertex set of Q_{n} as the power set 2^{[n]}. Denote the symmetric difference of two sets S and R by S△R, and abbreviate S△{i} by S△i. Thus two vertices S, R form an edge in Q_{n} exactly when S△R is a singleton set {i}; in this case the direction of this edge is dir(e) := i. It is useful to note that the neighbors of S are

N(S) = {S△i | i ∈ [n]}.

Our goal is to show that the two sides of the theorem coincide as elements of Z[q_{i}, x_{i}, x_{i}^{−1}]. Note that the two sides coincide as polynomials in q_{i} after setting x_{i} = 1 for all i, using the special case of Theorem 1 in which all n_{i} = 2.

We next show that both sides have the same maximum and minimum total degrees as Laurent polynomials in the x_{i}. Each side is easily seen to be invariant under the substitution x_{i} ↦ x_{i}^{−1} (this follows from the antipodal symmetry of the n-cube for the left-hand side), so it suffices to show that both sides have the same maximum total degree. For the right-hand side, the maximum total degree in the x_{i} is simply the number of subsets S ⊂ [n] with |S| ≥ 2, that is, 2^{n} − n − 1.

For the left-hand side, we argue as follows. Denote by V′ the set of vertices of Q_{n} other than [n]. For any spanning tree T and vertex S ∈ V′, define ϕ(S) to be the parent vertex of the vertex S when the tree T is rooted at the vertex [n] (that is, ϕ(S) is the first vertex on the unique path in T from S to [n]); then the edges of T are precisely

E(T) = {{S, ϕ(S)} | S ∈ V′} .

One has |ϕ(S)| = |S| ± 1 (because ϕ(S) = S△i for some i). Therefore the total degree of the monomial x^{wt(T)} will be maximized when |ϕ(S)| = |S| + 1 for all S ∈ V′; for instance, when ϕ(S) = S ∪ {max([n] \ S)}. In this case, that total degree is

∑_{{S,ϕ(S)}∈T} (|S| + |ϕ(S)| − n) = ∑_{S∈V′} (2|S| + 1 − n) = 2^{n} − n − 1.

Having shown that both sides have the same total degree in the q_{i}, the same maximum and minimum total degrees in the x_{i}, and that they coincide when all x_{i} = 1, it suffices by unique factorization to show that the left-hand side is divisible by each factor on the right-hand side, that is, by

f_{A} := ∑_{i∈A} q_{i} (x_{i}^{−1} + x_{i}) .

Henceforth, fix A ⊂ [n] of cardinality ≥ 2. It is not hard to check that f_{A} is irreducible in Z[q_{i}, x_{i}, x_{i}^{−1}], using the fact that it is a linear form in the q_{i}.

Starting with the weighted Laplacian matrix (3) for Q_{n}, whose rows and columns are indexed by subsets S ⊆ [n], let L be the matrix obtained by making the substitutions

e_{S,R} = \begin{cases}\frac{q_{i}x_{S}x_{S△i}}{x_{[n]}} & for S△R = \{i\}, \\ 0 & for |S△R| > 1. \end{cases}

By Kirchhoff’s Theorem, the left-hand side in Theorem 3 is the determinant of the reduced Laplacian matrix L̂ obtained from L by removing the row and column indexed by S = ∅. It therefore suffices to show that the reduction of L̂ modulo (f_{A}) has nontrivial nullspace. We will show that

v := ∑_{∅≠S⊂[n]} (x_{A}^{2} − (−1)^{|A∩S|}(x_{A\S})^{2}) ϵ_{S}  (7)

is a nullvector^{1}, where ϵ_{S} is the standard basis vector corresponding to S. Note that the entries of v are not all zero modulo (f_{A}); it remains to check that every entry (L̂v)_{R} of L̂v is a multiple of f_{A}. Since L̂_{R,S} = 0 unless S = R or S = R△i

1The form of the nullvector (7) was suggested by experimentation using the computational commutative algebra package Macaulay [1] to compute the nullspace of L̂ in the quotient ring modulo (f_{A}).

10 JEREMY L. MARTIN AND VICTOR REINER

for some i, one has

(L̂v)_{R} = L̂_{R,R} v_{R} + ∑_{i=1}^{n} L̂_{R,R△i} v_{R△i}

= ∑_{i=1}^{n} \frac{q_{i}x_{R}x_{R△i}}{x_{[n]}} (x_{A}^{2} − (−1)^{|A∩R|}(x_{A\R})^{2})

− ∑_{i=1}^{n} \frac{q_{i}x_{R}x_{R△i}}{x_{[n]}} (x_{A}^{2} − (−1)^{|A∩(R△i)|}(x_{A\(R△i)})^{2})

= \frac{x_{R}}{x_{[n]}} ∑_{i=1}^{n} q_{i}x_{R△i} ((−1)^{|A∩(R△i)|}(x_{A\(R△i)})^{2} − (−1)^{|A∩R|}(x_{A\R})^{2}) . (8)

If i ∉ A, then A ∩ R = A ∩ (R△i) and A \ R = A \ (R△i), so the summand in (8) is zero. If i ∈ A, then |A ∩ R| = |A ∩ (R△i)| ± 1, so one may rewrite (8) as follows:

(L̂v)_{R} = −(−1)^{|A∩R|} \frac{x_{R}}{x_{[n]}} ∑_{i∈A} q_{i}x_{R△i} ((x_{A\(R△i)})^{2} + (x_{A\R})^{2}) .  (9)

Note also that when i ∈ A,

x_{R△i} = \begin{cases}x_{R} x_{i}^{−1} & for i ∈ R \\ x_{R} x_{i} & for i ∉ R \end{cases}

and

x_{A\(R△i)} = \begin{cases}x_{A\R} x_{i} & for i ∈ R \\ x_{A\R} x_{i}^{−1} & for i ∉ R. \end{cases}

Therefore one may rewrite (9) as follows:

(L̂v)_{R} = ±\frac{x_{R}}{x_{[n]}} ( ∑_{i∈A∩R} q_{i}x_{R}x_{i}^{−1} ((x_{A\R} x_{i})^{2} + (x_{A\R})^{2})

+ ∑_{i∈A\R} q_{i}x_{R}x_{i} ((x_{A\R} x_{i}^{−1})^{2} + (x_{A\R})^{2}))

= ±\frac{(x_{R}x_{A\R})^{2}}{x_{[n]}} ( ∑_{i∈A∩R} q_{i}x_{i}^{−1}(x_{i}^{2} + 1) + ∑_{i∈A\R} q_{i}x_{i}(x_{i}^{−2} + 1))
= ±\frac{(x_{R}x_{A\R})^{2}}{x_{[n]}} ∑_{i∈A} q_{i}(x_{i} + x_{i}^{−1})
= ±\frac{(x_{R}x_{A\R})^{2}}{x_{[n]}} f_{A},

which shows that (L̂v)_{R} is zero modulo (f_{A}) as desired. □

6. Proof of Theorem 4

We recall the statement of Theorem 4.

Theorem 4. Let G be a connected threshold graph with vertices [n], edges E, and degree sequence λ. Then

∑_{T ∈Tree(G)} ∏_{i=1}^{n} x_{i}^{indeg_{T} (i)}y_{i}^{outdeg_{T} (i)} = x_{1}y_{n} ∏_{r=2}^{n−1} (∑_{i=1}^{λ′_{r}} x_{min{i,r}}y_{max{i,r}}) .

As noted in the Introduction, this result is a special case of Theorem 2.4 of [6]. For this reason, and because the ideas of the proof are quite similar to those of Theorem 3, we omit most of the technical details. We write N(v) for the neighbors of a vertex v, and denote the set {i, i + 1, …, j} by [i, j].

Sketch of proof. The partitions λ which arise as degree sequences of threshold graphs have been completely characterized (see, e.g., [4, Theorem 8.5]). In particular, suppose that Durfee square of λ (the largest square which is a subshape of λ) has side length s. Then for all r ∈ [n],

either r ≤ s < λ′_{r} = 1 + λ_{r}
or r > s ≥ λ′_{r} = λ_{r+1}. (10)

Using these identities, one may rewrite the desired equality as

∑_{T ∈Tree(G)} ∏_{i=1}^{n} x_{i}^{indeg_{T} (i)}y_{i}^{outdeg_{T} (i)} = x_{1} · ∏_{r=2}^{s} f_{r} · ∏_{r=s+1}^{n−1} g_{r} · ∏_{r=s+1}^{n} y_{r}.  (11)

where

f_{r} := y_{r} ∑_{i=1}^{r} x_{i} + x_{r} ∑_{i=r+1}^{1+λ_{r}} y_{i}  and  g_{r} := ∑_{i=1}^{λ_{r+1}} x_{i}.

Both the left-hand and right-hand sides of (11) are polynomials in the x_{i}, y_{i} of total degree 2n − 2, and both have coefficient of x_{1}^{n−1}y_{2}y_{3} ⋯ y_{n} equal to 1 (because N(1) = [2, n]). Thus it suffices to prove that the left-hand side is divisible by each of the factors on the right-hand side. By Kirchhoff’s Theorem, this left-hand side is the determinant of the matrix L̂ obtained from the usual weighted Laplacian matrix by removing the first row and column and making the substitution

e_{ij} = \begin{cases}x_{min\{i,j\}}y_{max\{i,j\}} & for \{i, j\} ∈ E \\ 0 & for \{i, j\} ∉ E. \end{cases}

\underline{First}, one must show that the left-hand side of the theorem is divisible by the monomial factor x_{1} ∏_{r=s+1}^{n} y_{r}. Every spanning tree T of G contains an edge of the form {1, j}, which contributes a factor of x_{1}y_{j} to the monomial corresponding to T. In particular, x_{1} divides the left-hand side of (11). Furthermore, if r > s, then q < r whenever q ∈ N(r). In particular, y_{r} divides every entry in the r^{th} row of L̂.

\underline{Second}, one must show that f_{r} divides det L̂ for r ∈ [2, s]. Clearly f_{r} is irreducible, since neither sum in the definition of f_{r} is empty. Define a column vector^{2}

v = ∑_{i=1}^{r} x_{i}ϵ_{r} + ∑_{i=r+1}^{λ′_{r}} x_{r}ϵ_{i},

where ϵ_{i} denotes the i^{th} standard basis vector. Note that the entries of v are not all divisible by f_{r}, so that v is a non-zero vector modulo (f_{r}). By Lemma 5, it is now sufficient to show that for each j, the entry (L̂v)_{j} of L̂v is divisible by f_{r}. One must consider four cases depending on the value of j: (i) j < r, (ii) j = r, (iii) j > r and {j, r} ∈ E, (iv) j > r and {j, r} ∉ E. We omit the routine calculations, which are similar to the proof of Theorem 3.

2Found using Macaulay; see the earlier footnote.

\underline{Third}, one must show that g_{r} divides det L̂ for all r ∈ [s+1, n−1]. In fact, some higher power of g_{r} may divide det L̂, as we now explain. If λ has exactly b columns of height λ′_{r}, i.e.,

λ′_{a−1} > λ′_{a} = ⋯ = λ′_{r} = ⋯ = λ′_{a+b−1} > λ′_{a+b}

for some a > s, then N(i) = [λ_{r}] for all vertices i ∈ [a + 1, a + b], so

g_{a} = g_{a+1} = ⋯ = g_{r} = ⋯ = g_{a+b−1}.

Accordingly, one must show that g_{r}^{b} divides det L̂. Restricting the Laplacian matrix L to the columns [a + 1, a + b] yields a rank-1 matrix of the form

− [x_{1} x_{2} ⋯ x_{λ_{r}} 0 ⋯ 0]^{T} · [y_{a+1} y_{a+2} ⋯ y_{a+b}] .

Consequently, both L and L̂ have b − 1 linearly independent nullvectors modulo (g_{r}) supported in coordinates [a + 1, a + b]. It remains only to exhibit one further nullvector for L̂ which is supported in at least one coordinate outside that range. We claim that such a vector^{3} is

v = ∑_{i=1+λ_{r}}^{a} (y_{a+b}ϵ_{i} − y_{i}ϵ_{a+b}) .

One must verify that for each k, the k^{th} coordinate (L̂v)_{k} vanishes modulo (g_{r}). This calculation splits into four cases: (i) k ∈ [2, λ_{r}], (ii) k ∈ [1 + λ_{r}, a], (iii) k ∈ [a + 1, n − 1] \ {a + b}, (iv) k = a + b. Once again, we omit the routine verification. □

References

[1] D. Bayer and M. Stillman, Macaulay: A computer algebra system for algebraic geometry.

    Software, 1994. Available at www.math.columbia.edu/∼bayer/Macaulay/.

[2] C. Krattenthaler, Advanced determinant calculus. The Andrews Festschrift (Maratea, 1998). Sém. Lothar. Combin. 42 (1999), Art. B42q, 67 pp. (electronic).

[3] R. Merris, Degree maximal graphs are Laplacian integral. Linear Algebra Appl. 199 (1994), 381–389.

[4] R. Merris, Graph theory. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2001.

[5] J.W. Moon, Counting labelled trees. Canadian Mathematical Monographs 1 Canadian Mathematical Congress, Montreal, 1970.

[6] J. Remmel and S.G. Williamson, Spanning trees and function classes. Electron. J. Combin. 9 (2002), Research Paper 34, 24 pp. (electronic).

[7] R.P. Stanley, Enumerative Combinatorics, Volume II. Cambridge Studies in Advanced Mathematics 62. Cambridge University, 1999.

School of Mathematics, University of Minnesota, Minneapolis, MN 55455

   E-mail address: martin@math.umn.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455

   E-mail address: reiner@math.umn.edu

3Found using Macaulay; see the earlier footnote.