The Spectral Geometry of the Mesh Matrices of Graphs

Sylvain E. Cappell and Edward Y. Miller

Dedicated to the memory of Jacob Eli Goodman

Abstract

The mesh matrix $Mesh(G,T_{0})$ of a connected finite graph
$G=(V(G),E(G))=(vertices,edges)\ of\ G$ of with respect to a choice of a
spanning tree $T_{0}\subset G$ is defined and studied. It was introduced by
Trent [30],[31]. Its characteristic polynomial $det(X\cdot Id-Mesh(G,T_{0}))$
is shown to equal $\Sigma_{j=0}^{N}\ (-1)^{j}\ ST_{j}(G,T_{0})\ (X-1)^{N-j}\
(\star)$ where $ST_{j}(G,T_{0})$ is the number of spanning trees of $G$
meeting $E(G-T_{0})$ in j edges and $N=|E(G-T_{0})|$ . As a consequence, there
are Tutte-type deletion-contraction formulae for computing this polynomial.
Additionally, $Mesh(G,T_{0})-Id$ is of the special form $Y^{t}\cdot Y$ ; so
the eigenvalues of the mesh matrix $Mesh(G,T_{0})$ are all real and are
furthermore be shown to be $\geq+1$. It is shown that $Y\cdot Y^{t}$, called
the mesh Laplacian, is a generalization of the standard graph Kirchhoff
Laplacian $\Delta(H)=Deg-Adj$ of a graph $H$. For example, $(\star)$
generalizes the all minors matrix tree theorem for graphs $H$ and gives a
deletion-contraction formula for the characteristic polynomial of $\Delta(H)$.
This generalization is explored in some detail. The smallest positive
eigenvalue of the mesh Laplacian, a measure of flux, is estimated, thus
extending the classical inequality for the Kirchoff Laplacian of graphs.

The Spectral Geometry of the Mesh Matrices of Graphs

Sylvain E. Cappell and Edward Y. Miller

Dedicated to the memory of Jacob Eli Goodman

Abstract

The mesh matrix $Mesh(G,T_{0})$ of a connected finite graph
$G=(V(G),E(G))=(vertices,edges)\ of\ G$ of with respect to a choice of a
spanning tree $T_{0}\subset G$ is defined and studied. It was introduced by
Trent [30, 31]. Its characteristic polynomial $det(X\cdot Id-Mesh(G,T_{0}))$
is shown to equal $\Sigma_{j=0}^{N}\ (-1)^{j}\ ST_{j}(G,T_{0})\ (X-1)^{N-j}\
(\star)$ where $ST_{j}(G,T_{0})$ is the number of spanning trees of $G$
meeting $E(G-T_{0})$ in j edges and $N=|E(G-T_{0})|$ . As a consequence, there
are Tutte-type deletion-contraction formulae for computing this polynomial.
Additionally, $Mesh(G,T_{0})-Id$ is of the special form $Y^{t}\cdot Y$ ; so
the eigenvalues of the mesh matrix $Mesh(G,T_{0})$ are all real and are
furthermore be shown to be $\geq+1$. It is shown that $Y\cdot Y^{t}$, called
the mesh Laplacian, is a generalization of the standard graph Kirchhoff
Laplacian $\Delta(H)=Deg-Adj$ of a graph $H$. For example, $(\star)$
generalizes the all minors matrix tree theorem for graphs $H$ and gives a
deletion-contraction formula for the characteristic polynomial of $\Delta(H)$.
This generalization is explored in some detail. The smallest positive
eigenvalue of the mesh Laplacian, a measure of flux, is estimated, thus
extending the classical inequality for the Kirchoff Laplacian of graphs.

##  1 Introduction

For a graph $H=(V(H),E(H))$ with vertices $V(H)$ and edges $E(H)$, two
distinct vertices, say $P,Q$, are called adjacent if there is an edge $e$ of
$H$ with $P,Q$ as end points. This is written as $P\sim Q$. The graph $H$ is
called connected if for any two distinct vertices, $P,Q$ there is a simple
path from $P$ to $Q$ in $H$, i.e., a sequence of distinct vertices
$R_{1},R_{2},\cdots,R_{K}$ with $P=R_{1},\ Q=R_{K}$ and $R_{k}\sim R_{k+1},\
k=1,\cdots,K-1$. The graph $H$ is called a tree if $H$ is connected and any
two distinct vertices are connected by a unique simple path. A subgraph
$T\subset G$ of a graph $G$ is called a spanning tree of $G$ if the subgraph
$T$ is a tree and $V(T)=V(G)$, i.e., $T$ and $G$ contain the same vertices.

The context of the mesh matrix studied here is that of a pair $(G,T_{0})$ with
$G$ a connected finite graph and the chosen subgraph $T_{0}\subset G$ a
spanning tree of $G$. It is called $Mesh(G,T_{0})$ and is a real, symmetric,
$|E(G-T_{0})|\times|E(G-T_{0})|$ matrix.

Before giving the precise definition of the mesh matrix $Mesh(G,T_{0})$ of a
connected graph $G$ with a choice $T_{0}\subset G$ of spanning tree of $G$
(see section 2) , it will be helpful to recall two relevant items and state
two theorems:

Item 1: An interesting and classically studied invariant of a graph $G$ is the
number of spanning trees in $G$ [32]:

$ST(G):=\\#\ spanning\ trees\ of\ G.$

Naturally, $ST(G)=0$ if $G$ is not connected. This invariant satisfies Tutte-
type deletion-contraction formulas. More generally, if $H\subset G$ is a
subgraph and
$N=|E(G-H)|$, one may introduce a mild generalization, the polynomial

$ST(G,H)(X)=\Sigma_{j=0}^{N}\ (-1)^{j}\ ST_{j}(G,H)\ X^{N-j}$

with $ST_{j}(G,H)$ the number of spanning trees of $G$ which contain precisely
$j$ edges of $E(G-H)$. Again, see section 4, there are Tutte-type deletion-
contraction formulas for computing these polynomials.

###### Theorem 1.1

Let $G$ be a connected graph and $T_{0}\subset G$ a spanning tree in $G$, then
the characteristic polynomial of the mesh matrix $Mesh(G,T_{0})$ is specified
by

$det(X\cdot Id-Mesh(G,T_{0}))=ST(G,T_{0})(X-1).$

See theorem 2.2 for the complete theorem.

In view of the above remarks, this polynomial can be computed directly by
deletion-contraction methods.

Item 2: It is claimed that $Mesh(G,T_{0})$ is of the special form
$Id+Y^{t}\cdot Y$ and

$Y\cdot Y^{t},\ where\ Y\ is\ defined\ via\ (G,T_{0}),$

is a natural generalization of the graph Laplacian $\Delta(H)=Deg-Adj$ of a
graph $H$. This will be seen as follows:

Let $H$ be a graph and $W$ be a disjoint point. Form $C(V(H))$, the cone on
the vertices $V(H)$ of $H$ from cone point $W$, by attaching an edge
$\vec{PW}$ for each vertex $P$ of $H$; in particular, the vertices of
$C(V(H))$ is the union $V(H)\sqcup\\{W\\}$. Let the “ $H$ with cone on
vertices added”, be the union

$C^{\prime}(H)=H\sqcup C(V(H)),$

i.e., the graph $C^{\prime}(H)$ has vertices
$V(C^{\prime}(H))=V(H)\sqcup\\{W\\}$ and edges
$E(C^{\prime}(H))=E(H)\sqcup\\{\vec{PW}\ for\ P\ a\ vertex\ of\ H\\}$. Note
that $C^{\prime}(H)$ is connected and $C(V(H))$ is a spanning tree of
$C^{\prime}(H)$.

###### Theorem 1.2

