% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.50}{21(1)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Logarithmic Tree-Numbers\\ for Acyclic Complexes}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Hyuk Kim\thanks{Partially supported by the Korea Research Foundation (KRF) grant funded by the Korea government (MEST)(No. 2011-0011223).}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Seoul National University\\[-0.8ex] 
\small Seoul, Republic of Korea\\
\small\tt hyukkim@snu.ac.kr\\
\and
Woong Kook\thanks{Corresponding author: partially supported by a grant from the Simons Foundation (No. 245994).}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Seoul National University\\[-0.8ex]
\small Seoul, Republic of Korea\\
\small\tt woongkook@snu.ac.kr
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{May 22, 2013}{Feb 26, 2014}{Mar 10, 2014}\\
\small Mathematics Subject Classifications: 05E99, 05C05}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  For a $d$-dimensional cell complex $\Gamma$ with $\tilde{H}_{i}(\Gamma)=0$ for $-1\leq i < d$, an $i$-dimensional tree is a non-empty collection $B$ of $i$-dimensional cells in $\Gamma$ such that $\tilde{H}_{i}(B\cup \Gamma^{(i-1)})=0$ and $w(B):= |\tilde{H}_{i-1}(B\cup \Gamma^{(i-1)})|$ is finite, where $\Gamma^{(i)}$ is the $i$-skeleton of $\Gamma$. The $i$-th tree-number is defined $k_{i}:=\sum_{B}w(B)^{2}$, where the sum is over all $i$-dimensional trees. In this paper, we will show that if $\Gamma$ is acyclic and $k_{i}>0$ for $-1\leq i \leq d$, then $k_{i}$ and the combinatorial Laplace operators $\Delta_{i}$  are related by  $\sum_{i=-1}^{d}\omega_{i}\,x^{i+1}=(1+x)^{2}\sum_{i=0}^{d-1}\kappa_{i} x^{i}$, where $\omega_{i}=\log \det \Delta_{i}$ and $\kappa_{i}=\log k_{i}$.  We will discuss various consequences and applications of this equation.
  % keywords are optional

%\bigskip\noindent \textbf{Keywords:} acyclic complexes; high-dimensional trees; combinatorial Laplacians
\end{abstract}
%
%
%
%
%
\section{Introduction}
In this paper, we will extend Temperley's tree-number formula for finite graphs \cite{Te}  to a class of cell complexes, called $\gamma$-complexes, and show applications to various acyclic complexes. 

As the main object of study in this paper, we define a $\gamma$-{\it complex} to be a non-empty finite cell complex $\Gamma$ whose integral cellular chain complex $\{C_{i},\partial_{i}\}$ with $C_{-1}=\mathbb{Z}$ satisfies the following conditions:
\begin{enumerate}
\item[($\gamma$1)] $\partial_{i}\not=0$ for $0\leq i\leq\dim\Gamma$, and
\item[($\gamma$2)] the reduced integral homology $\tilde{H}_{i}(\Gamma)=0$ for $i< \dim\Gamma$.
\end{enumerate}
This definition is intended to be a generalization of connected finite graphs. Other examples of $\gamma$-complexes are matroid complexes, standard simplexes, and cubical complexes \cite{DKM} with the latter two being acyclic. Note that a $\gamma$-complex is a special case of APC (acyclic in positive codimension) complexes in the terminology of \cite{DKM}. 

We define high-dimensional spanning trees for a $\gamma$-complex extending the ideas in \cite{Ad}.  Given a $\gamma$-complex $\Gamma$, let $\Gamma_{i}$ be the set of all $i$-dimensional cells, and $\Gamma^{(i)}$ the $i$-skeleton of $\Gamma$. Given a subset $S\subset \Gamma_{i}$, define $\Gamma_{S}=S\cup\Gamma^{(i-1)}$ as a subcomplex of $\Gamma$. An $i$-{\it dimensional spanning tree} of $\Gamma$ (or simply, an $i$-{\it tree}) is a non-empty subset $B\subset\Gamma_{i}$ such that $\tilde{H}_{i}(\Gamma_{B})=0$ and $w(B):=|\tilde{H}_{i-1}(\Gamma_{B})|$ is finite.
Define the $i$-{\it th tree-number} of $\Gamma$ by 
$$k_{i}(\Gamma)=k_{i}=\sum_{B}w(B)^{2}\, ,$$ 
where the sum is over all $i$-trees in $\Gamma$.  We will see that $k_{i}>0$ for all $-1\leq i \leq \dim\Gamma$ where we define $k_{-1}=1$. If $\Gamma$ is a graph, then $k_{0}$ is the number of vertices and $k_{1}$ is the number of spanning trees in $\Gamma$. 

An important method for computing the tree-numbers for $\Gamma$ is given by the combinatorial Laplacians $\Delta_{i}$ (\cite{Ad}, \cite{DKM}, and \cite{Te}). For example, let $\Delta_{0}=L+J$, where $L$ is the Laplacian matrix of a finite graph $G$ of order $n$, and $J$ is the all 1's matrix. Temperley \cite{Te} showed that $\det\Delta_{0}=n^{2}k_{1}$ for $G$ (refer to Theorem \ref{TemperleyFormula}). This method is more efficient than the matrix-tree theorem for certain graphs. Indeed, for $\Gamma=K_{n}$ the complete graph on $n$ vertices, we have $\Delta_{0}=nI$ and  $\det\Delta_{0}=n^{n}$, from which the Cayley's Theorem $k_{1}(K_{n})=n^{n-2}$ is immediate. 

We will show that Temperley's formula can be extended to any $\gamma$-complex $\Gamma$ (refer to Proposition \ref{determinant}). Also, if $\Gamma$ is acyclic of dimension $d$, then each $\Delta_{i}$ is positive-definite, and the following polynomials are well-defined: $$D(x)=\sum_{i=-1}^{d}(\log \det\Delta_{i})x^{i+1} \mbox{ and }
K(x)=\sum_{i=0}^{d-1}(\log k_{i})x^{i}\, .$$
The main result of the paper is  
\begin{equation}\label{mainintro}
D(x)=(1+x)^{2}K(x)\, .
\end{equation}
A refinement of this equation and its applicability to matroid complexes will be discussed through a simple example. (See Section 5.)

