text:
# Yamada Conference LVI, the Fourth International Symposium on Crystalline Organic Metals, Superconductors and Ferromagnets ISCOM 2001 - Abstract Number S67 Thermal Conductivity in Vortex State of Nodal Superconductors

## 1 Introduction

Since the discovery of the first organic superconductor in (TMTSF)2PF6 (or Bechgaard salts) , the symmetry in superconducting order parameter has been one of the important issues . Indeed the symmetry of the superconducting order parameter becomes one of the central issues after the establishment of $`d`$-wave symmetry in both hole and electron doped high Tc superconductors . Most likely the superconductivity in (TMTSF)2X with X = ClO4, PF6, etc. is of $`p`$-wave . In particular, a flat Knight shift seen in a recent NMR experiment  is consistent with this picture. The remaining question is whether the p-wave superconductor belongs to 1D representation  or 2D representation . After a long controversy , $`d`$-wave superconductivity is emerging in $`\kappa `$-(ET)2 salts . Here now the question is whether the symmetry is of dxy-wave as suggested by the theoretical works  or d$`_{x^2y^2}`$-wave as the recent STM study suggests . We shall give a somewhat surprising answer on this based on the recent angular dependent thermal conductivity data of $`\kappa `$-(ET)2Cu(NCS)2 by Izawa et al . The quasiparticle spectrum of all these new superconductors is well described by the BCS theory for nodal (or unconventional) superconductors . In particular, there are nodal excitations (i.e. the quasiparticles which inhabit in the vicinity of the nodal lines) which persist to low temperatures (i.e.T$`<<\mathrm{\Delta }`$ where $`\mathrm{\Delta }`$ is the superconducting order parameter). In the vortex state the quasiparticle spectrum is modified due to the supercurrent circling around individual vortices. In order to describe the quasiparticle spectrum in the vortex state, Volovik  has introduced a very simple method to evaluate the effect of the supercurrent within the quasiclassical approximation. In particular, he has shown that the specific heat in the vortex state in nodal superconductors is proportional to $`\sqrt{H}`$ for $`H/H_{c2}<<1`$ where H is the magnetic field strength. This $`\sqrt{H}`$ dependence has been seen in YBCO , LSCO , $`\kappa `$-(ET)2 salts  and Sr2RuO4 . We shall show later that in the presence of impurity the above dependence may change as

$`{\displaystyle \frac{C_s}{\gamma _NT}}={\displaystyle \frac{N(0)}{N_0}}\{1+{\displaystyle \frac{\mathrm{\Delta }}{\pi \mathrm{\Gamma }}}<x^2>\}`$
$`={\displaystyle \frac{N(0)}{N_0}}\{1+{\displaystyle \frac{3\stackrel{~}{v}^2(eH)}{16\pi \mathrm{\Gamma }\mathrm{\Delta }}}[\mathrm{ln}(\sqrt{{\displaystyle \frac{3}{2(eH)}}}{\displaystyle \frac{\mathrm{\Delta }}{\stackrel{~}{v}}}){\displaystyle \frac{1}{27}}]\}`$ (1)
for Sr2RuO4 in H$`//`$ a-b. Similarly for $`d`$+$`s`$-wave in H$`//`$ a-b,

$`{\displaystyle \frac{C_s}{\gamma _NT}}={\displaystyle \frac{N(0)}{N_0}}\{1+{\displaystyle \frac{\stackrel{~}{v}^2(eH)}{8\pi \mathrm{\Gamma }\mathrm{\Delta }}}[(1{\displaystyle \frac{1}{2}}r\mathrm{cos}(2\theta ))\times `$
$`\mathrm{ln}({\displaystyle \frac{\mathrm{\Delta }}{\stackrel{~}{v}\sqrt{eH}}}){\displaystyle \frac{1}{16}}(1{\displaystyle \frac{1}{2}}(12r^2)\mathrm{cos}(4\theta ))]\}`$ (2)
Here $`N(0)`$ is the residual density of states in the presence of the impurity scattering and $`N_0`$ is the one for the normal state. Also $`\gamma _N`$ is the Sommerfeld coefficient, $`\stackrel{~}{v}=\sqrt{v_av_c}`$ and $`v_a`$ and $`v_c`$ are the Fermi velocities in the a-b plane and parallel to the c-axis, respectively. For $`d+s`$-wave we took $`\mathrm{\Delta }(𝐤)\mathrm{cos}(2\varphi )r`$. $`\theta `$ is the angle $`𝐇`$ makes from the $`a`$ axis. Here $`x=𝐯𝐪/\mathrm{\Delta }`$ and $`𝐯𝐪`$ is called the Doppler shift, where $`𝐯`$ is the Fermi velocity and 2$`𝐪`$ is the pair momentum and $`<\mathrm{}>`$ means space average over the vortex lattice and $`𝐯`$ average over the nodal lines. Some of these details are given in . In the above derivation, we have assumed that the system is in the clean limit ( $`ϵ`$, $`T`$ $`<<\sqrt{\mathrm{\Gamma }\mathrm{\Delta }}`$ ) while Volovik’s result applies for the superclean limit ($`\sqrt{\mathrm{\Gamma }\mathrm{\Delta }}`$ $``$ $`ϵ`$, $`T`$). Here $`ϵ=\frac{1}{2}\stackrel{~}{v}\sqrt{eH}`$ is the characteristic magnetic energy. Also when we put $`r`$ = 0 in Eq.(2), we obtain the usual expression for $`d`$-wave superconductors. The specific heat in the clean limit in LSCO in $`𝐇c`$ has been reported recently. The quasiclassical approximation is extended to calculate the thermal conductivity in the vortex state . Indeed we can now describe the angular dependent thermal conductivity observed in single crystals of YBCO  consistently if we assume that the system is in the superclean limit and T$`>>ϵ`$ . In the following we shall first review the theory limiting ourselves to the clean limit ($`ϵ<<\sqrt{\mathrm{\Delta }\mathrm{\Gamma }}`$). As to the result for the superclean limit readers may consult . Also we consider the phononic thermal conductivity both in Sr2RuO4 and in $`\kappa `$-(ET)2 salts. The c-axis thermal conductivity in Sr2RuO4  appears to be described in terms of the phononic thermal conductivity . As to $`\kappa `$-(ET)2Cu(NCS)2 it appears the phononic thermal conductivity dominates for T $`>`$ 0.5K . For T $`<`$ 0.47K there appears a clear sign of the electronic contribution. From the angle dependence of the thermal conductivity, we can deduce $`d`$+$`s`$-wave ($`\mathrm{\Delta }(𝐤)\mathrm{cos}(2\varphi )0.067`$) for $`\kappa `$-(ET)2Cu(NCS)2. In Fig.1 we show $`|\mathrm{\Delta }(𝐤)|`$ for superconductors a)$`s`$-wave, (b) $`d`$-wave as in HTSC, CeCoIn5, $`\kappa `$-(ET)2 salts, (c)2D $`f`$-wave as in Sr2RuO4 and (d)$`f`$-wave as in UPt3 .