Let $H$ be a finite graph. The characteristic polynomials of the Kirchhoff
graph Laplacian $\Delta(H)=Deg-Adj$ of a graph $H$ and that of the mesh matrix
of the pair $(C^{\prime}(H),C(V(H))$ are related by

$\begin{array}[]{l}Mesh(C^{\prime}(H),C(V(H)))=Id+Y^{t}\cdot Y\ \ \ with\ \ \
\Delta(H)=Y\cdot Y^{t}=\Delta(C^{\prime}(H),C(V(H))).\\\ \end{array}$

In particular, $\Delta(H)$ has the same non-vanishing eigenvalues counted with
multiplicities as $Y^{t}\cdot Y=Mesh(C^{\prime}(H),C(V(H)))-Id$ and as $Y\cdot
Y^{t}=\Delta(C^{\prime}(H),C(V(H)))$.

See section 2.

By these means, one sees that the mesh Laplacian defined by
$\Delta(G,T_{0})=Y\cdot Y^{t}$ generalizes to the mesh setting the well known
and studied Kirchhoff graph Laplacian [23] of a graph $H$, $\Delta(H)$.

In particular, in view of item # 1, the characteristic polynomial of the graph
Laplacian of a graph $H$, namely $det(T\cdot Id-\Delta(H))$, acquires a Tutte-
type deletion-contraction method of computation.

Recently, an elegant paper of F. Aliniaeifard, V. Wang,and S. Van
Willigenburg, “Deletion-Contraction for a Unified Laplacian and Applications”,
[2], has appeared with a deletion-contraction method for computing the
characteristic polynomial of the graph Laplacian of a graph $H$ among other
valuable results. It proceeds by finding such a formula in terms of an
extension $det(T\cdot\epsilon-\Delta(H))$ where $\epsilon$ is a diagonal
matrix of vertex weights. The computation stays in this restricted context as
opposed to the above which stays in the context defined for pairs $(G,H)$ with
$G$ a graph and $H$ a subgraph. The methods for these cases are analogous, but
different.

The definition of the mesh matrix $Mesh(G,T_{0})$ appears in section 2 along
with the proof of theorem 1.2 in a more explicit form in theorem 2.3. Section
3 contains the proofs of theorems 1.1, 2.2, 2.4. In section 4 , the Tutte-type
deletion-contraction formulas for $ST(G)$ and the polynomial $ST(G,H)(X)$ are
described. In section 5 , by specializing theorem 2.2 to the case
$(C^{\prime}(H),C(V(H)))$ and employing theorem 1.2, one recovers the all
minors theorem for graphs; see theorem 5.2. Section 6 proves that
$det(Mesh(G,T_{0}))=ST(G,T_{0})$ is the order of the torsion group
$C_{1}(G;\mathbb{Z})/[Z_{1}(G;\mathbb{Z})\oplus\Pi(B^{1}(G;\mathbb{Z}))]$
defined there. Section 7 introduces eigenvalue estimates for the smallest
positive eigenvalue of $\Delta(G,T_{0})$, a measure of the flux from $T_{0}$
to $T_{0}$ through $G-T_{0}$. The present authors’ earlier work on mesh
matrices on general C-W complexes appeared in [8]; section 8 below concerns a
higher dimensional generalization of theorem 2.2 with a correction of a
slightly misstated theorem of that paper.

##  2 Definition of the mesh matrix $Mesh(G,T_{0})$:

The context of the mesh matrix is that of a pair $(G,T_{0})$ with $G$ a
connected graph and $T_{0}\subset G$ a spanning tree of $G$.

Definition of the mesh matrix : $Mesh(G,T_{0})$ .

Now let $T_{0}$ be a choice of spanning tree of $G$. Let
$e_{1},\cdots,e_{|E(G-T_{0})|}$ be a listing of edges of $E(G-T_{0})$ and
$f_{1},f_{2},\cdots,f_{|E(T_{0})|}$ comprise the edges of $E(T_{0})$.

Choose for each edge of $G$ a direction, giving a representation
$\vec{e_{j}}=\vec{e_{j}}[P_{j},Q_{j}]$ with $\vec{e}_{j}$ going from vertex
$P_{j}$ to vertex $Q_{j}$ and $\vec{f}_{k}=\vec{f}_{k}[R_{k},S_{k}]$ going
from vertex $R_{k}$ to vertex $S_{k}$.

Consider the directed edge $\vec{e}_{j}\in E(G-T_{0})$ with end points
$P_{j},Q_{j}$. Then $P_{j},Q_{j}$ are vertices of the spanning tree $T_{0}$;
so if $P_{j}\neq Q_{j}$ there is a unique directed simple path from $Q_{j}$ to
$P_{j}$ in the spanning tree $T_{0}$, given by distinct vertices say
$Q_{j}=R_{j,1},R_{j,2},\cdots,R_{j,n[j]}=P_{j}$ with $R_{j,t}\sim R_{j,t+1}$
and the edge $[R_{j,t}\rightarrow R_{j,t+1}]$ chosen in $T_{0}$. Let
$N=|E(G-T_{0})|$.

Now define the mapping

$\begin{array}[]{l}D:C_{1}(E(G-T_{0});\mathbb{R})\rightarrow
C_{1}(T_{0};\mathbb{R})\\\ \ by\ \ D(1\cdot\vec{e}_{j})=0\ if\ 1\leq j\leq N\
and\ e_{j}\ is\ a\ loop\\\ \ by\
D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])=\Sigma_{t=1}^{n[j]-1}\ \ 1\cdot\
[R_{j,t}\rightarrow R_{j,t+1}]\ \ if\ 1\leq j\leq N\ and\ P_{j}\neq
Q_{j}.\end{array}$

As seen the 1-chain $D(1\cdot\vec{e}_{j}[P_{j},Q_{k}])$ has boundary
$\partial(D(1\cdot\vec{e}_{j}))=1\cdot P_{j}-1\cdot Q_{j}$ as the directed
path starts at $Q_{j}$ and ends at $P_{j}$.

In this manner one has a uniquely defined 1-chain for $G$, namely:

$Z[j]=1\cdot\vec{e}_{j}+D(1\cdot\vec{e}_{j})\ for\ j=1,\cdots,\ N\ =\
|E(G-T_{0})|.$

This 1-chain is a 1-cycle, it has boundary $0$, and $D(1\cdot\vec{e}_{j})$
supported in $T_{0}$. If $e_{j}$ is not a loop, this 1-cycle is a directed
simple closed curve, it goes from $P_{j}$ to $Q_{j}$ in $E(G-T_{0})$, then
back through the spanning tree $T_{0}$ from $Q_{j}$ to $P_{j}$.

Since $Z[j]$ restricted to $E(G-T_{0})$ becomes $1\cdot\vec{e}_{j}$, the
linear mapping defined by $1\cdot\vec{e}_{j}\mapsto Z[j]$ is one to one. It
maps $C_{1}(E(G-T_{0});\mathbb{Z})$ into the integral 1-cycles,
$Z_{1}(G;\mathbb{Z})$. Indeed, this gives an isomorphism:

$C_{1}(E(G-T_{0});\mathbb{Z})\stackrel{{\scriptstyle\cong}}{{\rightarrow}}Z_{1}(G;\mathbb{Z}).$

In particular, these 1-cycles $\\{Z[j]\\}$ form an integral basis for the
integral 1-cycles of $G$.

[Proof: For any 1-cycle $z=\Sigma_{j=1}^{N}\
b_{j}\cdot\vec{e}_{j}+\Sigma_{k=1}^{|E(T_{0})|}\ c_{k}\cdot\vec{f}_{k}$ of
$G$, the 1-chain $z-\Sigma_{j=1}^{N}\ b_{j}\cdot Z[j]$ is supported in $T_{0}$
and is a 1-cycle, so equals the zero chain.] The mesh matrix of Trent [30, 31]
may be defined using this integral basis, $\\{Z[j]\\}$, of 1-cycles of $G$.

Having chosen a spanning tree $T_{0}$ of the graph $G$, and having made these
directed edge choices, one defines the mesh matrix for the pair $(G,T_{0})$
via the intersection pairing on $C_{1}(G;\mathbb{R})$:

$Mesh(G,T_{0})=\\{\ <Z[j_{1}],\ Z[j_{2}]>\ |\ 1\leq j_{1},j_{2}\leq
N=|E(G-T_{0})|\\}.$

The basic theorem about the mesh matrix $Mesh(G,T_{0})$ is the theorem of
Trent evaluating its determinant. This is studied in more detail in [8] along
with higher dimensional generalizations.

######  Theorem 2.1 (Trent [30, 31] )

For a connected graph $G$, the determinant
$det(Mesh(G,T_{0}))$ equals the number of spanning trees of $G$, or as in item
# 1 equals $ST(G)$.

More explicitly, expand the 1-cycle $Z[k]$ as a column $|E(G)|\times 1$
vector, say $z[k]$, in terms of the basis $\\{1\cdot\vec{e}_{j}\\}$ and then
$\\{1\cdot\vec{f}_{k}\\}$ of $C_{1}(G;\mathbb{Z})$ and form the $|E(G)|\times
N$ matrix of column vectors $Y[+]:=(z[1],\cdots,z[N])$, then
$Mesh(G,T_{0})=Y[+]^{t}\cdot Y[+],$ As seen $Y[+]$ has the special form
$Y[+]=\left(\begin{array}[]{c}\ Id\\\ Y\end{array}\right)$ where $Id$ denotes
the $N\times N$ identity matrix and $Y$ is the $|E(T_{0})|\times|E(G-T_{0})|$
matrix representing the linear mapping $D$.

As a consequence,

$\begin{array}[]{l}Mesh(G,T_{0})=Y[+]^{t}\cdot Y[+]=Id\ \ +\ \ (Y^{t}\cdot Y)\
and\\\ charactistic\ polynomial\ of\ Mesh(G,T_{0})=det(X\ Id-Y[+]^{t}\cdot
Y[+])\\\ =det((X-1)\ Id-Y^{t}\cdot Y)\\\ =characteristic\ polynomial\ of\
(Y^{t}\cdot Y)\ evaluated\ at\ (X-1).\end{array}$

