Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Counting spanning trees of the hypercube and its $q$-analogs by explicit
  block diagonalization   The number of spanning trees of a graph $G$ is called the {\em complexity} of
$G$ and is denoted $c(G)$. Let C(n) denote the {\em (binary) hypercube} of
dimension $n$. A classical result in enumerative combinatorics (based on
explicit diagonalization) states that $c(C(n)) = \prod_{k=2}^n (2k)^{n\choose
k}$.
  In this paper we use the explicit block diagonalization methodology to derive
formulas for the complexity of two $q$-analogs of C(n), the {\em nonbinary
hypercube} $\Cq(n)$, defined for $q\geq 2$, and the {\em vector space analog of
the hypercube} $\Cfq(n)$, defined for prime powers $q$.
  We consider the nonbinary and vector space analogs of the Boolean algebra. We
show the existence, in both cases, of a graded Jordan basis (with respect to
the up operator) that is orthogonal (with respect to the standard inner
product) and we write down explicit formulas for the ratio of the lengths of
the successive vectors in the Jordan chains (i.e., the singular values). With
respect to (the normalizations of) these bases the Laplacians of $\Cq(n)$ and
$\Cfq(n)$ block diagonalize, with quadratically many distinct blocks in the
nonbinary case and linearly many distinct blocks in the vector space case, and
with each block an explicitly written down real, symmetric, tridiagonal matrix
of known multiplicity and size at most $n+1$. In the nonbinary case we further
determine the eigenvalues of the blocks, by explicitly writing out the
eigenvectors, yielding an explicit formula for $c(\Cq(n))$ (this proof yields
new information even in the binary case). In the vector space case we have been
unable to determine the eigenvalues of the blocks but we give a useful formula
for $c(\Cfq(n))$ involving "small" determinants (of size at most $n$).

0
The categories of this paper are: hep-ph
35
The categories of this paper are: mtrl-th
23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
16
The categories of this paper are: stat
36
The categories of this paper are: cmp-lg
29
The categories of this paper are: funct-an
3
The categories of this paper are: physics
26
The categories of this paper are: bayes-an
20
The categories of this paper are: acc-phys
27
The categories of this paper are: comp-gas
33
The categories of this paper are: plasm-ph
8
The categories of this paper are: hep-ex
25
The categories of this paper are: patt-sol
4
The categories of this paper are: cond-mat
5
The categories of this paper are: gr-qc