## 2 Thermal conductivity in the vortex state.

In the following we limit ourselves to nodal superconductors; 2D $`f`$-wave with $`\mathrm{\Delta }(𝐤)\mathrm{cos}(ck_z)e^{\pm i\varphi }`$ as in Sr2RuO4 and $`d+s`$-wave with $`\mathrm{\Delta }(𝐤)\mathrm{cos}(2\varphi )r`$ as in $`\kappa `$-(ET)2Cu(NCS)2. Also we limit ourselves to the clean limit(i.e. $`\sqrt{\mathrm{\Delta }\mathrm{\Gamma }}ϵ=\stackrel{~}{v}\sqrt{eH}`$, where $`\stackrel{~}{v}=\sqrt{v_av_b}`$). Then the thermal conductivity for $`T\mathrm{\Delta }`$ and in a planar magnetic field is given by

$$\frac{\kappa _{xx}}{\kappa _0}=1+\frac{\stackrel{~}{v}^2(eH)}{4\pi \mathrm{\Gamma }\mathrm{\Delta }}\mathrm{ln}(4\sqrt{\frac{2\mathrm{\Delta }}{\pi \mathrm{\Gamma }}})(\mathrm{ln}(\frac{\mathrm{\Delta }}{\stackrel{~}{v}}\sqrt{\frac{2}{3eH}})\frac{1}{72})$$
(3)
for 2D $`f`$-wave.

$`{\displaystyle \frac{\kappa _{xx}}{\kappa _0}}`$ $`=`$ $`1+{\displaystyle \frac{\stackrel{~}{v}^2(eH)}{6\pi \mathrm{\Gamma }}}\mathrm{ln}(4\sqrt{{\displaystyle \frac{2\mathrm{\Delta }}{\pi \mathrm{\Gamma }}}})((1{\displaystyle \frac{1}{2}}r\mathrm{cos}(4\theta ))\times `$ (4)
$`\mathrm{ln}{\displaystyle \frac{2\mathrm{\Delta }}{\stackrel{~}{v}\sqrt{eH}}}{\displaystyle \frac{1}{16}}(1{\displaystyle \frac{1}{2}}(12r^2)\mathrm{cos}(2\theta )))`$
for $`d+s`$-wave.

Similarly the Hall thermal conductivity is given by

$$\frac{\kappa _{xy}}{\kappa _0}=\frac{\stackrel{~}{v}^2(eH)}{24\pi \mathrm{\Gamma }\mathrm{\Delta }}\mathrm{sin}(2\theta )\mathrm{ln}(2\sqrt{\frac{2\mathrm{\Delta }}{\pi \mathrm{\Gamma }}})\mathrm{ln}(\frac{\mathrm{\Delta }}{\stackrel{~}{v}}\sqrt{\frac{2}{3eH}})$$
(5)
for 2D $`f`$-wave, and

$`{\displaystyle \frac{\kappa _{xy}}{\kappa _0}}`$ $`=`$ $`{\displaystyle \frac{\stackrel{~}{v}^2(eH)}{16\pi \mathrm{\Gamma }\mathrm{\Delta }}}(1r^2)\mathrm{sin}(2\theta )\mathrm{ln}(4\sqrt{{\displaystyle \frac{2\mathrm{\Delta }}{\pi \mathrm{\Gamma }}}})\times `$ (6)
$`\mathrm{ln}({\displaystyle \frac{\mathrm{\Delta }}{\stackrel{~}{v}\sqrt{eH}}})`$
for $`d+s`$-wave. Here $`\kappa _0`$ is the thermal conductivity in the absence of the magnetic field.

## 3 Phononic thermal conductivity

So far we have considered only the electronic thermal conductivity. In general, the thermal conductivity is written as $`\kappa =\kappa ^{el}+\kappa ^g`$ , where the second term is due to phonons. The importance of $`\kappa ^g`$ in high Tc cuprate superconductors, YBCO and Bi2212 have been well-documented . In low temperatures (for T $`<`$ 5K ) $`\kappa ^gT^3`$ in single crystals of YBCO and Bi2212 . In high quality crystals phonons are mostly scattered by crystalline defects and crystal boundaries. In the vortex state in nodal superconductors the quasiparticles provide another scattering center. When the thermal phonons are ballistic, the phonon scattering due to the quasiparticles is proportional to \[N(0,$`\theta `$)\]2 at low temperatures . Here $`N(0,\theta )`$ is the residual density of states in the presence of a magnetic field and $`\theta `$ refers to the field orientation. Therefore the $`c`$ axis phononic thermal conductivity $`\kappa ^g`$ in Sr2RuO4 is a planar magnetic field is written