In particular, the eigenvalues of the reduced mesh matrix
$Mesh^{\\#}(G,T_{0})\stackrel{{\scriptstyle def.}}{{:=}}Y^{t}\cdot Y$ are real
and non-negative, while those of the mesh matrix $Mesh(G,T_{0})$ are obtained
by adding $+1$ to those of the reduced mesh matrix.

The following theorem specifies the coefficients of the characteristic
polynomial of the mesh matrix and the reduced mesh matrix of $(G,T_{0})$. It
is a restatement of theorem 1.1.

###### Theorem 2.2

Let $G$ be a connected graph and $T_{0}$ a spanning tree of $G$. For
$j=1,\cdots,N=|E(G-T_{0})|$, denote by $ST_{j}(G,F)$ the number of spanning
trees $T$ of $G$ such that $|E(T)\cap(E(G-T_{0}))|=j$. Then

$\begin{array}[]{l}det((U+1)Id-Mesh(G,T_{0}))=det(U\ Id-
Mesh^{\\#}(G,T_{0}))\\\ =U^{N}+\Sigma_{j=1}^{N}\ (-1)^{j}ST_{j}(G,T_{0})\
U^{N-j}=ST(G,T_{0})(U).\end{array}$

Setting $U=-1$ gives $det(Mesh(G,T_{0}))=\Sigma_{j=0}^{N}\
ST_{j}(G,T_{0})=ST(G)$ in agreement with Trent’s theorem 2.1. Here $Y^{t}\cdot
Y$ represents the reduced mesh matrix $Mesh^{\\#}(G,T_{0})$ and
$Mesh(G,T_{0})=Id+Y^{t}\cdot Y$.

In terms of the previously defined polynomials for $H$ a subgraph of $G$
listed in item # 1, section 1 $ST(G,H)(U),$ this theorem evaluates the
characteristic polynomials of the reduced mesh matrix $Y^{t}\cdot Y$ as equal
to $ST(G,T_{0})(U)$. In this larger context of pairs of graphs, $(G,H)$ one
has, see section 4, deletion-contraction formulas which may be used to compute
this invariant.

It is natural to define the $|E(T_{0})|\times|E(T_{0})|$ matrix

$Y\cdot Y^{t}\ as\ the\ Mesh\ Laplacian\ of\ (G,T_{0})\
=\Delta(G,T_{0})=D\cdot D^{\star}.$

This terminology is consistent with the standard notations in view of the
following theorem. [See [15, 16] for a discussion of $\Delta(G)=Deg-Adj$ and
its normalized version.]

As in item # 2, section 1, for a graph $H$, let $C^{\prime}(H)=H\cup C(V(H))$
be $H$ with the cone on vertices of $H$ added,

###### Theorem 2.3

For a graph $H$, consider $C^{\prime}(H)$ and its subcone $C(V(H))$ with cone
point $W$. Then $C^{\prime}(H)$ is connected and $C(V(H))$ is a spanning tree
for $C^{\prime}(H)$.

Following the above construction, for each edge of $H$ once directed, say
$\vec{e}_{j}=\vec{e}_{j}[P_{j}\rightarrow Q_{j}],j=1,\cdots,|E(H)|$ associate
the 1-cycle, $Z[j]\newline =1\cdot\vec{e}_{j}+1\cdot(Q_{j}\rightarrow
W)-1\cdot(P_{j}\rightarrow W)$ of $C^{\prime}(H)$, then the associated matrix
$Y$ defined by

$\begin{array}[]{l}1\cdot\vec{f}_{j}\mapsto
D(1\cdot\vec{f}_{j})=1\cdot(Q_{j}\rightarrow W)-1\cdot(P_{j}\rightarrow W)\in
C_{1}(C(V(H));Z)\\\ under\ the\ identification\ C_{1}(C(V(H));Z)\cong
C_{0}(V(H);Z)\ given\ by\\\ \ 1\cdot(P\rightarrow W)\mapsto 1\cdot
P\end{array}$

becomes [under this identification] precisely the standard boundary mapping
$\partial:C_{1}(H;Z)\rightarrow C_{0}(H;Z)$,
$\partial(1\cdot\vec{f}_{j})=1\cdot Q_{j}-1\cdot P_{j}$ of the graph $H$.

Consequently, the mesh Laplacian of $(G,T_{0})=\Delta(G,T_{0})$ represented by
$Y\cdot Y^{t}$ for this special case $(C^{\prime}(H),C(V(H))$ becomes exactly
the graph Laplacian matrix $\Delta(H)=\partial\cdot\partial^{t}=Deg-Adj$ of
$H$.

Also $Mesh(C^{\prime}(H),C(V(H))=Id+Y^{t}\cdot
Y=Id+Mesh^{\\#}(C^{\prime}(H),C(V(H))$.

The significance of this theorem is that the mesh Laplacian matrix $Y\cdot
Y^{t}$ representing $D\cdot D^{\star}$ may be viewed as a natural
generalization of the Kirchhoff graph Laplacian $\Delta(H)$ to the context of
mesh matrices for pairs $(G,T_{0})$.

Since eigenvalues of $Y\cdot Y^{t}$ and $Y^{t}\cdot Y$ are non-negative, and
their non-vanishing eigenvalues are equal [counted with multiplicities] the
characteristic polynomials of $Y\cdot Y^{t}$ and $=Y^{t}\cdot Y$ are related
by

$U^{|E(T_{0})|}\cdot det(U\ Id-Y^{t}\cdot Y)=\\\ U^{|E(G-T_{0})|}\cdot det(U\
Id-Y\cdot Y^{t}).$

Applied to the case of $C^{\prime}(H)$ theorem 1.2 of item # 2 follows.

Additionally, the mesh Laplacian $\Delta(G,T_{0})=Y\cdot Y^{t}$ has a nice
direct description:

###### Theorem 2.4

Let the edges of $E(T_{0})$ be directed and labeled as
$\vec{f}_{k},k=1,\cdots,|E(T_{0})|$. Then the mesh Laplacian
$\Delta(G,T_{0})=Y\cdot Y^{t}$ is specified by

$\begin{array}[]{l}(Y\cdot Y^{t})_{\vec{f}_{k},\vec{f_{k}}}=\\#\\{e\in
E(G-T_{0})\ with\ f_{k}\ in\ the\ support\ of\ D(1\cdot\vec{e})\\},\\\ for\
k\neq l\\\ (Y\cdot Y^{t})_{\vec{f}_{k},\vec{f_{l}}}=Sign(k,l)\cdot\\#\\{e\in
E(G-T_{0})\ with\ f_{k}\ and\ f_{l}\ in\ the\ support\ of\
D(1\cdot\vec{e})\\}\end{array}$

Here $Sign(k,l)=\pm 1$ for $k\neq l$ is defined by taking the unique directed
path, $\gamma$, in $T_{0}$ from the edge $f_{k}$ to the edge $f_{l}$. Let
$Sign(k,l)=<1\cdot\vec{f}_{k},\vec{\gamma}>\cdot<1\cdot\vec{f}_{l},\vec{\gamma}>$.

##  3 Proof of theorems 1.1, 2.2, 2.4 :

Now the characteristic polynomial of $Mesh(G,T_{0})$ represented by
$Y[+]^{t}\cdot Y[+]$ is easily determined by the following method: Let

$det(X\ Id-Y[+]^{t}\cdot Y[+])=X^{N}+\Sigma_{j=1}^{N}(-1)^{j}\ b_{j}\
X^{N-j}.$

Firstly, by expanding to get the coefficient of $X^{N-j}$, $b_{j}$ equals the
sum over $j\times j$ diagonal minors of $Y[+]^{t}\cdot Y[+]$ of the
determinant $det(minor)$. This sum may be organized as summing over a choice
of $j$ indices say $1\leq k_{1}<k_{2}<\cdots<k_{j}\leq N$ [specifying the rows
and corresponding columns of the diagonal block chosen].

More explicitly, let $Y[+][k_{1},\cdots,k_{j}]$ denote the $|E(G)|\times j$
matrix from $Y[+]$ obtained by deleting all but these $j$ specified columns.
Then the desired block determinant equals

$det(\ Y[+][k_{1},\cdots,k_{j}]^{t}\cdot Y[+][k_{1},\cdots,k_{j}]\ ).$

Now compare this last to the determinant of the mesh matrix for the subgraph
$G[k_{1},k_{2},\cdots,k_{j}]$ obtained from the spanning tree $T_{0}$ by
adding in the $j$ edges $\vec{e_{k_{a}}},\ a=1,\cdots,j$ of $E(G-T_{0})$ to
$T_{0}$. Each of the 1-cycles $Z[k_{a}]$ lie in $G[k_{1},k_{2},\cdots,k_{j}]$.
As seen, $Y[+][k_{1},\cdots,k_{j}]^{t}\cdot
Y[+][k_{1},\cdots,k_{j}]=Mesh(G[k_{1},k_{2},\cdots,k_{j}];T_{0})$.
Consequently, by the results of Trent:

$\\#spanning\ trees\ of\ G[k_{1},\cdots,k_{j}]=det(\
Y[+][k_{1},\cdots,k_{j}]^{t}\cdot Y[+][k_{1},\cdots,k_{j}]\ ).$

So in total, the coefficient $b_{j}$ is expressed in terms of spanning trees.
More explicitly :

###### Lemma 3.1

Let $G$ be a connected graph and $T_{0}$ be a spanning tree of $G$ and
$N=|E(G-T_{0})|$. Then the characteristic polynomial of the mesh matrix
$Mesh(G,T_{0})$ is given by

$det(X\ Id-(Y[+]^{t}\cdot Y[+])=X^{N}+\Sigma_{j=0}^{N}(-1)^{j}\ b_{j}\
X^{N-j}$

with $b_{j}$ equal to the sum over $j$ distinct indices $1\leq
k_{1}<k_{2}<\cdots k_{j}\leq N$ of the number of spanning trees in the
subgraph $T_{0}\cup(e_{k_{1}}\cup e_{k_{2}}\cup\cdots\cup e_{k_{j}})$.

Now consider this sum $b_{j}$ in detail with reference to the integers

$ST_{j}(M,T_{0})=\\#\\{\ spanning\ trees\ T\ of\ G\ with\ |E(T)\cap
E(G-T_{0})|=j\ \\}.$

Each spanning tree $T$ counted in $ST_{j}(G,T_{0})$ appears exactly once in
the counting of $b_{j}$ as it fills in all the j added edges of $E(G-T_{0})$.

Each spanning tree $T$ of $ST_{j-1}(G,T_{0})$ fills in $j-1$ edges of
$E(G-T_{0})$ so to get $j$ one needs to chose 1 from the remaining $N-(j-1)$
edges. Thus each spanning tree $T$ of $ST_{j-1}(G,T_{0})$ appears exactly
${{N-(j-1)}\choose{1}}={{N-(j-1)}\choose{N-j}}$ times in $b_{j}$.

Each spanning tree $T$ of $ST_{j-2}(G,T_{0})$ fills in $j-2$ edges of
$E(G-T_{0})$ so to get $j$ one needs to chose 2 from the remaining $N-(j-2)$
edges. Thus each spanning tree $T$ of $ST_{j-2}(G,T_{0})$ appears exactly
${{N-(j-2)}\choose{2}}={{N-(j-2)}\choose{N-j}}$ times in $b_{j}$.

Combining these observations, proves the formula for $N\geq j\geq 1$:

$b_{j}=\Sigma_{t=0}^{j}\ {{N-(j-t)}\choose{N-j}}\ ST_{j-t}(G,T_{0}).$

It also holds for $j=0$ since both sides equal +1. Inserting [and letting
$k=j-t$] this gives:

$\begin{array}[]{l}det(X\ Id-Mesh(G,T_{0}))=\Sigma_{j=0}^{N}\ (-1)^{j}\ b_{j}\
X^{N-j}\\\ =\Sigma_{j=0}^{N}\ (-1)^{j}[\Sigma_{t=0}^{j}\
{{N-(j-t)}\choose{N-j}}\ ST_{j-t}(G,T_{0})]\ X^{N-j}\\\ =\Sigma_{k=0}^{N}(\
\Sigma_{j=k}^{N}\ (-1)^{j}\ {{N-k}\choose{N-j}}X^{N-j}\ )\ ST_{k}(G,T_{0})\\\
=\Sigma_{k=0}^{N}\ (-1)^{k}\ (\Sigma_{j=k}^{N}(-1)^{j+k}\
{{N-k}\choose{N-j}}X^{N-j})\ ST_{k}(G,T_{0})\\\ =\Sigma_{k=0}^{N}\ (-1)^{k}\
(X-1)^{N-k}\ ST_{k}(G,T_{0})=det((X-1)\ Id-Mesh^{\\#}(G,T_{0})).\end{array}$

Thus

$\begin{array}[]{l}det((U+1)\ Id-Mesh(G,T_{0}))=det(U\ Id-
Mesh^{\\#}(G,T_{0}))\\\ =U^{N}+\Sigma_{j=1}^{N}\ (-1)^{j}\ ST_{j}(G,T_{0})\
U^{N-j}\end{array}$

as claimed.

Proof of theorem 2.4:

For directed edge $e_{j}$ with end points directed by $P_{j}\rightarrow Q_{j}$
let $C[Q_{j},P_{j}]$ be the unique simple path from $Q_{j}$ to $P_{j}$ in
$T_{0}$. By definition $D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])$ is then the sum of
these directed edges of $C[P_{j},Q_{j}]$ regarded as a 1-chain.

Tautologically, the mapping $D$ and adjoint $D^{\star}$ have the properties:

$\begin{array}[]{l}If\ P_{j}\neq Q_{j},\
D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])=\Sigma_{f_{k}\ in\ support\ of\
C[Q_{j},P_{j}]}\ \
<1\cdot\vec{f}_{k},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>\cdot\vec{f}_{k};\\\
D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])=0\ if\ e_{j}\ is\ a\ loop\
i.e.,P_{j}=Q_{j}.\\\ Similarly,\\\ if\ f_{k}\ not\ a\ loop,\ \
D^{\star}(1\cdot\vec{f}_{k})=\Sigma_{f_{k}\ in\ support\ of\ C[Q_{j},P_{j}]}\
\ <1\cdot\vec{f}_{k},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>\cdot\vec{e}_{j};\\\
D^{\star}(1\cdot\vec{f}_{k})=0\ if\ f_{k}\ is\ a\ loop.\\\ \end{array}$

Hence, by $<f,\Delta(G,T_{0})(f)>=<D^{\star}(f),D^{\star}(f)>$, the mesh
Laplacian matrix is defined by

$\begin{array}[]{l}\Delta(G,T_{0})_{f_{k},f_{l}}=\Sigma_{e_{j}\ with\ f_{k}\
and\ f_{k}\ in\ the\ support\ of\ C[Q_{j},P_{j}]}\\\ \hskip
72.26999pt<1\cdot\vec{f}_{k},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>\cdot<1\cdot\vec{f}_{l},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>.\end{array}$

For $k=l$, this give the desired result. For $k\neq l$, one may change the
ordering of $Q_{j},P_{j}$ if necessary so that the unique path
$C[Q_{j},P_{j}]$ running from $Q_{j}$ to $P_{j}$ in $T_{0}$ containing the
edges $f_{k},f_{l}$ gives the unique directed path, say $\vec{\gamma}$, in
$T_{0}$ from $f_{k}$ to $f_{l}$. In particular, for any $e_{j}$ with
$f_{k},f_{l}$ in $C[Q_{j},P_{j}]$ one has the equality independent of $j$

$\begin{array}[]{l}<1\cdot\vec{f}_{k},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>\cdot<1\cdot\vec{f}_{l},D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])>=<1\cdot\vec{f}_{k},\vec{\gamma}>\cdot<1\cdot\vec{f}_{l},\vec{\gamma}>,\\\
\end{array}$

