%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%           FPSAC/SFCA '94, May 23-27, 1994   at DIMACS
%                     Problem Session
%   LaTeX file of problem submitted by Richard Stanley (May 3, 1994)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentstyle[12pt]{article}
\textwidth6.0truein
\textheight8.0truein
\topmargin-.5truein
\oddsidemargin+0truein
\evensidemargin+0truein
\baselineskip0.20truein
\parskip0.20truein

\begin{document}
\begin{center}
{FPSAC/SFCA '94}\\
{PROBLEM SESSION}\\
{Submission received May 3, 1994}\\[.2in]
{\bf SPANNING TREES OF AZTEC DIAMONDS}\\[.1in]
Richard P. Stanley\\[.2in]
\end{center}
The {\em Aztec diamond graph} AD$_n$ of order $n$ may be defined as
follows: The vertices consist of all integer vectors $(i,j)$
such that $i$ and $j$ are both odd and $|i|+|j|\leq 2n$, with two
vertices connected by an edge if their ordinary Euclidean distance is
two. A beautiful result of Elkies, Kuperberg, Larsen, and Propp
\cite{eklp} asserts that the number of matchings in AD$_n$ is
$2^{n(n+1)/2}$, and much additional work has been done on the
structure of matchings in AD$_n$. Here we wish to point out that the
number of spanning trees of AD$_n$ also appears to be interesting.
For this purpose we also introduce the {\em odd Aztec
  diamond graphs} OD$_n$, defined as follows: The vertices consist of
all integer vectors $(i,j)$ satisfying $|i|+|j|\leq n$, with two
vertices connected by an edge if their Euclidean distance is one. The
graphs OD$_n$ are not so interesting regarding their number of
matchings (since this number is zero), but their number of spanning
trees seems closely related to that of AD$_n$. Let
$\kappa(G)$ denote the number of spanning trees of the graph $G$.

{\bf Conjecture.} $\kappa($AD$_n) = 4\cdot\kappa($OD$_n)$.

The numbers $\kappa($AD$_n)$ and $\kappa($OD$_n)$ themselves seem to
have a lot of factors. For instance:
  \begin{eqnarray*} \kappa(\mbox{AD}_1) & = & 2^2 \\
     \kappa(\mbox{AD}_2) & = & 2^8\cdot 3 \\
     \kappa(\mbox{AD}_3) & = & 2^{10}\cdot 3\cdot 5\cdot 7\cdot 13^2
     \\
     \kappa(\mbox{AD}_4) & = & 2^{26}\cdot 3\cdot 7^2\cdot 17^3 \\
     \kappa(\mbox{AD}_5) & = & 2^{18}\cdot 3^2\cdot 5^3\cdot 11^2\cdot
        29\cdot 41\cdot 101^2\cdot 181^2 \\
     \kappa(\mbox{AD}_6) & = & 2^{32}\cdot 3^7\cdot 5^5\cdot 7^3\cdot
     11^3 \cdot 13^2\cdot 73^2\cdot 193^2.
  \end{eqnarray*}
  Certain other enumerative invariants of Aztec diamond graphs were
  also checked, such as the characteristic polynomial, the matchings
  polynomial, the characteristic polynomial of the Laplacian matrix,
  and the chromatic polynomial. The characteristic polynomial was
  computed by T. Chow \cite{chow} and has some nice properties, but no
  interesting patterns that didn't have simple explanations were seen
  for the other invariants .

  A number of graphs related to AD$_n$ and OD$_n$ also appear to have
  an interesting number of spanning trees. We won't give a complete
  discussion here, but instead will just give one example. Let $T_n$
  be the graph whose vertices consist of all integer vectors $(i,j)$
  with $i\geq 0$, $j\geq 0$, and $i+j<n$, with two vertices connected
  by an edge if their distance is one. Thus $T_n$ may be regarded as
  ``one quarter'' of an Aztec diamond graph. We have
  \begin{eqnarray*} \kappa(T_1) & = & 1\\ \kappa(T_2) & = & 1\\
    \kappa(T_3) & = & 2^2\\ \kappa(T_4) & = & 2^3\cdot 7\\
    \kappa(T_5) & = & 2^4\cdot 3\cdot 5\cdot 11\\
    \kappa(T_6) & = & 2^6\cdot 3^2\cdot 5\cdot 11\cdot
    13\\ \kappa(T_7) & = & 2^6\cdot 7\cdot 13\cdot 29^2
    \cdot 43. \end{eqnarray*}

\begin{thebibliography}{9}

\bibitem{chow} T. Chow, Spectra and complexity of periodic strips,
preprint.

\bibitem{eklp} N. Elkies, G. Kuperberg, M. Larsen, and J. Propp,
Alternating-sign matrices and domino tilings, {\em J.\ Algebraic
  Combinatorics} {\bf 1} (1992), 111--132, 219--234.

\end{thebibliography}
\end{document}