$$\frac{\kappa ^g}{\kappa _0^g}=[1+\frac{T}{T_0}(1+\frac{3\stackrel{~}{v}^2(eH)}{8\pi \mathrm{\Gamma }\mathrm{\Delta }}\mathrm{ln}(\frac{T}{c\sqrt{eH}})]^1$$
(7)
for 2D $`f`$-wave, and

$$\frac{\kappa ^g}{\kappa _0^g}=[1+\frac{T}{T_0}(1+\frac{\stackrel{~}{v}^2(eH)}{4\pi \mathrm{\Gamma }\mathrm{\Delta }}(1\frac{r}{2}\mathrm{cos}(2\theta ))\mathrm{ln}(\frac{T}{c\sqrt{eH}})]^1$$
(8)
for $`d+s`$-wave, respectively. Here T0 is a constant of the dimension of the energy, and $`c`$ is the phonon velocity. It is noteworthy that Eq.(8) does not contain the fourfold term.

When the phononic thermal conductivity dominates as in Sr2RuO4 , it is more convenient to analyze the thermal resistance $`W=(\kappa ^g)^1`$

$$\frac{W(H)}{W(0)}1=\frac{T}{T+T_0}\frac{3\stackrel{~}{v}^2(eH)}{8\pi \mathrm{\Gamma }\mathrm{\Delta }}\mathrm{ln}(\frac{T}{c\sqrt{eH}})$$
(9)
for 2D $`f`$-wave. We believe $`aH\mathrm{ln}(1/bH)`$ dependence is more consistent with the experiment for $`H[100]`$, which indicates the crystal of Sr2RuO4 is in the clean limit. This is readily seen from Fig.2. Also in the clean limit the specific heat behaves similarly . On the other hand for $`𝐇[001]`$, it appears that the superclean limit appears, ie. linear in $`H`$ as shown in Fig. 3.

More recently the $`b`$-axis thermal conductivity of $`\kappa `$-(ET)2Cu(NCS)2 in a planar magnetic field is reported . First of all for $`T>1`$ K the thermal conductivity decreases with increasing $`H`$ indicating the phonon dominance. more surprising is an appreciable twofold term($`\mathrm{cos}(2\theta )`$) in the thermal conductivity. This suggests naturally $`d+s`$-wave model. Indeed we obtain $`\mathrm{\Delta }(𝐤)\mathrm{cos}(2\varphi )0.067`$ as already mentioned earlier. As the temperature is lowered through $`T=0.47`$ K, there appears a positive fourfold term. Clearly this is the signature of the electronic thermal conductivity. Further the magnitude of the fourfold term is consistent with Eq.(4). Therefore we conclude the order parameter in $`\kappa `$-(ET)2Cu(NCS)2 is of $`d+s`$-wave with $`\mathrm{\Delta }(𝐤)\mathrm{cos}(2\varphi )0.067`$. In other words the nodal lines run 43.08 from the b-axis rather than 45. Since $`\kappa `$-(ET)2 salts do not have the tetragonal symmetry, the admixture of $`s`$-wave component is allowed. This is somewhat similar to YBCO, where the tetragonal symmetry is broken due to the orthorhombic distortion. This $`d_{x^2y^2}`$-wave is totally unexpected theoretically .There is a well-known parallel between high $`T_c`$ cuprates and $`\kappa `$-(ET)2 salts. However, the present result tells there is a subtle and delicate difference between these two systems and a more careful study of the pairing interaction is necessary. This makes the physics in organic superconductors all the more interesting.

## 4 Concluding Remarks

The gap symmetry is the central issue of new superconductors. We have shown the angular dependent thermal conductivity in the vortex state provides a new window to look this question. In this way we have succeeded in identifying the gap symmetry of Sr2RuO4, CeCoIn5  and $`\kappa `$-(ET)2Cu(NCS)2. We expect this method will be very useful to identify the gap symmetry of $`\beta `$-(ET)2 salts, $`\lambda `$-(ET)2 salts and other organic superconductors and to clarify existing controversy. Also the success of this method testifies the soundness of both the BCS theory of nodal superconductors and the Volovik’s semiclassical approach to handle the vortex state in nodal superconductors.


format: text

text:
# Factorizations of some weighted spanning tree enumerators

## 1. Introduction

Cayley’s celebrated formula $`n^{n2}`$ for the number of spanning trees in the complete graph $`K_n`$ has many generalizations (see ). 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.

$$\underset{TTree(K_n)}{}x^{\mathrm{deg}(T)}=x_1x_2\mathrm{}x_n(x_1+\mathrm{}+x_n)^{n2}$$

where $`Tree(K_n)`$ is the set of all spanning trees and $`x^{\mathrm{deg}(T)}:=_{i=1}^nx_i^{\mathrm{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}\times \mathrm{}\times 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,\mathrm{},j_r)[n_1]\times \mathrm{}\times [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)}:=\underset{i=1}{\overset{r}{}}q_i^{|\{\text{edges in }T\text{ in direction }i\}|}.$$

###### Theorem 1.

$`{\displaystyle \underset{TTree(K_{n_1}\times \mathrm{}\times K_{n_r})}{}}q^{dir(T)}`$ $`={\displaystyle \frac{1}{n_1\mathrm{}n_r}}{\displaystyle \underset{\mathrm{}A[r]}{}}\left({\displaystyle \underset{iA}{}}q_in_i\right)^{_{iA}(n_i1)}`$
$`={\displaystyle \underset{i=1}{\overset{r}{}}}q_i^{n_i1}n_i^{n_i2}{\displaystyle \underset{\begin{array}{c}A[r]\\ |A|2\end{array}}{}}\left({\displaystyle \underset{iA}{}}q_in_i\right)^{_{iA}(n_i1)}.`$
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,\mathrm{},r\}`$ is a direction and $`j`$ is in the range $`1,2,\mathrm{},n_i`$. In other words, there are $`r`$ sets of variables, with $`n_i`$ variables $`x_1^{(i)},x_2^{(i)},\mathrm{},x_{n_i}^{(i)}`$ in the $`i^{th}`$ set. Given a spanning tree $`T`$ of $`G`$, define the decoupled degree monomial

$$x^{dd(T)}:=\underset{v=(j_1,\mathrm{},j_r)[n_1]\times \mathrm{}\times [n_r]}{}\left(x_{j_1}^{(1)}\mathrm{}x_{j_r}^{(r)}\right)^{\mathrm{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,\mathrm{},n_r}(q,x):=\underset{TTree(K_{n_1}\times \mathrm{}\times K_{n_r})}{}q^{dir(T)}x^{dd(T)}$$

is divisible by

$$q_i^{n_i1},$$

by

$$\left(x_j^{(i)}\right)^{n_1\mathrm{}n_{i1}n_{i+1}\mathrm{}n_r}$$

and by

$$\left(x_1^{(i)}+\mathrm{}+x_{n_i}^{(i)}\right)^{n_i2}$$

for each $`i[r]`$ and $`j[n_i]`$.

Conjecture. The quotient polynomial

$$\frac{f_{n_1,\mathrm{},n_r}(q,x)}{{\displaystyle \underset{i=1}{\overset{r}{}}}q_i^{n_i1}\left(x_1^{(i)}\mathrm{}x_{n_i}^{(i)}\right)^{n_1\mathrm{}n_{i1}n_{i+1}\mathrm{}n_r}\left(x_1^{(i)}+\mathrm{}+x_{n_i}^{(i)}\right)^{n_i2}}$$

in $`𝐙[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_i3`$.

Section 5 shows that when all $`n_i=2`$, the spanning tree enumerator $`f_{n_1,\mathrm{},n_r}(q,x)`$ factors beautifully. Here we consider the Cartesian product

$$Q_n:=\underset{n\text{ times}}{\underset{}{K_2\times \mathrm{}\times K_2}},$$

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`$:

$`x_1^{(i)}`$ $`=x_i^{\frac{1}{2}},`$ (2)
$`x_2^{(i)}`$ $`=x_i^{\frac{1}{2}}.`$
The substitution (2) is harmless, because it is immediate from (1) that the polynomial $`f_{2,\mathrm{},2}(q,x)`$ is homogeneous of total degree $`2(2^n1)`$ in each of the sets of two variables $`\{x_1^{(i)},x_2^{(i)}\}`$. Our result may now be stated as follows:

###### Theorem 3.

$$\left[\underset{TTree(Q_n)}{}q^{dir(T)}x^{dd(T)}\right]_{x_1^{(i)}=x_i^{\frac{1}{2}},x_2^{(i)}=x_i^{\frac{1}{2}}}=q_1\mathrm{}q_n\underset{\begin{array}{c}A[n]\\ |A|2\end{array}}{}\underset{iA}{}q_i\left(x_i^1+x_i\right).$$

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,\mathrm{},n\}`$ in weakly decreasing order of their degrees, the degree sequence $`\lambda =(\lambda _1\mathrm{}\lambda _n)`$ determines the graph completely by the rule that the neighbors of vertex $`i`$ are the $`\lambda _i`$ smallest members of $`[n]`$ other than $`i`$ itself. A result of Merris  implies the following generalization of Cayley’s formula to all threshold graphs. It uses the notion of the conjugate partition $`\lambda ^{}`$ to the degree sequence $`\lambda `$, whose Ferrers diagram is obtained from that of $`\lambda `$ by flipping across the diagonal.

Merris’ Theorem. Let $`G`$ be a threshold graph with vertices $`[n]`$ and degree sequence $`\lambda `$. Then the number of spanning trees in $`G`$ is $`_{r=2}^{n1}\lambda _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 $`\lambda `$. Then

$$\underset{TTree(G)}{}\underset{i=1}{\overset{n}{}}x_i^{indeg_T(i)}y_i^{outdeg_T(i)}=x_1y_n\underset{r=2}{\overset{n1}{}}\left(\underset{i=1}{\overset{\lambda _r^{}}{}}x_{\mathrm{min}\{i,r\}}y_{\mathrm{max}\{i,r\}}\right).$$

In particular, setting $`y_i=x_i`$ gives

$$\underset{TTree(G)}{}x^{\mathrm{deg}(T)}=x_1x_2\mathrm{}x_n\underset{r=2}{\overset{n1}{}}\left(\underset{i=1}{\overset{\lambda _r^{}}{}}x_i\right).$$

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 .

## 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\times n`$ weighted Laplacian matrix defined by

$$L_{ij}:=\{\begin{array}{cc}_{k=1}^ne_{ik}\hfill & \text{ for }i=j\hfill \\ e_{ij}\hfill & \text{ for }ij.\hfill \end{array}$$
(3)
Kirchhoff’s Matrix-Tree Theorem \[5, §5.3\] For any $`r,s[n]`$,

$$\underset{TTree(K_n)}{}\underset{\{i,j\}T}{}e_{ij}=(1)^{r+s}det\widehat{L}$$

where $`\widehat{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.

$$\underset{TTree(K_n)}{}x^{\mathrm{deg}(T)}=x_1x_2\mathrm{}x_n(x_1+\mathrm{}+x_n)^{n2}$$

where $`x^{\mathrm{deg}(T)}:=_{i=1}^nx_i^{\mathrm{deg}_T(i)}`$.

###### Proof.

Apply the substitution $`e_{ij}=x_ix_j`$ to the weighted Laplacian matrix $`L`$ in Kirchhoff’s Theorem. Setting $`f:=x_1+\mathrm{}+x_n`$, one has from (3)

$$L_{ij}=\{\begin{array}{cc}(fx_i)x_j\hfill & \text{ for }i=j\hfill \\ x_ix_j\hfill & \text{ for }ij.\hfill \end{array}$$

By Kirchhoff’s Theorem, the left-hand side of the Cayley-Prüfer Theorem coincides with the determinant $`det\widehat{L}`$, where $`\widehat{L}`$ is the reduced Laplacian $`\widehat{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 $`2n2`$, and both have coefficient $`1`$ in the monomial $`x_1^{n1}x_2x_3\mathrm{}x_n`$. Therefore it suffices to show that the determinant is divisible by each of the variables $`x_j`$, and also by $`f^{n2}`$. Divisibility by $`x_j`$ is clear since $`x_j`$ divides every entry in the $`j^{th}`$ column of $`L`$ (and hence also $`\widehat{L}`$). Divisibility by $`f`$ follows from Lemma 5 below, once one notices that in the quotient ring $`𝐐[x_1,\mathrm{},x_n]/(f)`$, this weighted Laplacian $`L`$ (and hence $`\widehat{L}`$) reduces to a rank one matrix of the form $`L=v^Tv`$, where $`v`$ is the row vector $`\left[\begin{array}{ccc}x_1& \mathrm{}& x_n\end{array}\right]`$. ∎

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 $`fR`$ 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 $`AR^{n\times n}`$ be a square matrix. If the reduction $`\overline{A}(R/(f))^{n\times n}`$ has $`K`$-nullspace of dimension at least $`d`$, then $`f^d`$ divides $`detA`$ in $`R`$.

###### Proof.

Let $`\{\overline{v}_i\}_{i=1}^d`$ be $`d`$ linearly independent vectors in $`K^n`$ lying in the nullspace of $`\overline{A}`$. Extend them to a basis $`\{\overline{v}_i\}_{i=1}^n`$ of $`K^n`$. By clearing denominators, one may assume that $`\{\overline{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_iF`$ which are not all zero satisfying

$$\underset{i=1}{\overset{n}{}}c_iv_i=0.$$
(4)
Clearing denominators, one may assume that $`c_iR`$ 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 $`\{\overline{v}_i\}_{i=1}^n`$, a contradiction.

Let $`PF^{n\times n}`$ be the matrix whose columns are the vectors $`v_i`$. Note that $`detP`$ is not divisible by $`f`$, or else the reductions $`\{\overline{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)`$:

$$\begin{array}{ccccccccc}R& & & & R_{(f)}& & & & F\\ & & & & & & & \\ R/(f)& & & & K& \end{array}$$

Since $`P^1`$ has entries in $`R_{(f)}`$, so does $`P^1AP`$. For each $`i[d]`$, the reduction of $`Av_i`$ vanishes in $`K`$, so every entry in the first $`d`$ columns of $`P^1AP`$ lies in the ideal $`(f)`$. Hence $`detP^1AP=detA`$ 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 $`AS^{n\times n}`$ be a square matrix such that the reduction $`\overline{A}`$ has $`K`$-nullspace of dimension at least $`d`$. Then $`detA𝔪^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.

$$\underset{TTree(K_{n_1}\times \mathrm{}\times K_{n_r})}{}q^{dir(T)}=\frac{1}{n_1\mathrm{}n_r}\underset{\mathrm{}A[r]}{}\left(\underset{iA}{}q_in_i\right)^{_{iA}(n_i1)}.$$

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 $`ij`$ in the usual weighted Laplacian $`L(G)`$ defined in (3).

The Cartesian product $`G_1\times \mathrm{}\times 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\times \mathrm{}\times G_r)=V(G_1)\times \mathrm{}\times V(G_r)$$

and edge set

$`E(G_1\times \mathrm{}\times G_r)`$
$`={\displaystyle \underset{i=1}{\overset{r}{}}}V(G_1)\times \mathrm{}\times V(G_{i1})\times E(G_i)\times V(G_{i+1})\times \mathrm{}\times V(G_r).`$
where $``$ denotes a disjoint union. The following proposition follows easily from this description; we omit the proof.

###### Proposition 7.

If $`G_1,\mathrm{},G_r`$ are graphs with (unweighted) Laplacian matrices $`L(G_i)`$, then

$$L(G_1\times \mathrm{}\times G_r)=\underset{i=1}{\overset{r}{}}id\mathrm{}idL(G_i)id\mathrm{}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\times \mathrm{}\times G_r)`$ can be chosen of the form $`v_1\mathrm{}v_r`$, where $`v_i`$ is an eigenvector for $`L(G_i)`$. Furthermore, this eigenvector will have eigenvalue $`\lambda _1+\mathrm{}+\lambda _r`$ if $`v_i`$ has eigenvalue $`\lambda _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 $`\lambda _1,\mathrm{},\lambda _n`$, indexed so that $`\lambda _n=0`$, then the number of spanning trees in $`G`$ is

$$\frac{1}{n}\lambda _1\mathrm{}\lambda _{n1}.$$

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)}\times \mathrm{}\times K_{n_r}^{(q_r)},$$

as each spanning tree $`T`$ in $`K_{n_1}\times \mathrm{}\times K_{n_r}`$ gives rise in an obvious way to exactly $`q^{dir(T)}`$ spanning trees in $`K_{n_1}^{(q_1)}\times \mathrm{}\times K_{n_r}^{(q_r)}`$. It is well-known that the (unweighted) Laplacian $`L(K_n)`$ has eigenvalues $`n,0`$ with multiplicities $`n1,1`$, respectively \[7, Example 5.6.9\]. Hence $`L(K_n^{(q)})=qL(K_n)`$ has eigenvalues $`qn,0`$ with multiplicities $`n1,1`$, respectively. By Proposition 7, $`L(K_{n_1}^{(q_1)}\times \mathrm{}\times K_{n_r}^{(q_r)})`$ has an eigenvalue $`_{iA}q_in_i`$ for each subset $`A[r]`$, and this eigenvalue occurs with multiplicity $`_{iA}(n_i1)`$. As the zero eigenvalue arises (with multiplicity $`1`$) only by taking $`A=\mathrm{}`$, Theorem 8 implies that the number of spanning trees in $`K_{n_1}^{(q_1)}\times \mathrm{}\times K_{n_r}^{(q_r)}`$ is

$$\frac{1}{n_1\mathrm{}n_r}\underset{\mathrm{}A[r]}{}\left(\underset{iA}{}q_in_i\right)^{_{iA}(n_i1)}.$$

## 4. Proof of Theorem 2

We recall here the statement of Theorem 2.

Theorem 2. The spanning tree enumerator

$$f_{n_1,\mathrm{},n_r}(q,x):=\underset{TTree(K_{n_1}\times \mathrm{}\times K_{n_r})}{}q^{dir(T)}x^{dd(T)}$$

is divisible by

$$q_i^{n_i1},$$

by

$$\left(x_j^{(i)}\right)^{n_1\mathrm{}n_{i1}n_{i+1}\mathrm{}n_r}$$

and by

$$\left(x_1^{(i)}+\mathrm{}+x_{n_i}^{(i)}\right)^{n_i2}$$

for each $`i[r]`$ and $`j[n_i]`$.

###### Proof.

To see divisibility by $`q_i^{n_i1}`$, note that every spanning tree in $`K_{n_1}\times \mathrm{}\times 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_i1`$ edges in direction $`i`$ in the original tree.

To see divisibility by $`(x_j^{(i)})^{n_1\mathrm{}n_{i1}n_{i+1}\mathrm{}n_r}`$, note that every spanning tree has an edge incident to each vertex, and therefore to each of the $`n_1\mathrm{}n_{i1}n_{i+1}\mathrm{}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)}+\mathrm{}+x_{n_i}^{(i)})^{n_i2}`$. Starting with the weighted Laplacian matrix (3) for $`K_{n_1}\times \mathrm{}\times K_{n_r}`$ (regarded as a subgraph of $`K_{n_1\mathrm{}n_r}`$), let $`L`$ be the matrix obtained by the following substitution: if $`\{k,l\}`$ represents an edge of $`K_{n_1}\times \mathrm{}\times K_{n_r}`$ in direction $`i`$ between the two vertices $`k=(k_1,\mathrm{},k_r)`$ and $`l=(l_1,\mathrm{},l_r)`$, then we set

$$e_{kl}=q_ix_{k_1}^{(1)}\mathrm{}x_{k_r}^{(r)}x_{l_1}^{(1)}\mathrm{}x_{l_r}^{(r)};$$
(5)
otherwise we set $`e_{kl}=0`$. Then Kirchhoff’s Theorem says that $`f_{n_1,\mathrm{},n_r}(q,x)=\pm det\widehat{L}`$ for any reduced matrix $`\widehat{L}`$ obtained from $`L`$ by removing a row and column. Thus by Lemma 5, it suffices for us to show that $`\widehat{L}`$ has nullspace of dimension at least $`n_i2`$ modulo $`f^{(i)}:=x_1^{(i)}+\mathrm{}+x_{n_i}^{(i)}`$. In fact, we will show that $`L`$ itself has nullspace of dimension at least $`n_i1`$ 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=\underset{i=1}{\overset{r}{}}X^{(1)}\mathrm{}X^{(i1)}q_iL^{(i)}X^{(i+1)}\mathrm{}X^{(r)},$$

where $`X^{(i)}`$ is the diagonal matrix with entries $`(x_1^{(i)})^2,\mathrm{},(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_i1`$. If $`v`$ is any nullvector for $`L^{(i)}`$ modulo $`(f^{(i)})`$, then the following vector is a nullvector for $`L`$ modulo $`(f^{(i)})`$:

$$\mathrm{𝟏}_{n_1}\mathrm{}\mathrm{𝟏}_{n_{i1}}v\mathrm{𝟏}_{n_{i+1}}\mathrm{}\mathrm{𝟏}_{n_r}$$

where $`\mathrm{𝟏}_m`$ represents a vector of length $`m`$ with all entries equal to $`1`$. Since varying $`v`$ leads to $`n_i1`$ 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:=_{iS}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)}`$ $`={\displaystyle \underset{S[n]}{}}\left({\displaystyle \frac{x_S}{x_{[n]S}}}\right)^{\frac{1}{2}\mathrm{deg}_T(S)}`$ (6)
$`={\displaystyle \underset{\text{ edges }\{S,R\}\text{ in }T}{}}{\displaystyle \frac{x_Sx_R}{x_{[n]}}}`$
Theorem 3.

$$\underset{TTree(Q_n)}{}q^{dir(T)}x^{wt(T)}=q_1\mathrm{}q_n\underset{\begin{array}{c}A[n]\\ |A|2\end{array}}{}\underset{iA}{}q_i\left(x_i^1+x_i\right).$$

###### 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\mathrm{}R`$, and abbreviate $`S\mathrm{}\{i\}`$ by $`S\mathrm{}i`$. Thus two vertices $`S,R`$ form an edge in $`Q_n`$ exactly when $`S\mathrm{}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\mathrm{}ii[n]\}.$$

Our goal is to show that the two sides of the theorem coincide as elements of $`𝐙[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_ix_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^nn1`$.

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 $`SV^{}`$, define $`\varphi (S)`$ to be the parent vertex of the vertex $`S`$ when the tree $`T`$ is rooted at the vertex $`[n]`$ (that is, $`\varphi (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,\varphi (S)\}SV^{}\}.$$