as desired.

##  4 Properties of $ST(G,H)(X)$; Computation by deletion contraction methods:

It is well known that the number of spanning trees, $SF(G)$, obeys nice
formulas for deletion and contraction [32].

For a graph $G$ and a edge $e$, let $G\backslash e$ be the graph obtained by
deleting the open edge $e$ preserving the end points, i.e, $V(G\backslash
e)=V(G)$ and $E(G\backslash e)=E(G)-\\{e\\}$. Let $G/e$ denote the graph
obtained by contracting the end points of $e$ along with all of the edge $e$
to a single point.

As $ST(G)$ counts spanning trees, $ST(G)=0\ if\ G\ is\ disconnected.$

As no tree contains a loop, $ST(G)=ST(G\backslash e)\ if\ e\ is\ a\ loop.$

If $e$ is an edge with distinct end points, then the spanning trees of $G$
counted in $SF(G)$ either do not contain $e$ and are faithfully counted in
$ST(G\backslash e)$ or contain the edge $e$. In this second case, the spanning
trees of $G/e$ are exactly the result of collapsing the edge $e$ in a spanning
tree of $G$ containing $e$. In this manner, one gets the well known relations:

$ST(G)=ST(G\backslash e)+ST(G/e)\ if\ e\ an\ edge\ of\ G\ is\ not\ a\ loop.$

If $e$ is an isthmus, that is all trees of $G$ contain the edge $e$, then
$G\backslash e$ is disconnected, so

$ST(G)=ST(G\backslash e)+ST(G/e)=ST(G/e)\ if\ e\ is\ an\ isthmus.$

By using these relations in the context of a graph $G$ and a subgraph $H$ with

$ST(G,H)(X)=\Sigma_{j=0}^{N}\ (-1)^{j}\ ST_{j}(G,H)\ X^{N-j}\ and\ N=|E(G-H)|$

where $ST_{j}(G,H)$ is the number of spanning trees $T$ of $G$ with
$|E(T)\cap(E(G)-E(H))|=j$, one obtains by counting:

$\begin{array}[]{l}ST(G,H)(X)=ST(G,H\backslash e)(X)\ if\ e\in H\ is\ a\
loop;\\\ ST(G,H)(X)=ST(G,H\backslash e)(X)+ST(G,H/e)(X)\ if\ e\in H\ is\ not\
a\ loop;\\\ ST(G,H)(X)=ST(G\backslash e,H)(X)\ if\ e\in G\ is\ a\ loop;\\\
ST(G,H)(X)=ST(G\backslash e,H)(X)-X\cdot ST(G/e,H)(X)\\\ \hskip 36.135ptif\
e\in G\ is\ not\ a\ loop.\end{array}$

These deletion-contraction formulas give an inductive method for computing the
polynomials $SF(G,H)$.

By theorem 2.2, $det(X\cdot Id-Mesh^{\\#}(G,T_{0}))=ST(G,T_{0})(X)$ so these
formulas give a deletion-contraction method for computing the characteristic
polynomial of the reduced mesh matrix $Mesh^{\\#}(G,T_{0})$ and the mesh
matrix $Mesh(G,T_{0})=Mesh^{\\#}(G,T_{0})+Id$.

As a special case, by theorem 2.3, the characteristic polynomial of the graph
Laplacian $\Delta(H)$ of a graph $H$ equals that of
$\Delta(C^{\prime}(H),C(V(H)))$ so these deletion-contraction formulas give a
method that also applies to the graph Laplacian $\Delta(H)$.

Recall from item # 2, section 1, the paper [2] gives an alternative method to
get deletion-contraction formulas for computation in these graph Laplacian
cases.

##  5 Recapturing the All Minors Matrix Tree Theorem

The all minors matrix tree theorem, see [12, 13, 27], asserts:

###### Theorem 5.1

Let $H$ be a finite graph. Let a spanning forest $F$ in $H$ consist of the
union of $K$ disjoint trees, say $F=\sqcup_{j=1}^{K}\ T[j],\subset H$ which
spans, i.e., $V(F)=V(H)$. Let a spanning forest $F$ of $K$ components have
multiplicity $mult(F)=\prod_{j=1}^{K}\ |V(T[j])|$. Then the characteristic
polynomial of the graph Laplacian
$\Delta(H)=\partial\cdot\partial^{\star}=Deg-Adj$ is given by

$\begin{array}[]{l}det(T\cdot
Id-\Delta(H))=T^{|V(H)|}+\Sigma_{j=1}^{|V(H)|-1}\ (-1)^{j}\ b_{j}(H)\
T^{|V(H)|-j}\\\ with\ b_{j}(H)=\Sigma_{F\ a\ spanning\ forest\ of\ H\ with\
|V(H)|-j\ components}\ \ mult(F).\end{array}$

Note: Let a spanning rooted forest consist of a spanning forest $F$ and a
choice of a vertex, say $P_{j}\in V(T[j])$, called roots for each $j$. Then

$b_{j}(H)=\\#\ spanning\ rooted\ forests\ in\ H\ with\ |V(H)|-j\ components$

.

Now by contrast consider the spanning trees $T$ of $C^{\prime}(H)=H\cup
C(V(H))$, obtained from the graph $H$ with the cone on the vertices added.
Necessarily, the spanning tree $T$ must contains the cone point, say $W$, and
all vertices of $H$. Also, the intersection $F=T\cap H$ is a spanning forest
in $H$, say $F=\sqcup_{j=1}^{K}\ T[j]$ with $K$ components and each $T[j]$ a
tree in $H$. To complete the tree $T$ in $C^{\prime}(H)$ each component of
$F=\sqcup_{j=1}^{K}\ T[j]$ must be joined by exactly one edge of the form
$\vec{P_{j}W}$ with $P_{j}\in V(T[j])$. So one has the equality

$\begin{array}[]{l}\\#\\{spanning\ trees\ T\ in\ C^{\prime}(H)\ with\
|E(T)\cap C(V(H))|=K\\}\\\ \\#\\{spanning\ rooted\ forests\ F\ in\ H\ with\ K\
components\\}\\\ =\Sigma_{spanning\ forests\ F\ in\ H\ with\ K\ components}\ \
mult(F).\end{array}$

By these means the all minors matrix tree theorem can be recast in the form

######  Theorem 5.2 (All minors matrix tree theorem)

:

$\begin{array}[]{l}det(T\cdot
Id-\Delta(H))=T^{|V(H)|}+\Sigma_{j=1}^{|V(H)|-1}\ (-1)^{j}\ b_{j}(H)\
T^{|V(H)|-j}\\\ with\ b_{j}(H)=\\#\\{spanning\ trees\ T\ in\ C^{\prime}(H)\
with\ |E(T)\cap C(V(H))|=|V(H)|-j\\}\\\ =\\#\\{spanning\ trees\ T\ in\
C^{\prime}(H)\ with\ |E(T)\cap E(H)|=j\\}\\\
=ST_{j}(C^{\prime}(H),C(V(H)))\end{array}$

The last equalities use the fact that a spanning tree $T$ of $C^{\prime}(H)$
will have $|V(C^{\prime}(H))|-1=|V(H)|$ edges.

