\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
{\bf Fan Chung and S.-T. Yau}
\medskip
\noindent
{\bf Coverings, Heat Kernels and Spanning Trees}
\vskip.5cm


We consider a graph $G$ and a covering $\tilde{G}$
of  $G$ and we study
the relations of their eigenvalues and  heat kernels.
We evaluate the heat kernel for an infinite $k$-regular tree
and we examine the heat kernels
for general $k$-regular graphs.
In particular, we show that a $k$-regular graph on $n$ vertices
has at most
%\[ (1+o(1))  \frac {2\log n}{kn \log k} \left( \frac{(k-1)^{k-1}} {(k^2-2k)^{k/2-1}}\right)^n \]
$$ (1+o(1))   {{2\log n}\over {kn \log k}}
\left( {{ (k-1)^{k-1}}\over {(k^2-2k)^{k/2-1}}}\right)^n $$
spanning trees, which is
best possible within a constant factor.



\bye