This paper is organized as follows. Section 2 is a review of useful facts from matrix theory and combinatorial Laplacians for $\gamma$-complexes. It also provides a proof of Temperley's tree-number formula. In Section 3, we will describe high-dimensional spanning trees for a $\gamma$-complex via the boundary operators of its chain complex. In Section 4, we will prove the main results of the paper which consist of a generalization of Temperley's tree-number formula and a logarithmic version (\ref{mainintro}) of this result for acyclic $\gamma$-complexes. In Section 5, we will discuss applications of (\ref{mainintro}) to standard simplexes \cite{Ka}, the cubical complexes \cite{DKM}, and an example of graphic matroid complex.
%
%
%
%
%
\section{Preliminaries}
\subsection{Lemmas from Matrix Theory} We will review several important facts about symmetric matrices. For definitions and basic facts from matrix theory, one may refer to \cite{Ga}.  All matrices are assumed to have real entries. For a square matrix $M$, let $P_{M}$ denote the multiset of all non-zero eigenvalues of $M$, and let $\pi_{M}=\prod_{\lambda\in P_{M}}\lambda$\,.  The following two lemmas and their proofs appear in \cite{Ad}. We will sketch the proofs here. 
%
%
\begin{lemma}\label{matrixtheory1}
Let $A$ and $B$ be $n\times n$ symmetric matrices such that $AB=BA=0$.   Then, $P_{A+B}=P_{A}\cup P_{B}$ as a multiset. In particular, if $A+B$ is non-singular,  
\begin{equation}\label{detLap}
\det(A+B)=\pi_{A}\pi_{B}\, .
\end{equation}
\end{lemma}
\begin{proof}
Since $A$ and $B$ are symmetric and they commute, they are simultaneously diagonalizable. For each $i\in[1,n]$, let $\lambda_{i}$ and $\mu_{i}$ be the eigenvalues of $A$ and $B$, respectively,  so that the collection $\{\lambda_{i}+\mu_{i}\, |\, i\in[1,n]\}$ is the multiset of all eigenvalues of $A+B$. Since $AB=0$, we have either $\lambda_{i}=0$ or $\mu_{i}=0$ for each $i$. Therefore $\alpha=\lambda_{i}+\mu_{i}\in P_{A+B}$ if and only if $\alpha=\lambda_{i}\in P_{A}$ or $\alpha=\mu_{i}\in P_{B}$.
\end{proof}
%
\begin{lemma}\label{matrixtheory2}
Let $M$ be a rectangular matrix of rank $r$ $(r>0)$. Let $\mathcal{B}(M)$ be the collection of all non-singular $r\!\times\! r$ submatrices of $M$. If $A=MM^{t}$, or $M^{t}M$, then  
\begin{equation}\label{BinetCauchy}
\pi_{A}=\sum_{B\in \mathcal{B}(M)}(\det B)^{2}\, .
\end{equation}
\end{lemma}
\begin{proof} This result follows from Binet-Cauchy theorem and the fact that the product of all non-zero eigenvalues of a {\it diagonalizable} matrix of rank $r$ equals the sum of all principal minors of order $r$.  Equation (\ref{BinetCauchy}) holds for both $MM^{t}$ and $M^{t}M$ because they have the same multiset of non-zero eigenvalues. Details will be omitted. 
\end{proof} 
%
%
%
\subsection{Combinatorial Laplacians for $\gamma$-complexes}
We will assume familiarity with basic definitions concerning finite cell complexes and reduced homology groups. One may refer to standard texts such as  \cite{Mu} for details. 

Let $X$ be a finite cell complex of dimension $d$.  For $i\in [0,d]$, let $X_{i}$ denote the set of all $i$-dimensional cells in $X$.  The $i$-skeleton $X^{(i)}$ of $X$ is $X_{0}\cup X_{1}\cup\cdots \cup X_{i}$.  Since our main object of study is a $\gamma$-complex, we will consider only those $X$ such that $X_{i}\not= \emptyset$ for all $i\in[0,d]$. This condition on $X$ allows one to represent the boundary maps $\partial_{i}$ of its chain complex as matrices. Also we define $X_{-1}$ to be a set with one element.

For $i\in [-1,d]$, the $i$-th chain group of $X$ is the free abelian group  $C_{i}\cong \mathbb{Z}^{|X_{i}|}$ generated by $X_{i}$.  Let $\{C_{i},\partial_{i}\}$ be an augmented chain complex of $X$ with the augmentation $\partial_{0}:C_{0}\rightarrow C_{-1}\cong\mathbb{Z}$ given by $\partial_{0}(v)=1$ for every $v\in X_{0}$.  The $i$-th reduced homology group of $X$ is defined $\tilde{H}_{i}(X)=\mbox{Ker}\,\partial_{i}/\mbox{Im}\,\partial_{i+1}$ where we define $\partial_{d+1}$ and $\partial_{-1}$ to be zero maps. Hence, we have $\tilde{H}_{d}(X)=\mbox{Ker}\,\partial_{d}$ and $\tilde{H}_{-1}(X)=0$. $X$ is {\it acyclic} if $\tilde{H}_{i}(X)=0$ for all $i\in[-1,d]$. 

For $i\in[0,d]$, regard the boundary map $\partial_{i}:C_{i}\rightarrow C_{i-1}$ as a $|X_{i-1}|\!\times\!|X_{i}|$ integer matrix whose rows and columns are indexed by $X_{i-1}$ and $X_{i}$\,, respectively.  In particular, the augmentation $\partial_{0}$ is an all 1's row matrix of size $|X_{0}|$. The coboundary map $\partial^{t}_{i}:C_{i-1}\rightarrow C_{i}$ is the transpose of $\partial_{i}$. 

For $i\in[-1,d]$, the $i$-th combinatorial Laplacian $\Delta_{i}:C_{i}\rightarrow C_{i}$ is defined by 
$$\Delta_{i}
=\partial_{i+1}\partial^{t}_{i+1}+\partial^{t}_{i}\partial_{i}
\mbox{ if } i\in [0,d\!-\!1]\, ,$$ 
$$\Delta_{-1}=\partial_{0}\partial_{0}^{t}\, , \mbox{ and } \Delta_{d}=\partial^{t}_{d}\partial_{d}\, .$$   
Note that $L_{i}:=\partial_{i+1}\partial^{t}_{i+1}$ and $J_{i}:=\partial^{t}_{i}\partial_{i}$ are symmetric, non-negative definite, and $L_{i}J_{i}=J_{i}L_{i}=0$ because $\partial_{i}\partial_{i+1}=0$. Hence, each $\Delta_{i}$ is also symmetric and non-negative definite by Lemma \ref{matrixtheory1}.