Hence, one sees that the all minors matrix tree theorem is the special case
with $(G,T_{0})=(C^{\prime}(H),C(V(H)))$ of theorem 2.2 in view of theorem
2.3.

##  6  # spanning trees as the order of a torsion group associated to $G$:

Let $G$ be a connected graph with choices of directed edges as above. Let
$Z_{1}(G;Z)$ be the integral 1-cycles, i.e., the kernel of the boundary
mapping $\partial:C_{1}(G;\mathbb{Z})\rightarrow C_{0}(G;\mathbb{Z})$; let
$B^{1}(G;Z)$ be the 1-coboundaries i.e., the image of the dual coboundary
mapping
$\partial^{\star}:C^{0}(G;\mathbb{Z})=Hom(C_{0}(G;\mathbb{Z}),\mathbb{Z})\stackrel{{\scriptstyle
Hom(.,\partial)}}{{\rightarrow}}C^{1}(G;\mathbb{Z})=Hom(C_{1}(G;\mathbb{Z}),\mathbb{Z})$;
let

$\begin{array}[]{l}\Pi:C^{1}(G;\mathbb{Z})\rightarrow C_{1}(G;\mathbb{Z})\ be\
the\ isomorphism\ defined\ by\\\
{[F:E(G)\rightarrow\mathbb{Z}]}\mapsto[\Sigma_{\sigma\in E(G)}\
F(\sigma)\cdot\vec{\sigma}]\\\ \ with\ chosen\ direction\ \vec{\sigma}\ on\
an\ edge\ \sigma\ of\ G.\end{array}$

###### Theorem 6.1

The inclusion of integral chains
$[Z_{1}(G;\mathbb{Z})\oplus\Pi(B^{1}(G;\mathbb{Z}))]\subset
C_{1}(G;\mathbb{Z})$ is a rational equivalence; so the quotient
$U=C_{1}(G;\mathbb{Z})\ /\
[Z_{1}(G;\mathbb{Z})\oplus\Pi(B^{1}(G;\mathbb{Z}))]$ is a finite abelian
group. The order of this group is

$|\ U\ |=|\ C_{1}(G;\mathbb{Z})\ /\
[Z_{1}(G;\mathbb{Z})\oplus\Pi(B^{1}(G;\mathbb{Z}))]\ |=\\#\ spanning\ trees\
of\ G=ST(G)$

First, observe that the orthogonal complement of $Z_{1}(G;\mathbb{R})$ is
$\Pi(B^{1}(G;\mathbb{R}))$, so one gets an isomorphism of real vector spaces
$Z_{1}(G;\mathbb{R})\oplus\Pi(B^{1}(X;\mathbb{R}))=C_{1}(G;\mathbb{R}).$

Proof: If $<.,.>$ is the standard inner product on $C_{1}(X;\mathbb{R})$, then
one has for
$a\in Z_{1}(G,\mathbb{R}),b\in C_{0}(G;\mathbb{R})$,
$<a,\Pi(\delta(b))>=\delta(b)(a)=b(\partial a).$ Hence, $\partial a=0$ if and
only if $a$ is orthogonal to $\Pi(B^{1}(G;\mathbb{R})))$.

By this result, the associated embedding of lattices has finite quotient,

$U=C_{1}(G;\mathbb{Z})\ /\
[Z_{1}(G;\mathbb{Z})\oplus\Pi(B^{1}(G;\mathbb{Z}))].$

Next, let $T_{0}$ be a choice of spanning tree for $G$. Following the notation
of section 2, let the directed edges of $G-T_{0}$ be denoted by
$\vec{e}_{j},j=1,\cdots,|E(G-T_{0})|$. Let the directed edges of $T_{0}$ be
denoted by $\vec{f}_{k},k=1,\cdots,|E(T_{0})|$.

As above, consider the integer 1-cycles $Z[j],j=1,\cdots,|E(G-T_{0})|$. Here
the 1-cycle

$Z[j]=1\cdot\vec{e}_{j}+D(\vec{e}_{j}),\ j=1,\cdots,|E(G-T_{0}|$

has $D(\vec{e}_{j})$ supported in the tree $T_{0}$. As above, define the
$|E(T_{0})|\times|E(G-T_{0})|$ matrix $Y=\\{A[k,j]\\}$ by

$Z[j]=1\cdot\vec{e}_{j}+\Sigma_{k=1}^{|E(T_{0})|}\ Y[k,j]\ \vec{f}_{k},\ \ \
j=1,\cdots,|E(G-T_{0})|.$

Here the coefficients $Y[k,j]$ are either $0$ or $\pm 1$. As proved above,
these $Z[j]$’s form an integral basis for $Z_{1}(G;\mathbb{Z})$. That is, part
a) below is known.

###### Lemma 6.2

a) The 1-chains

$Z[\vec{e}_{j}]=1\cdot\vec{e}_{j}+D(\vec{e}_{j})=\vec{e}_{j}+\Sigma_{k=1}^{|E(T_{0})|}\
A[k,j]\ \vec{f}_{k},\ \ \ j=1,\cdots,|E(G-T_{0})|$

form an integral basis for $Z_{1}(G;\mathbb{Z})$.

b) The 1-chains

$b[\vec{f}_{k}]=1\cdot\vec{f}_{k}-\Sigma_{j=1}^{|E(G-T_{0})|}\ Y[j,k]\
\vec{e}_{j},\ \ k=1,\cdots,|E(T_{0})|$

form an integral basis for $\Pi(B^{1}(G;\mathbb{Z}))$.

Using the direct sum decomposition
$C_{1}(G;\mathbb{Z})=C_{1}(G-T_{0};\mathbb{Z})\oplus C_{1}(T_{0};\mathbb{Z}),$
write elements in column form:
$C_{1}(G;\mathbb{Z})=\left(\begin{array}[]{cc}C_{1}(G-T_{0};\mathbb{Z})\\\
C_{1}(T_{0};\mathbb{Z})\end{array}\right).$

As noted, the $\vec{e}_{j}\mapsto Z[\vec{e}_{j}]$ giving an integral basis of
$Z_{1}(G;Z)$ is represented by the matrix $\left(\begin{array}[]{cc}Id\\\
Y\end{array}\right)$ with $Y$ an integer valued matrix above. Granting lemma
6.2 part b), the mapping $\vec{f}_{k}\mapsto b[\vec{f}_{k}]$ giving an
integral basis of $\Pi(B^{1}(G;\mathbb{Z}))$ is represented by the matrix
$\left(\begin{array}[]{cc}-Y^{t}\\\ Id\end{array}\right).$

Thus, $|U|=det\left(\begin{array}[]{cc}Id&-Y^{t}\\\
Y&Id\end{array}\right)=det\left(\begin{array}[]{cc}Id+Y^{t}\ Y&-Y^{t}+Y^{t}\\\
Y&Id\end{array}\right)=det(Id+Y^{t}\ Y)=det(Mesh(G,T_{0})=ST(G)$ by Trent’s
theorem 2.1.

Proof of lemma 6.2 part b):

The first part about the 1-cycles $Z[j]$ has already been proved in section 2.

Pick a directed edge in $T_{0}$, say $\vec{f}_{k}=\vec{f}_{k}[R_{k}\rightarrow
S_{k}]$. Recall that the spanning tree $T_{0}$ is connected.

Decompose the set of vertices of $T_{0}$ into two disjoint non-empty sets
$V(T_{0})=A[k]\sqcup B[k]$ where $A[k]$ consists of the vertices of $T_{0}$
which can be connected to the initial vertex $R_{k}$ by a simple path not
including $f_{k}$ and $B[k]$ consists of the vertices of $T_{0}$ which can be
connected to the final vertex $S_{k}$ by a simple path not including $f_{k}$.
For convenience, chose the directions of the edges $\vec{e}_{j}$ [ which by
assumption range over $E(G-T_{0})$] so that if $\vec{e}_{j}$ has one end point
in $A[k]$ and the other in $B[k]$, then $\vec{e}_{j}$ is directed from the
point in $A[k]$ to the point in $B[k]$.

Now recall that for a vertex $P$ of $G$, the coboundary $\delta(1\cdot P)$ has
the property that $\Pi(\delta(X))$ is the 1-chain consisting of all edges with
distinct end points containing $P$ as a end point and directed [inwards]
towards $P$.

One easily sees that $\Pi(\delta(\Sigma_{b\in B[k]}\ 1\cdot b))$ consists of a
sum of two parts. Firstly $1\cdot\vec{f}_{k}$; and secondly a sum over all
edges $\vec{e}_{j}$ in $G-T_{0}$ with distinct end points and having one end
in $A[k]$ and the other in $B[k]$. This is usually called the cut defined by
$\vec{f}_{k}$. The edges $\vec{e}_{j}$ with this property have been directed
as going from $A[k]$ to $B[k]$.

Now consider the 1-cycle $Z[j]$ and its evaluation $<Z[j],1\cdot\vec{f}_{k}>$
; it equals zero unless $\vec{e}_{j}$ has one end in $A[k]$ and the other in
$B[k]$. It has sign $-1$ as $\vec{e}_{j}$ goes from $A[k]$ to $B[j]$.

Hence,

$\Sigma_{j}\ <z[j],1\cdot\vec{f}_{k}>\ \vec{e}_{j}=-\Sigma_{summed\ as\
below}\ Y[j,k]\ \vec{e}_{j}$

with the above sum is only over the directed edges $\vec{e}_{j}$ of $G-T_{0}$
going from $A[k]$ to $B[k]$ with direction from $A[k]$ to $B[k]$. Note
$Y[j,k]=0$ otherwise.

In total then