One has $`|\varphi (S)|=|S|\pm 1`$ (because $`\varphi (S)=S\mathrm{}i`$ for some $`i`$). Therefore the total degree of the monomial $`x^{wt(T)}`$ will be maximized when $`|\varphi (S)|=|S|+1`$ for all $`SV^{}`$; for instance, when $`\varphi (S)=S\{\mathrm{max}([n]S)\}`$. In this case, that total degree is

$$\underset{\{S,\varphi (S)\}T}{}\left(|S|+|\varphi (S)|n\right)=\underset{SV^{}}{}\left(2|S|+1n\right)=2^nn1.$$

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:=\underset{iA}{}q_i\left(x_i^1+x_i\right).$$

Henceforth, fix $`A[n]`$ of cardinality $`2`$. It is not hard to check that $`f_A`$ is irreducible in $`𝐙[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{array}{cc}\frac{q_ix_Sx_{S\mathrm{}i}}{x_{[n]}}\hfill & \text{for }S\mathrm{}R=\{i\},\hfill \\ 0\hfill & \text{for }|S\mathrm{}R|>1.\hfill \end{array}$$

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

$$v:=\underset{\mathrm{}S[n]}{}\left(x_A^2(1)^{|AS|}(x_{AS})^2\right)ϵ_S$$
(7)
is a nullvector<sup>1</sup><sup>1</sup>1The form of the nullvector (7) was suggested by experimentation using the computational commutative algebra package Macaulay  to compute the nullspace of $`\widehat{L}`$ in the quotient ring modulo $`(f_A)`$., 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 $`(\widehat{L}v)_R`$ of $`\widehat{L}v`$ is a multiple of $`f_A`$. Since $`\widehat{L}_{R,S}=0`$ unless $`S=R`$ or $`S=R\mathrm{}i`$ for some $`i`$, one has

$`(\widehat{L}v)_R`$ $`=\widehat{L}_{R,R}v_R+{\displaystyle \underset{i=1}{\overset{n}{}}}\widehat{L}_{R,R\mathrm{}i}v_{R\mathrm{}i}`$
$`={\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \frac{q_ix_Rx_{R\mathrm{}i}}{x_{[n]}}}\left(x_A^2(1)^{|AR|}(x_{AR})^2\right)`$
$`{\displaystyle \underset{i=1}{\overset{n}{}}}{\displaystyle \frac{q_ix_Rx_{R\mathrm{}i}}{x_{[n]}}}\left(x_A^2(1)^{|A(R\mathrm{}i)|}(x_{A(R\mathrm{}i)})^2\right)`$
$`={\displaystyle \frac{x_R}{x_{[n]}}}{\displaystyle \underset{i=1}{\overset{n}{}}}q_ix_{R\mathrm{}i}\left((1)^{|A(R\mathrm{}i)|}(x_{A(R\mathrm{}i)})^2(1)^{|AR|}(x_{AR})^2\right).`$ (8)
If $`iA`$, then $`AR=A(R\mathrm{}i)`$ and $`AR=A(R\mathrm{}i)`$, so the summand in (8) is zero. If $`iA`$, then $`|AR|=|A(R\mathrm{}i)|\pm 1`$, so one may rewrite (8) as follows:

$$(\widehat{L}v)_R=(1)^{|AR|}\frac{x_R}{x_{[n]}}\underset{iA}{}q_ix_{R\mathrm{}i}\left((x_{A(R\mathrm{}i)})^2+(x_{AR})^2\right).$$
(9)
Note also that when $`iA`$,

$$x_{R\mathrm{}i}=\{\begin{array}{cc}x_Rx_i^1\hfill & \text{for }iR\hfill \\ x_Rx_i\hfill & \text{for }iR\hfill \end{array}$$

and

$$x_{A(R\mathrm{}i)}=\{\begin{array}{cc}x_{AR}x_i\hfill & \text{for }iR\hfill \\ x_{AR}x_i^1\hfill & \text{for }iR.\hfill \end{array}$$

Therefore one may rewrite (9) as follows:

$`(\widehat{L}v)_R`$ $`=`$ $`\pm {\displaystyle \frac{x_R}{x_{[n]}}}({\displaystyle \underset{iAR}{}}q_ix_Rx_i^1((x_{AR}x_i)^2+(x_{AR})^2)`$
$`+{\displaystyle \underset{iAR}{}}q_ix_Rx_i((x_{AR}x_i^1)^2+(x_{AR})^2))`$
$`=`$ $`\pm {\displaystyle \frac{(x_Rx_{AR})^2}{x_{[n]}}}\left({\displaystyle \underset{iAR}{}}q_ix_i^1(x_i^2+1)+{\displaystyle \underset{iAR}{}}q_ix_i(x_i^2+1)\right)`$
$`=`$ $`\pm {\displaystyle \frac{(x_Rx_{AR})^2}{x_{[n]}}}{\displaystyle \underset{iA}{}}q_i(x_i+x_i^1)`$
$`=`$ $`\pm {\displaystyle \frac{(x_Rx_{AR})^2}{x_{[n]}}}f_A,`$
which shows that $`(\widehat{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 $`\lambda `$. Then

$$\underset{TTree(G)}{}\underset{i=1}{\overset{n}{}}x_i^{indeg_T(i)}y_i^{outdeg_T(i)}=x_1y_n\underset{r=2}{\overset{n1}{}}\left(\underset{i=1}{\overset{\lambda _r^{}}{}}x_{\mathrm{min}\{i,r\}}y_{\mathrm{max}\{i,r\}}\right).$$

As noted in the Introduction, this result is a special case of Theorem 2.4 of . 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,\mathrm{},j\}`$ by $`[i,j]`$.

Sketch of proof. The partitions $`\lambda `$ 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 $`\lambda `$ (the largest square which is a subshape of $`\lambda `$) has side length $`s`$. Then for all $`r[n]`$,

$$\begin{array}{cc}\hfill \text{either}& rs<\lambda _r^{}=\mathrm{\hspace{0.33em}1}+\lambda _r\hfill \\ \hfill \text{or}& r>s\lambda _r^{}=\lambda _{r+1}.\hfill \end{array}$$
(10)
Using these identities, one may rewrite the desired equality as

$$\underset{TTree(G)}{}\underset{i=1}{\overset{n}{}}x_i^{indeg_T(i)}y_i^{outdeg_T(i)}=x_1\underset{r=2}{\overset{s}{}}f_r\underset{r=s+1}{\overset{n1}{}}g_r\underset{r=s+1}{\overset{n}{}}y_r.$$
(11)
where

$$f_r:=y_r\underset{i=1}{\overset{r}{}}x_i+x_r\underset{i=r+1}{\overset{1+\lambda _r}{}}y_i\text{and}g_r:=\underset{i=1}{\overset{\lambda _{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 $`2n2`$, and both have coefficient of $`x_1^{n1}y_2y_3\mathrm{}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 $`\widehat{L}`$ obtained from the usual weighted Laplacian matrix by removing the first row and column and making the substitution

$$e_{ij}=\{\begin{array}{cc}x_{\mathrm{min}\{i,j\}}y_{\mathrm{max}\{i,j\}}\hfill & \text{ for }\{i,j\}E\hfill \\ 0\hfill & \text{ for }\{i,j\}E.\hfill \end{array}$$

First, one must show that the left-hand side of the theorem is divisible by the monomial factor $`x_1_{r=s+1}^ny_r`$. Every spanning tree $`T`$ of $`G`$ contains an edge of the form $`\{1,j\}`$, which contributes a factor of $`x_1y_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 $`qN(r)`$. In particular, $`y_r`$ divides every entry in the $`r^{th}`$ row of $`\widehat{L}`$.

Second, one must show that $`f_r`$ divides $`det\widehat{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<sup>2</sup><sup>2</sup>2Found using Macaulay; see the earlier footnote.

$$v=\underset{i=1}{\overset{r}{}}x_iϵ_r+\underset{i=r+1}{\overset{\lambda _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 $`(\widehat{L}v)_j`$ of $`\widehat{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.

Third, one must show that $`g_r`$ divides $`det\widehat{L}`$ for all $`r[s+1,n1]`$. In fact, some higher power of $`g_r`$ may divide $`det\widehat{L}`$, as we now explain. If $`\lambda `$ has exactly $`b`$ columns of height $`\lambda _r^{}`$, i.e.,

$$\lambda _{a1}^{}>\lambda _a^{}=\mathrm{}=\lambda _r^{}=\mathrm{}=\lambda _{a+b1}^{}>\lambda _{a+b}^{}$$

for some $`a>s`$, then $`N(i)=[\lambda _r]`$ for all vertices $`i[a+1,a+b]`$, so

$$g_a=g_{a+1}=\mathrm{}=g_r=\mathrm{}=g_{a+b1}.$$

Accordingly, one must show that $`g_r^b`$ divides $`det\widehat{L}`$. Restricting the Laplacian matrix $`L`$ to the columns $`[a+1,a+b]`$ yields a rank-$`1`$ matrix of the form

$$\left[\begin{array}{ccccccc}x_1& x_2& \mathrm{}& x_{\lambda _r}& 0& \mathrm{}& 0\end{array}\right]^T\left[\begin{array}{cccc}y_{a+1}& y_{a+2}& \mathrm{}& y_{a+b}\end{array}\right].$$

Consequently, both $`L`$ and $`\widehat{L}`$ have $`b1`$ linearly independent nullvectors modulo $`(g_r)`$ supported in coordinates $`[a+1,a+b]`$. It remains only to exhibit one further nullvector for $`\widehat{L}`$ which is supported in at least one coordinate outside that range. We claim that such a vector<sup>3</sup><sup>3</sup>3Found using Macaulay; see the earlier footnote. is

$$v=\underset{i=1+\lambda _r}{\overset{a}{}}\left(y_{a+b}ϵ_iy_iϵ_{a+b}\right).$$

One must verify that for each $`k`$, the $`k^{th}`$ coordinate $`(\widehat{L}v)_k`$ vanishes modulo $`(g_r)`$. This calculation splits into four cases: (i) $`k[2,\lambda _r]`$, (ii) $`k[1+\lambda _r,a]`$, (iii) $`k[a+1,n1]\{a+b\}`$, (iv) $`k=a+b`$. Once again, we omit the routine verification. ∎