An important property of $\Delta_{i}$ is that the dimension of the  0-eigenspace of $\Delta_{i}$ as an operator on a finite dimensional vector space over $\mathbb{Q}$ equals the dimension of the reduced rational homology  
$\tilde{H}_{i}(X;\mathbb{Q})$ \cite[Proposition 2.1]{Fr}. 
Therefore, if $\Delta_{i}\not=0$,  
\begin{equation}\label{Hodge}
\det\Delta_{i}>0\quad\mbox{if and only if}\quad\mathrm{rk}\,\tilde{H}_{i}(X)=0\, .
\end{equation}
Note that $\Delta_{-1}=L_{-1}:\mathbb{Z}\rightarrow\mathbb{Z}$ is a multiplication by $|X_{0}|$. Now the following lemma is immediate from the definition of $\gamma$-complex and (\ref{Hodge}). 
%
\begin{lemma}\label{detDelta} If $\Gamma$ is a $\gamma$-complex of dimension $d$, then $\det\Delta_{i}> 0$ for $i\in [-1, d)$. In addition, if $\Gamma$ is acyclic, then $\det\Delta_{d}>0$ also. \hfill $\Box$
\end{lemma}
% 
%
%
\subsection{Temperley's tree-number formula}\label{Temperley}
For a finite loopless graph $G$ with $n$ vertices and its Laplacian matrix $L(G)$, 
Temperley \cite{Te} showed the following analogue of the Matrix-Tree theorem \cite{Ki} for the number of spanning trees $k(G)$ in $G$. Let $J$ denote the all 1's matrix. 
%
\begin{theorem}\label{TemperleyFormula} 
$$\det (L(G)+J)=n^{2}k(G)\, .$$
\end{theorem}
\begin{proof} We will give a proof of this formula as a consequence of the multilinearity of determinant function and the Matrix-Tree theorem.  We refer the readers to \cite{Bi} for a proof via eigenvalues. 

Let $L(G)+J=(C_{1}+D_{1}, C_{2}+D_{2}, \ldots , C_{n}+D_{n})$, where $C_{i}$'s and $D_{i}$'s are the columns of $L(G)$ and $J$, respectively.  Given a subset $S\subset [n]$, define 
$M_{S}=(X_{1}, X_{2}, \ldots , X_{n})$, where $X_{i}=C_{i}$ if 
$i\notin S$ and $X_{i}=D_{i}$ if $i\in S$. By the multilinearity of determinant function (on columns), $\det(L(G)+J)=\sum_{S\subset [n]}\det M_{S}$, where the sum is over all subsets $S$ of $[n]$. 

Clearly, we have $\det M_{\emptyset}=\det L(G)=0$ because $L(G)$ is singular. Also, if $|S|>1$, then $\det M_{S}=0$ because rank of $J$ is $1$.  However, for every $i\in [n]$, we see that $\det M_{\{i\}}= n k(G)$ because every entry in $D_{i}$ is $1$ and every cofactor of $L(G)$ equals $k(G)$ by the Matrix-Tree theorem. Therefore, we have 
$$\det(L(G)+J)=\sum_{0\leq i\leq n}\det M_{\{i\}}=n^{2}k(G)\; .$$
\end{proof}
%
We make two observations about Theorem \ref{TemperleyFormula}. First, unlike Matrix-Tree theorem, Temperley's formula does not require deletion of a row and a column from $L(G)$ to compute $k(G)$. Second, regarding $G$ as a 1-dimensional $\gamma$-complex, one can check that $L(G)=\partial_{1}\partial_{1}^{t}$ and $J=\partial_{0}^{t}\partial_{0}$. Hence, Theorem \ref{TemperleyFormula} says
\begin{equation} 
\label{TemperleycombinatorialLaplacian}
\det\Delta_{0}=n^{2}k(G)\, .
\end{equation}

As we shall see,  similar observations can be made in computing high-dimensional tree-numbers for $\gamma$-complexes using combinatorial Laplacians.  In particular, one can easily check that equation (\ref{TemperleycombinatorialLaplacian}) is a consequence of Proposition \ref{determinant}.
%
%
%
%
%
\section{High-dimensional trees for $\gamma$-complexes}
We refer the readers to \cite{Ad}, \cite{DKM}, and \cite{Ka} for details of high-dimensional trees and of the exact homology sequence used in the proof of Theorem \ref{nonsingular}. In this section, $\Gamma$ will denote a $\gamma$-complex of dimension $d$. For a non-empty subset $S\subset \Gamma_{i}$, define $\Gamma_{S}:=S\cup\Gamma^{(i-1)}$ as an $i$-dimensional subcomplex of $\Gamma$. For $i\in [-1, d]$, a non-empty subset $B\subset\Gamma_{i}$ is an $i$-{\it dimensional spanning tree} (or simply, $i$-{\it tree}) if 
\begin{enumerate}
\item{} $\tilde{H}_{i}(\Gamma_{B})=0$, 
\item{} $w(B):=|\tilde{H}_{i-1}(\Gamma_{B})|$ is finite, and
\item{} $\tilde{H}_{j}(\Gamma_{B})=0$ for $j\leq i-2$.
\end{enumerate} 
Note that condition 3 is a consequence of the fact $\Gamma_{B}^{(i-1)}=\Gamma^{(i-1)}$. 
We will denote the set of all $i$-trees in $\Gamma$ by $\mathcal{B}_{i}=\mathcal{B}_{i}(\Gamma)$ with $\mathcal{B}_{-1}=\{\emptyset \}$. It is clear that $\mathcal{B}_{0}$ is the set of all single $0$-cells in $\Gamma$ and $\mathcal{B}_{1}$ is the set of all graph theoretic spanning trees of $\Gamma^{(1)}$ as a finite graph.

Define the {\it$i$-th tree-number} of $\Gamma$ to be $$k_{i}=k_{i}(\Gamma)=\sum_{B\in \mathcal{B}_{i}}w(B)^{2}\, .$$
We have $k_{-1}=1$ by definition, and $ k_{0}=|\Gamma_{0}|$. If $\Gamma$ is a connected graph, then $k_{1}$ is the number of spanning trees in $\Gamma$ because $w(B)=1$ for $B\in \mathcal{B}_{1}$. However, $w(B)$ may not equal 1 for $B\in \mathcal{B}_{i}$ when $i>1$. (See \cite{Ka}.) 

Next, we will describe $i$-trees via the boundary operator  $\partial_{i}$ of $\Gamma$, which will show that $k_{i}>0$ for $i\geq 0$. Since  $\partial_{i}\not=0$ for $i\in [0, d]$, both $\Gamma_{i-1}$ and $\Gamma_{i}$ are non-empty. Given a non-empty subset $T\subset \Gamma_{i}$, define $\partial_{T}$ to be the $|\Gamma_{i-1}|\times |T|$ submatrix of $\partial_{i}$ consisting of the columns of $\partial_{i}$ indexed by $T$. Recall that if $\Gamma$ is a connected finite graph of order $n$ with the incidence matrix $\partial_{1}$, then $T\subset \Gamma_{1}$ is a spanning tree of $\Gamma$ iff 
$|T|=\mathrm{rk}\,\partial_{T}=\mathrm{rk}\,\partial_{1}=n-1$. (Refer to \cite{Bi} for details.) More generally, we have the following useful fact. 
%
\begin{proposition}\label{spanningtree}
Let $\Gamma$ be a $\gamma$-complex of dimension $d$. Let $r_{i}=\mathrm{rk}\,\partial_{i}$ for $i\in [0, d]$. Then $\mathcal{B}_{i}$ is non-empty, and it is given by 
\begin{equation}\label{base}
\mathcal{B}_{i}
=\{\,B\subset \Gamma_{i}\,|\,\, |B|=\mathrm{rk}\, \partial_{B}=r_{i}\, \}\, .
\end{equation} 
Moreover, we have $r_{i}=|\Gamma_{i-1}|-r_{i-1}$, where $r_{-1}=0$. 
\end{proposition}
\begin{proof} Suppose $B\in \mathcal{B}_{i}$. Since $\mbox{Ker}\,\partial_{B}=\tilde{H}_{i}(\Gamma_{B})=0$, we have $\mathrm{rk}\,\partial_{B}=|B|$. Since $\Gamma_{B}^{(i-1)}=\Gamma^{(i-1)}$ and $\tilde{H}_{i-1}(\Gamma_{B})$ is finite, we must have $\mathrm{rk}\,\partial_{B}=n_{i-1}$ the rank of $\mbox{Ker}\,\partial_{i-1}$.  However, $\tilde{H}_{i-1}(\Gamma)=0$ implies $r_{i}=n_{i-1}$, and we have $|B|=\mathrm{rk}\, \partial_{B}=r_{i}$\,. The inclusion of the right-hand side of (\ref{base}) in $\mathcal{B}_{i}$ is proved similarly. The second statement follows from 
$n_{i-1}=|\Gamma_{i-1}|-r_{i-1}$. 
\end{proof}
%
\noindent
{\bf Remarks} 1. In matroid theoretic terms, $\mathcal{B}_{i}$ is the set of all bases of a matroid whose ground set is $\Gamma_{i}$ and the independent sets are the subsets $I\subset\Gamma_{i}$ such that $\mbox{Ker}\,\partial_{I}=0$ or $I=\emptyset$. (Refer to \cite{Ox} for the definition of a matroid.)\\
\noindent
2. If $\Gamma$ is also acyclic, then there is exactly one $d$-tree, namely $B=\Gamma_{d}$. Since $\mbox{Ker}\,\partial_{d}=\tilde{H}_{d}(\Gamma)=0$, the only base of the matroid just mentioned is $\Gamma_{d}$. In this case, it also follows that $k_{d}=1$ because $\tilde{H}_{d-1}(\Gamma_{B})=\tilde{H}_{d-1}(\Gamma)=0$.
\\
\noindent
3. If $X$ is a cell complex satisfying ($\gamma$2) but $r_{i}=0$ for some $i$, then $X$ has no $i$-tree. Indeed, for any non-empty subset $S\subset \Gamma_{i}$\,, we would have $\tilde{H}_{i}(\Gamma_{S})=\mathbb{Z}^{|S|}\not=0$.\\
\hfill \\
\indent
The following theorem will play an essential role in Section \ref{mainresults}. Given non-empty subsets $S\subset\Gamma_{i-1}$ and $T\subset\Gamma_{i}$, let $\partial_{S, T}$ be the $|S|\times|T|$ submatrix of $\partial_{i}$ whose rows and columns are indexed by $S$ and $T$, respectively. Denote $\bar{S}=\Gamma_{i-1}\setminus S$. 
%
\begin{theorem}\label{nonsingular}
Let $\Gamma$ be a $\gamma$-complex of dimension $d$. Let $r_{i}=\mathrm{rk}\,\partial_{i}$ for $i\in [0, d]$. Then the set of all $r_{i}\!\times\!r_{i}$ non-singular submatrices of $\partial_{i}$ is given by 
$$
\mathcal{B}(\partial_{i})
:=\{\,\partial_{\bar{A},B}\,|\,A\in\mathcal{B}_{i-1}\,\, \mbox{and}\,\, B\in\mathcal{B}_{i}\,\}\, .
$$
Moreover, we have $|\det\partial_{\bar{A},B}|=w(A)w(B)$ for $\partial_{\bar{A},B}\in \mathcal{B}(\partial_{i})$. 
\end{theorem}
\begin{proof} Let $S\subset\Gamma_{i-1}$ with $|S|=r_{i-1}$ and let $T\subset\Gamma_{i}$ with $|T|=r_{i}$. Then $\partial_{\bar{S},T}$ is a square submatrix of $\partial_{i}$ of order $r_{i}$ by Prop. \ref{spanningtree}. First, we will show that $\partial_{\bar{S},T}$ is singular if $S\notin \mathcal{B}_{i-1}$ or $T\notin \mathcal{B}_{i}$. Regard $\partial_{\bar{S},T}$ as the top boundary operator for the relative complex $(\Gamma_{T},\Gamma_{S})$. Note that 
$\tilde{H}_{i}(\Gamma_{T})=\mbox{Ker}\,\partial_{T}$\,, 
$\tilde{H}_{i}(\Gamma_{T},\Gamma_{S})=\mbox{Ker}\,\partial_{\bar{S},T}$\,, and  
$\tilde{H}_{i-1}(\Gamma_{S})=\mbox{Ker}\,\partial_{S}$. Since $\tilde{H}_{i}(\Gamma_{S})=0$, 
we obtain the following exact sequence from the long exact homology sequence of the pair $(\Gamma_{T},\Gamma_{S})$\,:
$$0\rightarrow\mbox{Ker}\,\partial_{T}
\rightarrow\mbox{Ker}\,\partial_{\bar{S},T}
\rightarrow\mbox{Ker}\,\partial_{S}
\rightarrow\tilde{H}_{i-1}(\Gamma_{T})\, .$$  
If $T\notin \mathcal{B}_{i}$, then $\mbox{Ker}\,\partial_{T}\not=0$ by Remark 1 above. Hence, we have  $\mbox{Ker}\,\partial_{\bar{S},T}\not=0$. Similarly, if $S\notin\mathcal{B}_{i-1}$, then $\mathrm{rk}(\mbox{Ker}\,\partial_{S})\not=0$. If $T\notin \mathcal{B}_{i}$, we are done. If $T\in\mathcal{B}_{i}$, then $\mbox{Ker}\,\partial_{T}=0$ and $\tilde{H}_{i-1}(\Gamma_{T})$ is finite. Therefore, it is clear that $\mbox{Ker}\,\partial_{\bar{S},T}\not=0$.

Now we proceed to prove the second statement, which will also complete the proof of the first statement. Consider the following portion of the long exact homology sequence of the pair $(\Gamma_{B},\Gamma_{A})$ with $A\in\mathcal{B}_{i-1}$ and $B\in\mathcal{B}_{i}$:
$$\tilde{H}_{i-1}(\Gamma_{A})
\rightarrow\tilde{H}_{i-1}(\Gamma_{B})
\rightarrow\tilde{H}_{i-1}(\Gamma_{B},\Gamma_{A})
\rightarrow\tilde{H}_{i-2}(\Gamma_{A})
\rightarrow\tilde{H}_{i-2}(\Gamma_{B})\, .$$  
Since $\tilde{H}_{i-1}(\Gamma_{A})=\tilde{H}_{i-2}(\Gamma_{B})=0$, it follows that $$|\tilde{H}_{i-1}(\Gamma_{B},\Gamma_{A})|=|\tilde{H}_{i-2}(\Gamma_{A})|\cdot|\tilde{H}_{i-1}(\Gamma_{B})|=w(A)w(B)\, .$$
Note that $C_{j}(\Gamma_{B},\Gamma_{A})=\mathbb{Z}^{r_{i}}$ if $j=i-1$, and $0$ if $j<i-1$. Therefore, we have $|\tilde{H}_{i-1}(\Gamma_{B},\Gamma_{A})|=|\mathbb{Z}^{r_{i}}/\mbox{Im}\,\partial_{\bar{A},B}|=|\det \partial_{\bar{A},B}|$. 
\end{proof}
%
%
%
%
%
\section{Main Results}\label{mainresults} 
The following proposition is a generalization of Temperley's tree-number formula (\ref{TemperleycombinatorialLaplacian}) for $\gamma$-complexes. 
%
\begin{proposition}
\label{determinant} 
Let $\Gamma$ be a $\gamma$-complex of dimension $d$, and let $\Delta_{i}$ be its combinatorial Laplacians for $i\in [-1, d]$. Then 
\begin{itemize}
\item[(1)] $\det\Delta_{-1}=k_{0}$,
\item[(2)] $\det\Delta_{i}=k_{i-1}k_{i}^{2}k_{i+1}$ for $i\in [0, d-1]$, and 
\item[(3)] $\det\Delta_{d}=k_{d-1}$ if $\Gamma$ is acyclic, and $0$ otherwise.
\end{itemize}
\end{proposition}
\begin{proof} (1) In Section 2, we noted that $\Delta_{-1}=L_{-1}: \mathbb{Z}\rightarrow\mathbb{Z}$ is a multiplication by $|\Gamma_{0}|$. In Section 3, we also saw that $k_{0}=|\Gamma_{0}|$. Hence $\det\Delta_{-1}=k_{0}$.\\
\noindent
(2) Note that we have $\mathrm{rk}\,\partial_{i}\partial_{i}^{t}
=\mathrm{rk}\,\partial_{i}>0$ for $i\in [0, d]$. Therefore, $\partial_{i}\partial_{i}^{t}$
has non-zero eigenvalues. Let $\pi_{i}$ denote the product of all non-zero eigenvalues of $\partial_{i}\partial_{i}^{t}$.
By Lemma \ref{matrixtheory2} and Theorem \ref{nonsingular}, we have  
\begin{equation*} 
\pi_{i}=\sum_{\substack{\quad A\in\mathcal{B}_{i-1}\\ B\in\mathcal{B}_{i}}}
(\det \partial_{\bar{A},B})^{2}\quad =
\sum_{\substack{\quad A\in\mathcal{B}_{i-1}\\ B\in\mathcal{B}_{i}}}w(A)^{2}w(B)^{2}\quad =\quad k_{i-1}k_{i}\, . 
\end{equation*}
Now recall that $\partial_{i}^{t}\partial_{i}$ and $\partial_{i}\partial_{i}^{t}$ have the same multiset of non-zero eigenvalues. Therefore, for $i\in [0, d\!-\!1]$,  Lemma \ref{matrixtheory1} and Lemma \ref{detDelta} imply
$$\det \Delta_{i}
=\det(\partial_{i}^{t}\partial_{i}+\partial_{i+1}\partial_{i+1}^{t})
=\pi_{i}\pi_{i+1}=k_{i-1}k_{i}^{2}k_{i+1}\, .$$
(3) If $\Gamma$ is acyclic, then $k_{d}=1$ because $\Gamma_{d}$ is the only $d$-tree in $\Gamma$. Therefore,
$$\det\Delta_{d}
=\det(\partial_{d}^{t}\partial_{d})
=\pi_{d}
=k_{d-1}k_{d}=k_{d-1}\, .$$
If $\Gamma$ is not acyclic, then $\mathrm{rk}\,\tilde{H}_{d}(\Gamma)>0$   and $\det\Delta_{d}=0$ by (\ref{Hodge}). 
\end{proof}
%
As we discussed relations between Theorem \ref{TemperleyFormula} and the Matrix-Tree theorem in Section \ref{Temperley},  we can make similar observations about Proposition \ref{determinant} and the {\it Cellular Matrix-Tree Theorem} \cite[Theorem 2.8]{DKM} as follows. Proposition \ref{determinant} may be derived from the Cellular Matrix-Tree Theorem for general APC complexes $X$, which states that 
$\pi_{i}=k_{i-1}k_{i}/|\tilde{H}_{i-2}(X)|^{2}$. Since $\tilde{H}_{i-2}(X)=0$ if $X$ is a $\gamma$-complex, this formula reduces to $\pi_{i}=k_{i-1}k_{i}$ as in the above proof.  Also, if $X$ is an acyclic $\gamma$-complex, then the following theorem, a logarithmic version of Proposition \ref{determinant} for acyclic $\gamma$-complexes, shows that high-dimensional tree numbers of $X$ can be obtained without using reduced Laplacians. Refer to Section \ref{examples} for examples.
%
\begin{theorem}\label{logtree} 
Let $\Gamma$ be an acyclic $\gamma$-complex of dimension $d$. Let  $D(x)=\sum_{i=-1}^{d} \omega_{i}x^{i+1}$ and $K(x)=\sum_{i=0}^{d-1}\kappa_{i}x^{i}$, where $\omega_{i}=\log \det \Delta_{i}$ and $\kappa_{i}=\log k_{i}$ . Then we have
\begin{equation}\label{main}
D(x)=(1+x)^{2}K(x)\, .
\end{equation}
\end{theorem} 
\begin{proof} Since $\Gamma$ is a $\gamma$-complex, we have $\mathcal{B}_{i}\not=\emptyset$ and $k_{i}\geq 1$ for 
$i\in [0, d]$. Hence $K(x)$ is well defined. By Proposition \ref{determinant}, we see that $\det\Delta_{i}\geq 1$ for $i\in [-1, d]$, and $D(x)$ is well defined. The rest of the proof is checking the following details. 
Proposition \ref{determinant} (1) implies $\omega_{-1}=\kappa_{0}$. 
Proposition \ref{determinant} (2) implies $\omega_{i}=\kappa_{i-1}+2\kappa_{i}+\kappa_{i+1}$ for $i\in [0, d\!-\!1]$. In particular, $k_{-1}=1$ implies $\omega_{0}=2\kappa_{0}+\kappa_{1}$, which also follows from (\ref{TemperleycombinatorialLaplacian}). Also, $k_{d}=1$ because $\Gamma$ is acyclic, and we have $\omega_{d-1}=\kappa_{d-2}+2\kappa_{d-1}$.
Finally, Proposition \ref{determinant} (3) implies $\omega_{d}=\kappa_{d-1}$. The result follows.
\end{proof}
%
The requirement that $\Gamma$ be a $\gamma$-complex is important in Theorem \ref{logtree}. For example, one can construct an acyclic cell complex consisting of one 0-cell, one 2-cell, and one 3-cell which is not a $\gamma$-complex because $\partial_{1}=\partial_{2}=0$ in its cellular chain complex. In this case, $\Delta_{1}=0$ and the above theorem cannot be applied.  
\hfill 
\\
\indent
As a corollary to Theorem \ref{logtree}, we obtain the following interesting property of the combinatorial Laplacians for acyclic $\gamma$-complexes.  Refer to \cite{RS} for further discussions.
%
\begin{corollary}\label{torsion} 
Let $\Gamma$ be an acyclic $\gamma$-complex of dimension $d$.  Then 
$$\sum_{q=0}^{d}(-1)^{q+1}q\log \det \Delta_{q}=0\, .$$
\end{corollary}
\begin{proof} Letting $x=-1$ in (\ref{main}), we obtain $\sum_{q=-1}^{d}(-1)^{q+1}\log \det \Delta_{q}=0\, .$ The result follows by differentiating (\ref{main}), letting $x=-1$, and applying this formula. 
\end{proof}
%
\noindent
{\bf Remarks.} Theorem \ref{logtree} can be refined as follows.  Let $\det \Delta_{i}=\prod_{p}p^{\epsilon_{p,i}}$ be the prime decomposition of the positive integer $\det \Delta_{i}$\,. Let $\mathcal{P}$ be the set of all distinct primes that appear in these prime decompositions.  For each $p\in \mathcal{P}$, define 
$$D_{p}(x)=\log p\sum_{i=-1}^{d}\epsilon_{p,i}\, x^{i+1}\, .$$ Then, $D(x)=\sum_{p\in \mathcal{P}}D_{p}(x)$. Also, we claim that each $D_{p}(x)$ is divisible by $(1+x)^{2}$. Indeed, suppose $D_{p}(x)\equiv \log p\, (a_{p}x+b_{p}) \,\mbox{mod}\, (1+x)^{2}$ for some integers $a_{p}$ and $b_{p}$. Since $D(x)\equiv 0 \,\mbox{mod}\, (1+x)^{2}$, we must have $\sum_{p\in\mathcal{P}}\log p\, (a_{p}x+b_{p})=0$. From this equation, one can show that $a_{p}=0$ and $b_{p}=0$ for each $p\in\mathcal{P}$. See Section \ref{anon-acyclicexample} for an example. 
%
%
%
%
%
\section{Examples}\label{examples}
\subsection{Standard simplexes}
Let $\Sigma$ be the standard simplex on $n$ vertices (hence $\dim\Sigma=n-1$). $\Sigma$ is acyclic and  
$|\Sigma_{i}|={n\choose i+1}$ for $i\in [-1, n\!-\!1]$. If $[\sigma]$ denotes an oriented simplex for $\sigma\in\Sigma_{i}$, one can check that $\Delta_{i}[\sigma]=n[\sigma]$, which follows directly from the definition of the boundary operators $\partial_{i}$ and $\partial_{i+1}$ (and their transpose). Therefore, we have $\Delta_{i}=nI$, where $I$ is the identity matrix of order ${n\choose i+1}$, and $\det\Delta_{i}=n^{n\choose i+1}$. 
Letting $\omega_{i}=\log_{n}\det\Delta_{i}={n\choose i+1}$, we see that 
$$D(x)=\sum_{i=-1}^{n-1}\omega_{i}x^{i+1}
=\sum_{i=-1}^{n-1}{n\choose i+1}x^{i+1}
=(1+x)^{n}\, .$$
By Theorem \ref{logtree}, we obtain 
$$K(x)=\sum_{i=0}^{n-2}\kappa_{i}x^{i}=(1+x)^{n-2}\, ,$$ 
where $\kappa_{i}=\log_{n}k_{i}={n-2\choose i}$. Hence, we have $k_{i}=n^{n-2\choose i}$ for $i\in [0, n\!-\!2]$. This result was originally obtained by Kalai \cite{Ka}.
%
%
%
\subsection{Cubical complexes} The $n$-cube $Q_{n}$ ($n\geq 1$) is an $n$-dimensional cell complex that is the $n$-fold product $I\times \cdots \times I$, where $I$ is the unit interval regarded as a cell complex with two 0-cells and one 1-cell. Hence $Q_{n}$ is a cell complex of dimension $n$, and is the convex hull of the $2^{n}$ points in $\mathbb{R}^{n}$ whose coordinates are all 0 or 1. One can see that $Q_{n}$ is acyclic by induction on $n$ together with the fact that $Q_{n-1}$ is a deformation retract of $Q_{n}$ for $n\geq 2$. 

In \cite{DKM}, Duval, Klivans, and Martin showed that the tree-numbers for $Q_{n}$ are 
\begin{equation}\label{cubic}
k_{i}=\prod_{j=2}^{n}(2j)^{{j-2\choose i-1}{n\choose j}} \qquad(i\in [1,n\!-\!1])
\end{equation}
based on the spectra (the multisets of eigenvalues) of $\partial_{i}\partial^{t}_{i}$, which are, in turn, obtained from those of  $\Delta_{i}$'s. In what follows, we will derive (\ref{cubic}) directly from the spectra $Spec(\Delta_{i})$ of $\Delta_{i}$ via Theorem \ref{logtree}. We will start with the following generating function for the eigenvalues of $\Delta_{i}$'s  for  $Q_{n}$ (\cite[Theorem 3.4]{DKM}): 
\begin{equation}\label{specpoly}
\sum_{i=0}^{\dim Q_n}\sum_{\lambda\in Spec(D_{i})} t^{i}r^{\lambda}=(1+r^{2}+tr^{2})^{n}=\sum_{k=0}^{n}t^{k}{n\choose k}r^{2k}(1+r^{2})^{n-k}\, ,
\end{equation}
where $D_{i}=\Delta_{i}$ for $i\geq 1$ and $D_{0}=\partial_{1}\partial_{1}^{t}$.
From (\ref{specpoly}), one can deduce that $\det\Delta_{i}=\prod_{j=1}^{n}(2j)^{{n\choose j}{j\choose i}}$ for $i\in[1,n]$, and that $\pi_{D_{0}}=k_{0}k_{1}=\prod_{j=1}^{n}(2j)^{n\choose j}$. By Theorem \ref{TemperleyFormula}, we also obtain $\det\Delta_{0}=2^{n}\prod_{j=1}^{n}(2j)^{n\choose j}$. Now,
let $\omega_{i}=\log_{2}\det\Delta_{i}$, and let 
$\alpha_{j}={n\choose j}\log_{2}(2j)$. Then, 
$$\omega_{-1}=n,\quad 
\omega_{0}=n+\sum_{j=1}^{n}\alpha_{j}\, ,\quad\mbox{and}\,\,\, \omega_{i}=\sum_{j=1}^{n}{j\choose i}\alpha_{j}\,\, \mbox{for}\,\,  i\in[1,n]\, ,$$
and we have
\begin{equation*}
\begin{split}
D(x) &=\sum_{i=-1}^{n}\omega_{i}x^{i+1}\\
&= n+\Bigl(n+\sum_{j=1}^{n}\alpha_{j}\Bigr)x
+\sum_{i=1}^{n}
\Bigl(\sum_{j=1}^{n}{j\choose i}\alpha_{j}\Bigr)x^{i+1}\\
&=n(1+x)+\sum_{i=0}^{n}
\Bigl(\sum_{j=1}^{n}{j\choose i}\alpha_{j}\Bigr)x^{i+1}\\
&=n(1+x)+x\sum_{j=1}^{n}\alpha_{j}(1+x)^{j} \quad\mbox{(by interchanging the sums)}\\
&=n(1+x)^{2}+x\sum_{j=2}^{n}\alpha_{j}(1+x)^{j} \quad\mbox{(because $\alpha_{1}=n$)}\, .
\end{split}
\end{equation*}
By Theorem \ref{logtree}, we obtain  $$K(x)
=\sum_{i=0}^{n-1}\kappa_{i}x^{i}
=n+x\sum_{j=2}^{n}\alpha_{j}(1+x)^{j-2}\, ,$$ 
where $\kappa_{i}=\log_{2}k_{i}$. By identifying the coefficients of $x^{i}$ for $i\in [1,n\!-\!1]$, we obtain 
$\kappa_{i}
=\sum_{j=2}^{n}{j-2\choose i-1}\alpha_{j}$, and  $k_{i}=\prod_{j=2}^{n}(2j)^{{j-2\choose i-1}{n\choose j}}$ for $i\in [1,n\!-\!1]$.  
%
%
%
\subsection{A non-acyclic example}\label{anon-acyclicexample} Let $X$ be a 2-dimensional simplicial complex on the vertex set $E=\{a,b,c,d,e\}$ given by
$X_{-1}=\{\emptyset\}$, $X_{0}=\binom{E}{1}$, $X_{1}=\binom{E}{2}$, and $X_{2}=\binom{E}{3}\setminus\{ \{a,b,e\},\{c,d,e\}\}$. One can check that $X$ is the independent set complex of a cycle matroid of the graph $K_{4}\setminus \{\mbox{an edge}\}$.  (Refer to \cite{Bj} for general matroid complexes.) In particular, $X$ has the homotopy type of a bouquet of two-dimensional spheres. Hence it is a $\gamma$-complex of dimension 2.

For convenience, assume that simplices in each $X_{i}$ ($i=0,1,2$) are ordered lexicographically, and that the alphabetical ordering of vertices in each simplex gives the positive orientation for the corresponding oriented simplex. For example, $C_{2}$ for $X$ is isomorphic to $\mathbb{Z}^{8}$ generated by the oriented simplices $[abc]$, $[abd]$, $[acd]$, $[ace]$, $[ade]$, $[bcd]$, $[bce]$, and $[bde]$. $X$ is not acyclic because $\tilde{H}_{2}(X)=\operatorname{Ker} \partial_{2}\cong\mathbb{Z}^{2}$ whose generators can be chosen to be $z_{1}=[abc]-[abd]+[ace]-[ade]-[bce]+[bde]$ and $z_{2}=[acd]-[ace]+[ade]-[bcd]+[bce]-[bde]$. The simplices in $z_{1}$ (or $z_{2}$) form a hollow triangular bipyramid. As column vectors, we may write
$$z_{1}=[1,-1,0,1,-1,0,-1,1]^{t} \mbox{ and } z_{2}=[0,0,1,-1,1,-1,1,-1]^{t}\,.$$

Now, let $C_{3}=\mathbb{Z}^{2}$, and define  $\partial_{3}:C_{3}\rightarrow C_{2}$ to be a $8\!\times\! 2$ matrix whose columns are $z_{1}$ and $z_{2}$. One easily checks that the chain complex of $X$ together with $C_{3}$ and $\partial_{3}$ is acyclic.  With this new ``augmented" acyclic complex, one can show
$$\det\Delta_{-1}=5,\, 
\det\Delta_{0}=5^{5},\,
\det\Delta_{1}=2^{2}5^{8},\,
\det\Delta_{2}=2^{4}5^{5}, \mbox{ and }
\det\Delta_{3}=2^{2}5\, .$$ 

By Proposition \ref{determinant}, $\det\Delta_{2}$ and $\det\Delta_{3}$ are independent of the choices of $z_{1}$ and $z_{2}$ because $k_{2}$ depends only on $\partial_{2}$ and $k_{3}=1$. The primes that appear in these prime decompositions are $\mathcal{P}=\{2,5\}$, and we see that
$$D_{2}(x)=\log 2\, (2x^{2}+4x^{3}+2x^{4})=\log 2\,(1+x)^{2}2x^{2}\mbox{ and}$$
$$D_{5}(x)=\log 5\, (1+5x+8x^{2}+5x^{3}+x^{4})=\log 5\, (1+x)^{2}
(1+3x+x^2)\, .$$
By the remarks at the end of Section 4,   
$$D(x)=D_{2}(x)+D_{5}(x)=(1+x)^{2}(\log 5+\log 5^3\, x+\log 2^{2}5\, x^{2})\, ,$$
from which we get $k_{0}=5$, $k_{1}=5^{3}$, and $k_{2}=2^{2}5$ by Theorem \ref{logtree}.
\\
\hfill \\
\noindent
{\bf Question.} Can one characterize tree numbers of a matroid complex via known matroid invariants? 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors would like to thank Prof. M. Wachs for her encouragement to extend the results in \cite{Ko} to generalize Temperley's tree-number formula. We also thank the referee for helpful comments and suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{Ad} R. Adin. \newblock
Counting colorful multi-dimensional trees.
\newblock{\em Combinatorica}, 12(3):247--260, 1992.

\bibitem{Bi} N. Biggs. \newblock {\em Algebraic Graph Theory} (2nd ed.), 
Cambridge University Press, Cambridge, 1993.

\bibitem{Bj} A. Bj\"orner. \newblock The homology and shellability of
matroids and geometric lattices. \newblock In {\em Matroid Applications} (ed. N. White), volume 40 of {\em Encyclopedia of Mathematics and Its Applications}, Cambridge University Press, Cambridge, 1992.

\bibitem{DKM} A. Duval, C. Klivans, and J. Martin. \newblock
Cellular spanning trees and Laplacians of cubical complexes. \newblock{\em 
Advances in Applied Mathematics}, 46:247--274, 2011.

\bibitem{Fr} J. Friedman. \newblock Computing Betti numbers
via combinatorial Laplacians. \newblock In 
{\em Proc. 28th Annual ACM Symposium
on the Theory of Computing}, pages 386--391. ACM: New York, 1996. 

\bibitem{Ga} F. R. Gantmacher. \newblock{\em The Theory of Matrices-Volume I},
Chelsea, New York, 1960.

\bibitem{Ka} G. Kalai. \newblock Enumeration of ${\bf Q}$-acyclic simplicial complexes. \newblock{\em Israel J. Math.}, 45:337--351, 1983.   

\bibitem{Ki} G. Kirchhoff. \newblock \"Uber die Aufl\"osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer 
Str\"ome gef\"urht wird. \newblock{\em Ann. Phys. Chem.}, 72:497--508, 1847.

\bibitem{Ko} W. Kook. \newblock Combinatorial Green's function of a graph and applications to networks. \newblock{\em Advances in Applied Mathematics}, 46:417--423, 2011.

\bibitem{Mu} J.R. Munkres. \newblock{\em Elements of Algebraic Topology},
Addison-Wesley, Reading, MA, 1984.

\bibitem{Ox} J. Oxley. \newblock{\em Matroid Theory},
Oxford University Press, Oxford, England, 1992.

\bibitem{RS} D. B. Ray and I. M. Singer. \newblock R-torsion and the Laplacian on Riemannian manifolds. \newblock{\em Advances in Mathematics}, 7:145--210, 1971.

\bibitem{Te} H.N.V. Temperley. \newblock On the mutual cancellation of cluster integrals in Mayer's fugacity series. \newblock{\em
Proc. Phys. Soc.}, 83:3--16, 1964.


\end{thebibliography}
%
%
%
\end{document}



