$\Pi(\delta(\Sigma_{b\in B[k]}\ 1\cdot b)=1\cdot\vec{f}_{k}-\Sigma_{j}\
Y[j,k]\ \vec{e}_{j}.$

Thus there is a well defined mapping

$\begin{array}[]{l}F:C_{d}(T_{0};Z)\rightarrow\Pi(B^{d}(X;\mathbb{Z})),\ \ \ \
\vec{f}_{k}\mapsto 1\cdot\vec{f}_{k}-\Sigma_{j}\ Y[j,k]\
\vec{e}_{j}.\end{array}$

Now let $a$ be any element of $\Pi(B^{1}(X;Z))$ and note that

$<a,Z[j]>=0\ as\ Z[j]\in Z_{1}(X;\mathbb{Z})\ and\
\Pi(B^{1}(X;\mathbb{R}))^{\perp}=Z_{1}(G;\mathbb{R}).$

Say $a=(\ \Sigma_{j}\ x_{j}\ \vec{e}_{j}\ )+(\ \Sigma_{k}\ y_{k}\ \vec{f}_{k}\
).$ Then the difference $Diff=a-(\ \Sigma_{k}\ y_{k}\ F(\vec{f}_{k}\ )\ )$
lies in $\Pi(B^{d}(X;\mathbb{Z}))$ and is supported in $G-T_{0}$. But then
$0=<Z[e_{j}],Diff>=x_{j}\ for\ each\ j=1,\cdots,|E(G-T_{0})|$ proving that
$Diff=0$. Hence, the integral chains $F(\vec{f}_{k})$ generate
$\Pi(B^{d}(X;\mathbb{Z}))$ They are independent since projecting to
$C_{1}(T_{0};\mathbb{Z})$ each goes to $1\cdot\vec{f}_{k}$, part of the basis
of $C_{1}(T_{0};Z)$.

Hence, the lemma is proved.

##  7 Flux and Eigenvalue Inequalities

For the Kirchoff Laplacian $\Delta(G)$ of a graph $G$ there is the
foundational Rayleigh-Ritz inequality providing an upper estimate of the first
positive eigenvalue.111An inequality giving a lower estimate on the
eigenvalues is due to Cheeger for Riemannian manifolds [14]. Bounds either way
in the setting of graph theory are often referred to as Cheeger type
inequalities inspired by his methods, i.e., see [15, 16].  Following the
principle that the mesh Laplacian is a natural generalization of the Kirchoff
Laplacian, it is natural to discuss an extension of such inequalities to the
mesh context. The flux of the of the graph $G$ is a measured by the
eigenvalues of the Kirchoff Laplacian.

The mesh Laplacian $\Delta(G,T_{0})=D\cdot D^{\star}$ is represented by
$Y\cdot Y^{t}$ which is real symmetric with non-negative eigenvalues. Let
$\Lambda$ be the smallest positive eigenvalue of $Y\cdot Y^{t}$, equivalently
of $\Delta(G,T_{0})$. This $\Lambda$ is also the smallest positive eigenvalue
of $Y^{t}\cdot Y$ which represents the reduced mesh matrix
$Mesh^{\\#}(G,T_{0})$.

By the standard Rayleigh-Ritz theorem, there is the associated equality giving
upper estimates for $\Lambda$. Namely,

$\Lambda=min_{f\neq 0,\ \ f\in[kernel\
C_{1}(T_{0};\mathbb{R})\stackrel{{\scriptstyle
D^{\star}}}{{\rightarrow}}C_{1}(G-T_{0};\mathbb{R})]^{\perp}}\ \
\frac{<D^{\star}(f),D^{\star}(f)>}{<f,f>}$

where $[kernel\ C_{1}(T_{0};\mathbb{R})\stackrel{{\scriptstyle
D^{\star}}}{{\rightarrow}}C_{1}(G-T_{0};\mathbb{R})]^{\perp}$ is the
orthogonal complement of this kernel in $C_{1}(T_{0};\mathbb{R})$ endowed with
the standard cellular inner product. Here $<D^{\star}(f),D^{\star}(f)>\newline
=<f,D\cdot D^{\star}(f)>=<f,\Delta(G,T_{0})(f)>$. Hence, the kernel consists
precisely of the eigenvectors of $\Delta(G,t_{0})$ with eigenvalue zero.

One may regard $\Lambda$ as a measure of the flux of $\Delta(G,T_{0})$ through
$G-T_{0}$ from $T_{0}$ to $T_{0}$.

Let the edges in $E(G-T_{0})$ be enumerated and directed as before. Then there
are three different types of directed edges. Firstly
$\vec{e}_{j}[P_{j},Q_{j}]$ may be a loop, i.e., $P_{j}=Q_{j}$. Let these be
called type 1 edges. Secondly, the edge $\vec{e}_{j}$ may have distinct end
points, but these end points $P_{j},Q_{j}$ [ which lie in $V(T_{0})=V(G)$] are
adjacent in the subgraph $T_{0}$. Call these type 2 edges. Note that in the
first case $D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])=0$ and in the second case
$D(1\cdot\vec{e}_{j}[P_{j},Q_{j}])$ is the unique directed edge in $T_{0}$
from $Q_{j}$ to $P_{j}$. Finally and thirdly, the directed edge
$\vec{e}_{j}[P_{j},Q_{j}]$ is called of type 3, if it has a directed simple
path in $T_{0}$ from $Q_{j}$ to $P_{j}$ of length $\geq 2$.

In the third type 3 case, $\vec{e}_{j}[P_{j},Q_{j}]$, $P_{j},Q_{j}$ are
vertices of the spanning tree $T_{0}$ so by $P_{j}\neq Q_{j}$ there is a
unique directed simple path from $Q_{j}$ to $P_{j}$ in the spanning tree
$T_{0}$, given by distinct vertices say
$Q_{j}=R_{j,1},R_{j,2},\cdots,R_{j,n[j]}=P_{j}$ with $R_{j,t}\sim R_{j,t+1}$
[adjacent] and the edge $[R_{j,t}\rightarrow R_{j,t+1}]$ chosen in $T_{0}$.
Here $n[j]\geq 2$, so one has two distinct well defined directed edges,
initial and final directed inward into $T_{0}$ given by

$[Q_{j}\rightarrow R_{j,2}]=[R_{j,1}\rightarrow R_{j,2}]\in E(T_{0})\ \ and\ \
[R_{j,n[j]}\rightarrow R_{j,n[j]-1}]=[P_{j}\rightarrow R_{j,n[j]-1}]\in
E(T_{0})$

For a directed edge $\vec{e}_{j}[P_{j},Q_{j}]\in E(G-T_{0})$ of type 3, let
these directed two directed edges be denoted by
$F_{1}(\vec{e}_{j}[P_{j},Q_{j}])=[Q_{j}\rightarrow R_{j,2}]\in E(T_{0})$, the
initial edge of $D(\vec{e}_{j}[P_{j},Q_{j}])$, and
$F_{2}(\vec{e}_{j}[P_{j},Q_{j}])=[P_{j}\rightarrow R_{j,n[j]-1}]\in E(T_{0})$,
the final edge of $D(\vec{e}_{j}[P_{j},Q_{j}])$ both directed inward to
$T_{0}$.

Let $\vec{e}_{j}[P_{j},Q_{j}]$ range over all type 3 directed edges of
$E(G-T_{0})$, set $X$ to be the set of all these inward directed edges so
obtained:

$X=\\{F_{1}(\vec{e}_{j}[P_{j},Q_{j}])\\}\cup\\{F_{2}(\vec{e}_{j}[P_{j},Q_{j}])\\}.$

Naturally a given such directed edge may arise in several ways; multiplicities
are neglected in this representation. The construction provides a set of
distinct type 3 inward directed edges of $G$.

Now form a graph $W$ with vertices the elements of the set $X$ of the type 3
edges. Declare that two distinct vertices, say with representatives
$[F_{r}(\vec{e}_{s}[P_{s},Q_{s}])],[F_{t}(\vec{e}_{u}[P_{u},Q_{u}])]$, having
an edge in the graph $W$ between them for each type 3 directed edge
$\vec{e}_{j}[P_{j},Q_{j}]$ with ingoing edges equal to these two, i.e.,
$\\{F_{1}(\vec{e}_{j}[P_{j},Q_{j}]),F_{2}(\vec{e}_{j}[P_{j},Q_{j}])\\}\newline
=\\{F_{r}(\vec{e}_{s}[P_{s},Q_{s}]),F_{t}(\vec{e}_{u}[P_{u},Q_{u}])\\}$.

###### Theorem 7.1

Let $\lambda$ be the smallest positive eigenvalue of the graph Laplacian
$\Delta(W)$ of the graph $W$ derived from $G$. Let $\Lambda$ be the smallest
positive eigenvalue of the mesh Laplacian $\Delta(G,T-0)$. Then the following
inequality holds:

$\Lambda\leq\lambda$

By the standard methods, [15, 16] $\lambda$ has upper estimates of the Cheeger
type. These then imply upper estimates for $\Lambda$.

In detail, let the graph $W$ have M distinct connected components, say

$W=\sqcup_{k=1}^{M}\ W[k]\ and\ correspondingly\ vertex\ decomposition\
X=V(W)=\sqcup_{k=1}^{M}\ X[k].$

For each $k$ make a choice of proper subset $C[k]\subset X[k]$ and denote the
complement in $X[k]$ by $D[k]=X[k]-C[k]$, then

$\begin{array}[]{l}\Lambda/2\leq\lambda/2\\\ \leq
min\\{\frac{\\#\vec{e}_{j}[P_{j},Q_{j}]\ of\ type\ 3\ with\
F_{1}(\vec{e}_{j}[P_{j},Q_{j}])\in C[k]\ and\
F_{2}(\vec{e}_{j}[P_{j},Q_{j}])\in D[k]\ or\ visa\
versa}{min(|A[k]|,|B[k])},k=1,\cdots,M\\}\end{array}$

Proof: Let $j:R[X]\subset C_{1}(T_{0};\mathbb{R})$ denote the inclusion of the
real sums of multiples of the [inward directed] edges in $X$. Let
$\overline{D^{\star}}=D^{\star}\cdot j:R[X]\rightarrow
C_{1}(G-T_{0};\mathbb{R})$ with adjoint $(\overline{D^{\star}})^{\star}$. Let
$\mu$ be the smallest positive eigenvalue of the composite
$\overline{\Delta}=(\overline{D^{\star}})^{\star}\cdot\overline{D^{\star}}$.
Tautologously, one has the inequality [restricting the minimum over fewer
cases]:

$\Lambda\leq min_{g\neq 0,\ \ g\in R[X]\cap[kernel\
C_{1}(T_{0};\mathbb{R})\stackrel{{\scriptstyle
D^{\star}}}{{\rightarrow}}C_{1}(G-T_{0};\mathbb{R})]^{\perp}}\ \
\frac{<D^{\star}(g),D^{\star}(g)>}{<g,g>}=\mu$

Now here $R[X]\cap[kernel\ C_{1}(T_{0};\mathbb{R})\stackrel{{\scriptstyle
D^{\star}}}{{\rightarrow}}C_{1}(G-T_{0};\mathbb{R})]$ consists of the sums
$Sum=\Sigma_{x\in X}\ A[x]\ x$ for which $D^{\star}(Sum)=0$. That is, for each
$\vec{e}_{j}[P_{j},Q_{j}]$ the equation
$<D(\vec{e}_{j}[P_{j},Q_{j}]),Sum>=0$ holds. But
$<D(\vec{e}_{j}[P_{j},Q_{j}]),Sum>=<F_{2}(\vec{e}_{j}[P_{j},Q_{j}])-F_{1}(\vec{e}_{j}[P_{j},Q_{j}]),Sum>=A[F_{2}(\vec{e}_{j}[P_{j},Q_{j}])]-A[F_{1}(\vec{e}_{j}[P_{j},Q_{j}])]$.
This means that if the vertices in $W$, $x,y$ are adjacent, then $A[x]=A[y]$.
Consequently, $R[X]\cap[kernel\ C_{1}(T_{0};\mathbb{R})\stackrel{{\scriptstyle
D^{\star}}}{{\rightarrow}}C_{1}(G-T_{0};\mathbb{R})]$ consists of the sum of
multiples of the entries one for each component

$S[k]=(\ \Sigma_{x\in W[k]}\ 1\cdot x\ )\in C_{1}(T_{0};\mathbb{R}),\
k=1,\cdots,M$

and the mapping
$(\hat{D^{\star}})^{\star}:C_{1}(G-T_{0};\mathbb{R})\rightarrow\\{\Sigma_{x\in
X}\ A[x]\ x\\}$ sends
$1\cdot\vec{e}_{j}(P_{j},Q_{j})=F_{1}(\vec{e}_{j}[P_{j},Q_{j}])-F_{2}(\vec{e}_{j}[P_{j},Q_{j}])$.

That is, under this identification, $(\overline{D}^{\star})^{\star}$ is
identified with $\partial:C_{1}(W;\mathbb{R})\rightarrow C_{0}(W;\mathbb{R})$
and $\overline{D}^{\star}$ with
$\partial^{\star}:C_{0}(W;\mathbb{R})\rightarrow C_{1}(W;\mathbb{R})$ and the
kernel of $\partial^{\star}$ with the sums of multiples of the $S[k]$’s. The
orthogonal complement of this kernel is identified with the span of the
eigenspaces with positive eigenvalues. In particular, $\mu=\lambda$ is given
as the least positive eigenvalue of the graph Laplacian of the graph $W$ in
the above inequality.

The standard Cheeger inequality [15, 16] now applies to the graph $W$ to give
the above estimate.

##  8 Appendix; A Correction to the statement of theorem 7.1 of [8] and
extension of theorem 2.2 to the higher dimensional context :

The paper [8] considers generalizations of the mesh matrix to the context of
$d$-dimensional finite CW-complexes $X$. The theorem 7.1 of [8], once stated
correctly, is a generalization of lemma 3.1. Once lemma 3.1 is generalized,
the methods of this paper combined with [8] also give a generalization of
theorem 2.2 above. This is carried out in this section. In the context of the
higher dimensional Kirchoff Laplacian for CW-complexes some relevant papers
are [1, 3, 4, 2, 9, 10, 11, 17, 18, 19, 24, 25, 29] and others.

Let $X$ be a finite d-dimensional CW-complex. Let $S_{d}$ be the $d$-cells of
$X$ with chosen orientations, i.e., $X$ is obtained from the $d-1$ skeleton of
$X$, i.e., $X^{d-1}$, by attaching the oriented $d$-cells of $S_{d}$. For
$V\subset S_{d}$ define the subcomplex

$X_{V}=X^{d-1}\cup V\subset X^{d-1}\cup S_{d}=X.$

For a finite cell complex, say $X$, let $t_{d}(X)$ denote the order of the
torsion subgroup of the $(d-1)^{th}$ integral homology of $X$,
$H_{d-1}(X;\mathbb{Z})$.

In this higher dimensional context a subset $V\subset S_{d}$ is called a
spanning forest of $X$ if the composition

$C_{d}(X_{V};\mathbb{R})\stackrel{{\scriptstyle\partial_{d}}}{{\rightarrow}}B_{d-1}(X_{V};\mathbb{R})\subset
B_{d-1}(X;\mathbb{R})$

is an isomorphism. In the case that $G$ is a graph and the graph $G$ is
connected, the spanning forests in the above sense are exactly the spanning
trees of the graph $G$. In the case that a graph $G$ has $K$ connected
components, say $G=\sqcup_{j=1}^{K}\ G[j]$, a spanning forest is a choice for
each connected component $G[j]$ of a spanning tree $T[j]$ of $G[j]$. It is
shown in [8] that all $d$-dimensional CW-complexes have spanning forests.

Now the integral $d$-cycles $Z_{d}(X;\mathbb{Z})$ is a free abelian group, so
one may pick a integral basis, say $\\{z_{j}\\}$. Via the natural pairing

$Z_{d}(X;\mathbb{Z})\times Z_{d}(X;\mathbb{Z})\subset
C_{d}(X;\mathbb{Z})\times
C_{d}(X;\mathbb{Z})\stackrel{{\scriptstyle<.,.>}}{{\rightarrow}}\mathbb{Z},$

one may form the mesh matrix for this integral choice of basis

$Mesh(X;\\{z_{r}\\})=\\{<z_{a},z_{b}>\\}$

On the other hand, if one chooses a spanning forest, say $V_{0}$, of $X$, for
each $e$ in $S_{d}-V_{0}$, the boundary $\partial_{d}(e)$ is uniquely
expressed as $\partial_{d}(D(e))$ for a unique $d$-chain $D(e)\in
C_{d}(X_{V_{0}};\mathbb{R})$. In particular, for each $e\in S_{d}-V_{0}$ there
the unique $d$-cycle

$z(e)=1\cdot e-D(e)\in Z_{d}(X;\mathbb{R})$

with $D(e)$ supported exactly in $X_{V_{0}}$. Since
$Z_{d}(X_{V_{0}};\mathbb{R})=0$ by $V_{0}$ a spanning tree, one sees that
these $\\{z(e)\ |\ \ e\in S_{d}-V_{0}\\}$ form a “geometric” basis for
$Z_{d}(X;\mathbb{R})$ with associated mesh matrix

$Mesh(X;\\{z(e)\ |\ e\in S_{d}-V_{0}\\},geometric)$

Note that $z(e)$ is supported in $X_{e}=X^{d-1}\cup e$ for $e\in S_{d}-V_{0}$.
Let $N=|S_{d}-V_{0}|$.

Let the $d$-cells in $S_{d}-V_{0}$, be enumerated via $e_{1},\cdots,e_{N}$.
Consider a choice of $j\times j$ diagonal minor, say
$Mesh(\\{z(e)\\},geometric)_{k_{1},k_{2},\cdots,k_{j}}$ with $1\leq
k_{1}<k_{2}<\cdots<k_{j}\leq N$ by picking these $j$ rows and columns. The
entries of this minor all are of the form $<z(e_{k_{a}}),z(e_{k_{b}})>$ with
each $z(e_{k_{a}})\in
Z_{d}(X_{V_{0}\cup\\{e_{k_{1}},e_{k_{2}},\cdots,e_{k_{j}}\\}});\mathbb{R})$
for $1\leq 1\leq j$. Consequently, as in §3,

$det(Mesh(\\{X(e)\\}),geometric)_{k_{1},k_{,}\cdots,k_{j}})=det(Mesh(X_{V_{0}\cup\\{e_{k_{1}},\cdots,e_{k_{j}}\\}}),geometric).$

Consequently, modeled on the proof of lemma 3.1, one has for the geometric
basis the equality

$det(X\cdot Id-Mesh(X;\\{z(e)\ |\ in\
S_{d}-V_{0}\\},geometric)=X^{N}+\Sigma_{j=1}^{N}\ (-1)^{j}\ b_{j}\ X^{N-j}$

with $b_{j}=\Sigma_{1\leq k_{1}<k_{2},\cdots,k_{j}\leq N}\ \
det(Mesh(X_{V_{0}\cup\\{e_{k_{1}},\cdots,{e_{k_{j}}\\}}})),geometric))$. Here
the choice of $k_{1},k_{2},\cdots,k_{j}$ in $S_{d}-V_{0}$ may be recorded as a
choice of subset $U=\\{k_{1},\cdots,k_{j}\\}\subset S_{d}-V_{0}$ with $|U|=j$.

In these terms the slightly corrected version of theorem 7.1 of [8] is: [It is
the high dimensional version of lemma 3.1.]

###### Theorem 8.1

Let $V_{0}\subset S_{d}$ be a $d$-dimensional spanning forest of a
$d$-dimensional CW-complex $X$ with oriented $d$-cells $S_{d}$, then
$\sigma_{j}(X;V_{0})=$ the coefficient of $(-1)^{j}\ T^{N-j}$ in the
characteristic polynomial

$det(Mesh(X,\\{z(e)\ |\ e\in(S_{d}-V_{0})\\}),geometric\ basis)$

is given by

$\sigma_{j}(X;V_{0})=\Sigma_{U\subset(S_{d}-V_{0})\ with\ |U|=j}\ \ (\
\Sigma_{V\ a\ spanning\ forest\ of\ X_{V_{0}\cup U}}\
\left(\frac{t_{d-1}(X_{V})}{t_{d-1}(V_{0})}\right)^{2}\ )$

For $d=1$, there is no torsion in the homologies, so sum is over entries all
equal to $+1$. So, this is the high dimensional version of lemma 3.1. The
proof is a consequence of the above argument and the following equality: For
$Y$ a d-dimensional finite CW-complex, and a choice of spanning forest
$V_{0}\subset S_{d}$ for $Y$.

$det(Mesh(Y,\\{z(e)\\},geometric)=\Sigma_{V\ a\ spanning\ forest\ of\ Y}\
\left(\frac{t_{d-1}(Y_{V})}{t_{d-1}(Y_{V_{0}})}\right)^{2}.\ \ (\star)$

applied to the various $Y=X_{V_{0}\cup U}$.

This last is the analog of Trent’s theorem 2.1 above. In the paper [8] theorem
2.1 asserts the evaluation of the determinant of the mesh matrix for the
integral basis $\\{z_{r}\\}$ as:

$det(Mesh(X;\\{z_{r}\\}))=\Sigma_{V\ a\ spanning\ forest\ of\ X}\
\left(\frac{t_{d-1}(X_{V})}{t_{d-1}(X)}\right)^{2}\ \ (\star\ \star)$

This equality $(\star\ \star)$ is to be modified to get $(\star)$ which
utilizes the geometric basis rather than the geometric basis.

Here under the mapping $Z_{d}(X;\mathbb{R})\subset
C_{d}(X;\mathbb{R})\rightarrow C_{d}(X,X_{V_{0}};\mathbb{R})$ [which by
$V_{0}$ a spanning forest is an isomorphism] the lattice of the geometric
basis $Z\\{z(e)\ |\ e\in S_{d}-V_{0}\\}$ has image equal to the image of the
integral classes $C_{d}(X;\mathbb{Z})$, [as $z(e)=1\cdot e+D(e)$ with $D[e]\in
C_{d}(X_{V_{0}};\mathbb{R})$]; and the lattice of the integral basis for
$Z_{d}(X;\mathbb{Z})$ has image equal of course to the image of the integral
basis of $Z_{d}(X;\mathbb{Z})$. As $V_{0}$ is a spanning forest, these images
provide two real bases for the $C_{d}(X,X_{V_{0}};\mathbb{R})$ with one
lattice inside the other. Hence, the change of basis from integral to
geometric has determinant equal to the order of the finite abelian group:

$\frac{C_{d}(X,X_{V_{0}};\mathbb{Z})}{image\ Z_{d}(X;\mathbb{Z})}.$

The order of this finite abelian group is identified on page 14 of [8] as

$|\frac{C_{d}(X,X_{V_{0}};\mathbb{Z})}{Z_{d}(X;\mathbb{Z})}|=\frac{t_{d-1}(X_{V_{0}})}{t_{d-1}(X)}$

The respective determinants of mesh matrices are related by the square of this
quotient. This relation demonstrates that $(\star\ \star)$ implies $(\star)$
so the above forms an independent proof of theorem 8.1.

Now as above in the present paper, the geometric basis is of the form:
$z(e_{j})=1\cdot e_{j}+D(e_{j})\in Z_{d}(X;\mathbb{R})$ for $e_{j}\in
S_{d}-V_{0}$ with $D(e_{j})$ supported in $X_{V_{0}}$. This implies

$<z(e_{j}),z(e_{k})>=Id_{j,k}+<D(e_{j}),D(e_{k})>.$

That is, the geometric mesh matrix is of the form,

$Mesh(X;\\{z(e_{j})\\},geometric)=Id+Mesh^{\\#}(X;\\{z(e_{j})\\},geometric)$

with the reduced mesh matrix $Mesh^{\\#}(X;\\{z(e_{j})\\},geometric)$ defined
by
$\\{<D(e_{j}),D(e_{k})>\\}$. Hence, the counting argument given for proving
theorem 2.2 of this paper applies without essential change to yield a higher
dimensional generalization of this paper’s theorem 2.2. Namely:

###### Theorem 8.2

$\begin{array}[]{l}det((U+1)\ Id-Mesh(X;\\{z(e_{a})\\},geometric))\\\ =det(U\
Id-Mesh^{\\#}(X;\\{z(e_{a})\\},geometric)=U^{N}+\Sigma_{j=1}^{N}\ (-1)^{j}\
c_{j}\ U^{N-j}\\\ with\\\ c_{j}=\Sigma_{U\ a\ spanning\ forest\ of\ X\ with\
|U\cap(S_{d}-V_{0})|=j}\
\left(\frac{t_{d-1}(X_{U})}{t_{d-1}(X_{V_{0}})}\right)^{2}\end{array}$

## References

  * [1] R. M. Adin, Counting colorful multi-dimensional trees, Combinatorica 12 (1992), no. 3, pp. 247-260.
  * [2] F. Aliniaeifard, V. Wang, S. Van Willigenburg, Deletion-Contraction for a Unified Laplacian and Applications, https://arxiv.org/abs/2110.13949, to appear.
  * [3] O. Bernardi, C. J. Klivans, Directed rooted forests in higher dimension, Electron. J. Combin. 23 (2016), no. 4, 20 pp.
  * [4] E. D. Bolker, Simplicial goemetry and transportation polytopes, Trrans. Amere. Math. Soc, 217 (1976) , pp. 121-142
  * [5] P. R. Bryant, Graph theory applied to electrical networks in F. Harary (ed.), Graph theory and theoretical physics 1967, Academic Press, N.Y., pp. 111-137.
  * [6] Y. Burman, B. Shapiro, Around matrix-tree theorem. Math. Res. Lett. 13 (2006), no. 5-6, pp. 761-774.
  * [7] Y. Burman, A. Ploskonosov, A. Trofimova, Matrix-tree theorems and discrete path integration. Linear Algebra Appl. 466 (2015), pp. 64-82.
  * [8] S. Cappell, E. Miller, Enumerative Combinatorics of Simplicial and Cell Complexes: Kirchoff and Trent Type Theorems, Discrete and Combinatorial Geometry (2019), vol 61, 1-41.
  * [9] M. Catanzaro, V. Chernyak, and J. Klein, On Kirchhoff’s theorems with coefficients in a line bundle, Homology, Homotopy and Applications, vol. 15 no. 2 (2013), 267 – 280.
  * [10] M. Catanzaro, V. Chernyak, and J. Klein, Kirchhoff’s Theorems in Higher Dimensions and Reidemeister Torsion, Homology Homotopy Appl. (2015), vol 17, # 1, 165-189.
  * [11] M. J. Catanzaro,V. Y. Chernyak, and J. R. Klein, A higher Boltzmann Distribution, J. Appl. Comp. Topol. 1, (2017), 215-240.
  * [12] S. Chaiken, A Combinatorial Proof of the All Minors Matrix Tree Theorem, SIAM J. Alg. Disc. Maht, (1982) , vol 3, No. 3, pp. 319-339.
  * [13] S. Chaiken and D. Kleitman, Matrix tree theorems, J. of Combinatorial Theory, Series A, 24 (1978), pp. 377-381.
  * [14] Cheeger, Jeff, A lower bound for the smallest eigenvalue of the Laplacian, Problems in analysis (Sympos. in honor of Salomon Bochner, Princeton Univ., Princeton, N.J., 1969), pp. 195–199. Princeton Univ. Press, Princeton, N.J., 1970.
  * [15] F. Chung, Spectral Graph Theory, American Mathematical Society, Regional Conference Series in Mathematics, (1997) # 92.
  * [16] F. Chung, Four Proofs of the Cheeger Inequality and graph partition algorithms, Proceeding of ICCM (2007).
  * [17] A. Duval, C. Klivans, and J. Martin, Simplicial Matrix Tree Theorems, Trans. Amer. Math. Soc., 361 (2009), pp. 6073-6114.
  * [18] A. Duval, C. Klivans, J. Martin, Simplicial and cellular trees. Recent trends in combinatorics, IMA Vol. Math. Appl., 159 (2016), pp. 713-752, Springer Press.
  * [19] G. Kalai, Enumeration of $Q$-acyclic Simplicial Complexes, Israel J. Math., vol 45 (1983), pp. 337-351.
  * [20] R. Kenyon, The asymptotic determinant of the discrete Laplacian, Acta Math., 185 (2000), pp. 239-286.
  * [21] Kenyon, R. The Laplacian and Dirac operators on critical planar graphs, Invent. Math. 150 (2002), no. 2, pp. 409-439.
  * [22] R. Kenyon, Spanning forests and the vector bundle laplacian, The Annals of Probability, 39 no. 5 (2011), pp. 1983-2017.
  * [23] G. Kirchhoff, Uber die Aufls̈ung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strome gerfuhrt wird , Poggendorf’s Ann. Phys. Chem., vol. 72 (1847), pp. 497-508; English translation, IRE Trans. Circuit Theory, vol. 5 (1958), pp. 4-8.
  * [24] R. Lyons, Random Complexes and $L^{2}$-Betti numbers,, J. Topol. Anal. vol. 1 (2009), pp. 153-175.
  * [25] , R. Lyons, and Y.Peres, Probability on trees and networks. Cambridge Series in Statistical and Probabilistic Mathematics, 42. Cambridge University Press, New York, 2016.
  * [26] G. Masbaum, Gregor, A. Vaintrob, A new matrix-tree theorem. Int. Math. Res. Not. 27 (2002), pp. 1397-1426.
  * [27] S. Maurer, Matrix Generalizations of Some Theorems on Trees, Cycles, and Cocycles in Graphs, SIAM J. Math., vol 30 (1976), # 1, 143-148.
  * [28] J. W. Moon, Counting Labeled Trees, Canadian Mathematical Congress, From lectures delivered to the Twelfth Biennial Seminar of the Canadian Mathematical Congress (Vancouver, 1969). Canadian Mathematical Monographs, No. 1 Canadian Mathematical Congress, Montreal, Que. 1970.
  * [29] A. Peterson, Enumerating Spanning Trees in Simplicial Complexes, Masters Thesis Uppsala University, 2009.
  * [30] H. M. Trent, A Note on the Enumeration and Listing of All Possible Trees in a Connected Linear Graph, Proc. National Acad. Sci,(1954) vol 40 , # 10, 1004-1007.
  * [31] H. Trent, A note on the enumeration and listing of all maximal trees of a connected linear graph , Proc. Nat. Acad. Sci. U.S.A., 40 (1954), pp. 1004-1007.
  * [32] W. Tutte, On the spanning trees of self-dual maps, in Second International Conference on Combinatorial Mathematics (A. Gewirtz andL/V. Quintas, eds.), The New York Academy of Science, 1979, pp. 540-548.

Sylvain E. Cappell<EMAIL_ADDRESS>Courant Institute of Mathematical
Sciences, NYU.

Edward Y. Miller<EMAIL_ADDRESS>, Courant Institute of Mathematical
Sciences, NYU.