Weighted Tree-Numbers of Matroid Complexes

Woong Kook$^{1}$† and Kang-Ju Lee$^{1}$‡

¹Department of Mathematical Sciences, Seoul National University, Seoul, Korea

**Abstract.** We give a new formula for the weighted high-dimensional tree-numbers of matroid complexes. This formula is derived from our result that the spectra of the weighted combinatorial Laplacians of matroid complexes consist of polynomials in the weights. In the formula, Crapo's $\beta$-invariant appears as the key factor relating weighted combinatorial Laplacians and weighted tree-numbers for matroid complexes.

**Résumé.** Nous présentons une nouvelle formule pour les nombres d'arbres pondérés de grande dimension des matroïdes complexes. Cette formule est dérivée du résultat que le spectre des Laplaciens combinatoires pondérés des matroïdes complexes sont des polynômes à plusieurs variables. Dans la formule, le $\beta$-invariant de Crapo apparaît comme étant le facteur clé reliant les Laplaciens combinatoires pondérés et les nombres d'arbres pondérés des matroïdes complexes.

**Keywords:** matroid complex, weighted combinatorial Laplacians, weighted tree-numbers

# 1 Introduction

The purpose of this paper is to give a new formula for the weighted tree-numbers of matroid complexes. As a high-dimensional analogue of Cayley-Prüfer theorem [29], Kalai [19] found the formula for the weighted tree-numbers of standard simplexes. Continuing his study, Adin [1] presented a formula for the tree-numbers of complete colorful complexes and posed the problem of finding their weighted tree-numbers. Duval, Klivans, and Martin [11] obtained a formula of the weighted tree-numbers of shifted complexes, developing simplicial matrix-tree theorem. We derive a formula of the weighted tree-numbers of the independent set complex of matroids (Theorem 9). In particular, we answer Adin's question in [1, Section 6 (b)].

<footnote>†Email: woongkook@snu.ac.kr This work was partially supported by Research Resettlement Fund for the new faculty of SNU and BK21 PLUS SNU Mathematical Sciences Division.</footnote>

<footnote>‡Email: leekj0706@snu.ac.kr This work was partially supported by BK21 PLUS SNU Mathematical Sciences Division and Kwanjeong Educational Foundation.</footnote>
## 2 Combinatorial Laplacians and high-dimensional tree-numbers

Adin [1] studied high-dimensional tree-number of simplicial complexes via combinatorial Laplacians, and similar studies were conducted in [8, 11–13, 20, 26–28, 30, 34]. For a finite graph, Temperley’s formula demonstrates how the number of spanning trees and the determinant of a combinatorial Laplacian are related.

**Theorem 1** [36, Temperley’s formula] Let $G$ be a finite loopless graph with $n$ vertices with its Laplacian matrix $L(G)$, and $J$ the all 1’s matrix. If we denote the number of spanning trees of $G$ by $k(G)$, then

$$ \det(L(G) + J) = n^2 \cdot k(G). $$

□

As we shall see, $L(G) + J$ is the 0-th combinatorial Laplacian for the chain complex of $G$ as a 1-dimensional complex.

Temperley’s formula has been generalized to high-dimensional complexes [11, 12, 20]. In this paper, we will focus on the following type of complexes. A finite simplicial complex will be called $\mathbb{Z}$-APC ($\mathbb{Z}$-acyclic in positive codimension) if its reduced homology over $\mathbb{Z}$ is trivial except possibly in the top dimension (refer to [11] for the origin of this terminology). The independent set complex $IN(M)$ of a matroid $M$, which is the main object of study in this paper, is $\mathbb{Z}$-APC because it is shellable [3]. We may refer to $IN(M)$ as a *matroid complex*, also.

Let $\{C_i, \partial_i\}$ be an augmented chain complex of a finite $\mathbb{Z}$-APC complex $\Gamma$ of dimension $d$ with the augmentation $\partial_0: C_0 \to \mathbb{Z}$ given by $\partial_0(v) = 1$ for every vertex $v$ in $\Gamma$. Recall that, for $i \in [-1, d]$, the $i$-th combinatorial Laplacian $\Delta_i: C_i \to C_i$ is defined by

$$ \Delta_i = \partial_i^t \partial_i + \partial_{i+1} \partial_{i+1}^t. $$

Note that if $\Gamma$ is a finite graph, then $\partial_0^t \partial_0 = J$ and $\partial_1 \partial_1^t = L(G)$. Hence, Temperley’s formula can be restated as $\det(\Delta_0) = n^2 k(G)$.

Let $\Gamma_i$ be the set of all $i$-simplices, and $\Gamma^{(i)}$ the $i$-skeleton of $\Gamma$. 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$-dimensional tree (or, simply, $i$-tree) if

(1) $H_i(\Gamma_B) = 0$,

(2) $|H_{i-1}(\Gamma_B)|$ is finite, and

(3) $H_j(\Gamma_B) = 0$ for $j \le i - 2$.

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\}$. Define the $i$-th tree-number of $\Gamma$ to be

$$ k_i = k_i(\Gamma) = \sum_{B \in \mathcal{B}_i} |H_{i-1}(\Gamma_B)|^2. $$

The following is a generalization of Temperley’s formula showing a relationship between $\Delta_i$ and unweighted high-dimensional tree-numbers $k_i$.
**Theorem 2** [20, Proposition 7] Let $k_i$ be the $i$-th tree-number of a $\mathbb{Z}$-APC complex $\Gamma$. Then

$$ (1) \det \Delta_{-1} = k_0 $$

$$ (2) \det \Delta_i = k_{i-1} k_i^2 k_{i+1} \text{ for } i \in [0, d-1] $$

$$ (3) \det \Delta_d = k_{d-1} \text{ if } \Gamma \text{ is acyclic, and } 0 \text{ otherwise.} \quad \square $$

## 3 Weighted combinatorial Laplacians and weighted tree-numbers

As a refined enumerator of tree-numbers, we discuss weighted tree-numbers. For example, Cayley-Prüfer theorem [29] gives an enumeration of the spanning trees of complete graphs according to their vertex degrees, and Kalai's formula [19, Theorem 3'] gives an enumeration of high-dimensional tree-numbers of standard simplexes according to their vertex degrees. Other examples of weighted Laplacians and weighted tree-numbers can be found in [11, 12, 30]. In [30], the weights of different dimensions were considered simultaneously, and we will develop similar ideas for matroid complexes in this paper.

Let $\Gamma$ be $\mathbb{Z}$-APC. For each vertex $v \in \Gamma_0$, let $x_v$ be an indeterminate and define the weight of $v$ to be $X_v = x_v^2$. For each face $\sigma \in \Gamma_i$, define $x_\sigma = \prod_{v \in \sigma} x_v$ and define the weight of $\sigma$ to be

$$ X_{\sigma} = \prod_{v \in \sigma} X_v = (x_{\sigma})^2. $$

Denote by $\mathbb{F}$ a field containing $\mathbb{R}$ and all indeterminates $x_v$. Let $\hat{C}_i$ be the $\mathbb{F}$-vector space of $i$-chains in $\Gamma$. The weighted boundary operator $\hat{\partial}_i : \hat{C}_i \to \hat{C}_{i-1}$ is defined as follows. For each oriented $i$-face $[\sigma] = [v_0, v_1, \dots, v_i]$,

$$ \hat{\partial}_i[\sigma] = \sum_{j=0}^{i} (-1)^j x_{v_j} [\sigma - v_j]. $$

Equivalently, $\hat{\partial}_i$ can be defined as

$$ \hat{\partial}_i = W_{i-1}^{-1} \partial_i W_i $$

where $W_i$ is the diagonal matrix whose diagonal entry corresponding to the $i$-face $\sigma \in \Gamma_i$ is $x_\sigma$. Define the $i$-th weighted combinatorial Laplacian $\hat{\Delta}_i : \hat{C}_i \to \hat{C}_i$ to be the $i$-th combinatorial Laplacian of the weighted chain complex $\{\hat{C}_i, \hat{\partial}_i\}$, i.e.,

$$ \hat{\Delta}_i = \hat{\partial}_i^t \hat{\partial}_i + \hat{\partial}_{i+1} \hat{\partial}_{i+1}^t. $$

**Example 1** Let $\mathcal{K}$ be an (abstract) simplicial complex on a vertex set $\{1, 2, 3, 4, 5\}$ whose facets are $\{124, 125, 134, 135, 145, 234, 235, 245\}$ (see Fig. 1). Suppose that the rows and columns of $\hat{\partial}_2 : \hat{C}_2 \to \hat{C}_1$
are ordered lexicographically. Then $\hat{\partial}_2$ is given by

<table><thead><tr><th></th><th>[124]</th><th>[125]</th><th>[134]</th><th>[135]</th><th>[145]</th><th>[234]</th><th>[235]</th><th>[245]</th></tr></thead><tbody><tr><th>[12]</th><td>x<sub>4</sub></td><td>x<sub>5</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>[13]</th><td>0</td><td>0</td><td>x<sub>4</sub></td><td>x<sub>5</sub></td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>[14]</th><td>-x<sub>2</sub></td><td>0</td><td>-x<sub>3</sub></td><td>0</td><td>x<sub>5</sub></td><td>0</td><td>0</td><td>0</td></tr><tr><th>[15]</th><td>0</td><td>-x<sub>2</sub></td><td>0</td><td>-x<sub>3</sub></td><td>-x<sub>4</sub></td><td>0</td><td>0</td><td>0</td></tr><tr><th>[23]</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>x<sub>4</sub></td><td>x<sub>5</sub></td><td>0</td></tr><tr><th>[24]</th><td>x<sub>1</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>-x<sub>3</sub></td><td>0</td><td>x<sub>5</sub></td></tr><tr><th>[25]</th><td>0</td><td>x<sub>1</sub></td><td>0</td><td>0</td><td>0</td><td>0</td><td>-x<sub>3</sub></td><td>-x<sub>4</sub></td></tr><tr><th>[34]</th><td>0</td><td>0</td><td>x<sub>1</sub></td><td>0</td><td>0</td><td>x<sub>2</sub></td><td>0</td><td>0</td></tr><tr><th>[35]</th><td>0</td><td>0</td><td>0</td><td>x<sub>1</sub></td><td>0</td><td>0</td><td>x<sub>2</sub></td><td>0</td></tr><tr><th>[45]</th><td>0</td><td>0</td><td>0</td><td>0</td><td>x<sub>1</sub></td><td>0</td><td>0</td><td>x<sub>2</sub></td></tr></tbody></table>

□

<figure><img src="image_1.png" /><figcaption>Fig. 1: a realization of $\mathcal{K}$</figcaption></figure>

We introduce the definition of weighted high-dimensional tree-numbers by Kalai [19].

**Definition 3** For $i \in [0, d]$, define the $i$-th weighted tree-number of $\Gamma$ to be

$$ \hat{k}_i = \hat{k}_i(\Gamma) = \sum_{B \in \mathcal{B}_i} |H_{i-1}(\Gamma_B)|^2 X_B. \qquad (3.1) $$

where $X_B = \prod_{\sigma \in \mathcal{B}_i} X_\sigma$ is the weight of $B \in \mathcal{B}_i$. Define $\hat{k}_{-1} = 1$.

For each $B \in \mathcal{B}_i$, define the degree of a vertex $v \in \Gamma_0$ in $B$ to be the number of facets in $\Gamma_B$ containing $v$, denoted by $\deg_B v$. When $\Gamma$ is a graph, this definition of degree is the same as that in graph theory. Then
equation (3.1) becomes

$$ \sum_{B \in \mathcal{B}_i} |H_{i-1}(\Gamma_B)|^2 \prod_{v \in \Gamma_0} X_v^{\deg_{\Gamma_B} v}, $$

which explains why weighted tree-numbers are often called degree-weighted tree-numbers. Note that if $X_v = 1$ for all $v \in \Gamma_0$, then we recover the $i$-th (unweighted) tree-number $k_i$.

An example of degree-weighted tree-numbers is the following Cayley-Prüfer [29] theorem for complete graphs.

$$ \sum_{T \in \mathcal{B}_1(K_n)} \prod_{i=1}^{n} X_i^{\deg_T(i)} = X_1 X_2 \cdots X_n (X_1 + X_2 + \cdots + X_n)^{n-2}. $$

A high-dimensional analogue of this theorem is Kalai's formula [19, Theorem 3']

$$ \sum_{B \in \mathcal{B}_i(\Sigma)} |H_{i-1}(\Gamma_B)| \prod_{i=1}^{n} X_i^{\deg_B(i)} = (X_1 X_2 \cdots X_n)^{\binom{n-2}{i-1}} (X_1 + X_2 + \cdots + X_n)^{\binom{n-2}{i}} \quad (3.2) $$

where $\Sigma$ is the standard simplex on $n$ vertices.

The following is the weighted version of Theorem 2.

**Theorem 4** The following holds for a $\mathbb{Z}$-APC complex $\Gamma$ of dimension $d$:

(1) $\det \hat{\Delta}_{-1} = \hat{k}_0$

(2) $\det \hat{\Delta}_i = (\prod_{\sigma \in \Gamma_{i-1}} X_\sigma)^{-1} (\prod_{\sigma \in \Gamma_i} X_\sigma)^{-1} \hat{k}_{i-1} \hat{k}_i^2 \hat{k}_{i+1}$ for $i \in [0, d-1]$

(3) $\det \hat{\Delta}_d = (\prod_{\sigma \in \Gamma_{d-1}} X_\sigma)^{-1} \hat{k}_{d-1} (\prod_{\sigma \in \Gamma_d} X_\sigma)$ if $\Gamma$ is acyclic, and 0 otherwise. $\square$

From now on, let $\Gamma$ be an acyclic complex of dimension $d+1$. The reason for considering dimension $d+1$ is that we will apply an acyclization to a $\mathbb{Z}$-APC complex of dimension $d$.

By using Theorem 2, a relation was found between the generating function of the logarithmic determinants of combinatorial Laplacians and that of the logarithmic tree-numbers, which makes it efficient to compute the tree-numbers [20, Theorem 8]. The following theorem is the weighted version of this relation. We introduce formal logarithm having the following property: $\log XY = \log X + \log Y$ for nonzero $X, Y \in \mathbb{F}$.

**Theorem 5** Let $\hat{D}(x)$, $\hat{K}(x)$, and $F(x)$ be given as follows.

(1) $\hat{D}(x) = \sum_{i=-1}^{d+1} \hat{\omega}_i x^{i+1}$ where $\hat{\omega}_i = \log \det \hat{\Delta}_i$

(2) $\hat{K}(x) = \sum_{i=0}^{d} \hat{\kappa}_i x^i$ where $\hat{\kappa}_i = \log \hat{k}_i$

(3) $F(x) = \sum_{v \in \Gamma_0} \log X_v \left( \left( \sum_{i=0}^{d} f_{v,i} x^{i+1} \right) - f_{v,d+1} x^{d+1} \right)$ where $f_{v,i}$ is the number of $i$-faces in $\Gamma$ containing $v$.

Then we have

$$ \hat{D}(x) = (1+x)^2 \hat{K}(x) - (1+x)F(x), \text{ or} $$

$$ \hat{K}(x) = (1+x)^{-2} \hat{D}(x) + (1+x)^{-1} F(x). $$

$\square$
From this theorem, one can recover Kalai's formula (equation (3.2)).

In addition, we express weighted tree-numbers in terms of the monomials corresponding to all vertices and eigenvalues of weighted combinatorial Laplacians. The following theorem is the weighted version of [12, equation (11)] obtained from Theorem 5.

**Theorem 6** Let $\hat{\Lambda}$ be the set of all distinct eigenvalues of the total weighted Laplacian $\bigoplus_{i=-1}^{d+1} \hat{\Delta}_i$ and let $m_{\hat{\lambda},i}$ be the multiplicity of $\hat{\lambda}$ in $\hat{\Delta}_i$, i.e., $\det \hat{\Delta}_i = \prod_{\hat{\lambda} \in \hat{\Lambda}} \hat{\lambda}^{m_{\hat{\lambda},i}}$. The d-th weighted tree-number $k_d$ of $\Gamma$ is

$$ \prod_{\text{vertices } v \text{ of } \Gamma} (X_v)^{|\tilde{\chi}((lk v)^{(d-2)})|} \prod_{\hat{\lambda} \in \hat{\Lambda}} \hat{\lambda}^{a_{\hat{\lambda},d}} $$

where $a_{\hat{\lambda},d} = \sum_{j=-1}^{d-1} (-1)^{d-j-1} (d-j) m_{\hat{\lambda},j}$ and the link of a vertex $v$ is given by

$$ lk v = \{ \sigma \in \Gamma \mid \sigma \cap \{v\} = \emptyset, \sigma \cup \{v\} \in \Gamma \}, $$

and $(lk v)^{(d-2)}$ denotes the $(d-2)$-skeleton of $lk v$. $\square$

One can regard the characteristic polynomial of $\hat{\Lambda}$ as an element in $\mathbb{F}[x]$, and its eigenvalues as elements in the algebraic closure of $\mathbb{F}$.

## 4 Weighted combinatorial Laplacians of matroid complexes

An interesting question concerning combinatorial Laplacians is which complexes have integral spectra. There are some known complexes with this property: chessboard [18], matching [10], matroid [25], shifted [14], and shifted cubical complexes [12]. Then a natural question for the weighted combinatorial Laplacians is which complexes have spectra that consist of polynomials. Duval, Klivans, and Martin showed that the spectra of the weighted combinatorial Laplacians of shifted complexes consist of polynomials and used their result to give the weighted tree-numbers of shifted complexes [11]. We show that matroid complexes have polynomial spectra and will use these to find the weighted tree-numbers of matroid complexes.

First, we review the spectra of the unweighted combinatorial Laplacians of matroid complexes [25]. Let $M$ be a loopless matroid, $r$ its rank function, $L(M)$ its lattice of flats, and $\mu(V, W)$ the Möbius function on $L(M) \times L(M)$. Define the $\alpha$-invariant $\alpha(M)$ of $M$ to be the unsigned reduced Euler characteristic of its matroid complex $IN(M)$. For convenience, we will denote $\mu(W/V) = |\mu(V, W)|$ and $d = r(M) - 1$.

**Theorem 7** [25, Corollary 18] Let $\Lambda$ be the set of all distinct eigenvalues of the total Laplacian $\bigoplus_{i=-1}^{d} \Delta_i$ of a matroid complex $IN(M)$. Then

$$ \Lambda = \{ |E \setminus V| : V \in L(M) \text{ and } \alpha(V) \neq 0 \} $$

and, for each $\lambda \in \Lambda$, its multiplicity $m_{\lambda,i}$ in $\Delta_i$ is given by

$$ \sum_{V:|E \setminus V|=\lambda} \sum_{W: r(W)=i+1} \alpha(V)\mu(W/V). $$

$\square$
We present the weighted version of the above theorem. Let $\mathbb{F}$ be a field containing $\mathbb{R}$ and all indeterminates $x_e$ for each element $e$ in the ground set $E$ of $M$. For each $e \in E$, define the weight of $e$ to be $X_e = x_e^2$. For each non-empty set $S \subset E$, define $\|S\| = \sum_{e \in S} X_e$ and $\|\emptyset\| = 0$.

**Theorem 8** Let $\hat{\Lambda}$ be the set of all distinct eigenvalues of the total weighted Laplacian $\bigoplus_{i=-1}^{d} \hat{\Delta}_i$ of a matroid complex $IN(M)$ where $\hat{\Delta}_i$ is the $i$-th weighted combinatorial Laplacian of $M$. Then

$$ \hat{\Lambda} = \{ \|E \setminus V\| : V \in L(M) \text{ and } \alpha(V) \neq 0 \} $$

and, for each $\hat{\lambda} = \|E \setminus V\| \in \hat{\Lambda}$, its multiplicity $m_{\hat{\lambda},i}$ in $\hat{\Delta}_i$ is given by

$$ \sum_{W:r(W)=i+1} \alpha(V)\mu(W/V). $$

In particular, the spectra of $\bigoplus_{i=-1}^{d} \hat{\Delta}_i$ consist of polynomials in $X_e$'s. $\square$

<figure><img src="image_2.png" /></figure>

# 5 Weighted tree-numbers of matroid complexes

We show that the weighted tree-numbers of matroid complexes have a nice factorization according to the degrees of their vertices. Our method is different from what was used to find the formula for the weighted tree-numbers of a shifted complex [11]. While the reduced Laplacian in the top dimension was used in [11], we use all of the combinatorial Laplacians.

To begin, we review two important invariants of a matroid $M$ which will appear in the formula. One is $\alpha(M)$ which equals the unsigned reduced Euler characteristic $|\tilde{\chi}(IN(M))|$ of $IN(M)$. Note that $\alpha(M)$ has other interpretations as follows:

$$ \alpha(M) = |\mu_{L(M^*)}(\hat{0}, \hat{1})| = \mathrm{rk} \, \tilde{H}_{r(M)-1}(IN(M)) = T_M(0, 1), $$

where $M^*$ is the dual matroid of $M$, and $T_M(x, y)$ the Tutte polynomial of $M$.

The other is Crapo's $\beta(M)$ which is defined as follows [6]:

$$ \beta(M) = (-1)^{r(M)} \sum_{A \in E(M)} (-1)^{|A|} r(A). $$

For our purpose, it will be useful to take the following equivalent definition of $\beta(M)$ (used in [38, Chapter 7.3]).

$$ \beta(M) = (-1)^{r(M)} \sum_{V \in L(M)} \mu(\hat{0}, V)r(V). $$

It is also known that $\beta(M)$ equals the unsigned reduced Euler characteristic of the reduced broken circuit complex [3]. The following is the main theorem of this paper.

**Theorem 9** The $d$-th weighted tree-number $\hat{k}_d(M) = \hat{k}_d(IN(M))$ of a matroid complex $IN(M)$ is

$$ \prod_{e \in E} X_e^{(|\mathcal{B}(M/e)| - \alpha(M/e))} \prod_{\text{flats } V \text{ of } M} (\sum_{e \in V} X_e)^{\alpha(V)\beta(M/V)}. $$

where $|\mathcal{B}(M)|$ denotes the number of bases of a matroid $M$. Here,

$$ |\mathcal{B}(M/e)| - \alpha(M/e) = |\tilde{\chi}(IN(M/e))^{(d-2)}|. $$

(This equality comes from the shellability of matroid complexes.) $\square$

<figure><img src="image_3.png" /></figure>
This theorem is proved using Theorem 6 and Theorem 8.

By setting $X_e = 1$ for all $e \in E$, we can recover (unweighted) tree-numbers of matroid complexes [24, Theorem 2]. To simplify their formulas, we introduce a convolution of $\alpha$-invariant and $\beta$-invariant.

**Definition 10** For $\lambda \in \Lambda = \{|E \setminus V| : V \in L(M) \text{ and } \alpha(V) \neq 0\}$, define a convolution of $\alpha$-invariant and $\beta$-invariant with respect to $\lambda$ as

$$ \alpha \circ_{\lambda} \beta = \sum_{V \in L(M) : |E \setminus V| = \lambda} \alpha(V)\beta(M/V). $$

**Theorem 11** [24, Theorem 5] The d-th tree-number $k_d(M) = k_d(IN(M))$ of a matroid complex $IN(M)$ is

$$ \prod_{\lambda \in \Lambda} \lambda^{\alpha \circ_{\lambda} \beta}. $$

□

**Example 2** Let $M = M(G)$ be the cycle matroid of $G$ where $G$ is a graph $K_4 - e$ (see Fig.2). Then the cycle matroid complex $IN(M)$ of $M$ is the simplicial complex $\mathcal{K}$ in Example 1 (see Fig.1). We apply our theorem to compute the weighted tree-numbers of the matroid complex $IN(M)$.

First, for each vertex $e$ in $IN(M)$, the matroid complex $IN(M/e)$ of the contraction $M/e$ consists of 4 vertices and so $|\hat{\chi}((IN(M/e))^{(0)})| = 3$.

Second, for each flat $V$ in $M$, let us compute $\alpha(V)$ and $\beta(M/V)$.

* If $V = \emptyset$, then $\alpha(V) = 1$ and $\beta(M/V) = \beta(M) = 1$.

* If $V$ has only one element, then $\alpha(V) = 0$.

* If $V$ is $\{1, 2, 3\}$ or $\{3, 4, 5\}$, then $\alpha(V) = 1$ and $\beta(M/V) = 1$.

* If $V = M$, then $\beta(M/V) = \beta(\emptyset) = 0$.

Therefore,

$$ \hat{k}_2(M) = X_1^3 X_2^3 X_3^3 X_4^3 X_5^3 (X_1 + X_2 + X_3 + X_4 + X_5)(X_1 + X_2)(X_4 + X_5) $$

and we obtain $k_2(M) = 2^2 \cdot 5$.

□

<figure><img src="image_4.png" /><figcaption>**Fig. 2:** a graph $G = K_4 - e$</figcaption></figure>
# 6 Applications: Complete colorful complexes

We give the weighted version of Adin's formula for the tree-numbers of complete colorful complexes, answering the question posed in [1, Section 6 (b)]. Define a complete colorful complex as follows. For each $t \in [r]$, let $E_t = \{e_{1,t}, e_{2,t}, \dots, e_{n_t,t}\}$ be a set of vertices representing color $t$. Let $E = \bigsqcup_{t=1}^r E_t$. Define complete colorful complex $K = K(n_1, \dots, n_r)$ to be a simplicial complex on a vertex set $E$ whose faces are subsets of $E$ each containing at most one element from each $E_t$, i.e.,

$$K = \{F \subset E \mid |F \cap E_t| \le 1 \text{ for } t = 1, \dots, r\}.$$

Note that $K$ is isomorphic to the matroid complex of $\bigoplus_{t=1}^r U_{1,n_t}$ where $U_{1,n_t}$ is a rank 1 uniform matroid on $n_t$ elements. FThe dimension of $K$ is $d = r - 1$. In addition, for each $i \in [1, d]$, the $i$-th skeleton $K^{(i)}$ is a matroid complex.

For each $t \in [r]$, denote the weights of $e_{1,t}, e_{2,t}, \dots, e_{n_t,t}$ by $X_{1,t}, X_{2,t}, \dots, X_{n_t,t}$, respectively. For each $S \subset [r]$, define $\pi_S = \prod_{s \in S} (n_s - 1)$.

**Theorem 12** For $i \in [1, d]$, we have

$$\hat{k}_i(K) = \prod_{t=1}^{r} (X_{1,t} \cdots X_{n_t,t})^{\sum_{j=0}^{i-1} (-1)^{i-1-j} e_j(n_1, \dots, \hat{n}_t, \dots, n_r)} \prod_{|S| \le i} \left( \sum_{s \notin S} X_{1,s} + \cdots + X_{n_s,s} \right)^{\pi_S \binom{r-2-|S|}{i-|S|}}$$

where $e_j(Y_1, \dots, Y_n)$ is the $j$-th elementary symmetric polynomial. In particular,

$$\hat{k}_d(K) = \prod_{t=1}^{r} \left( (X_{1,t} \cdots X_{n_t,t})^{\binom{r-s}{n_s} - \binom{r-s}{n_s-1}} (X_{1,t} + \cdots + X_{n_t,t})^{\binom{r-s}{n_s-1}} \right).$$

□

The weighted top-dimensional tree-number of a complete colorful complex was computed by Aalipour and Duval.

We recover Adin's formula for the unweighted tree-numbers of complete colorful complexes from the above weighted version, by setting $X_{1,t} = \cdots = X_{n_t,t} = 1$ for all $t \in [r]$. (The top-dimensional tree-number of a complete colorful complex was suggested by Bolker [5].)

**Corollary 13** [1, Theorem 1.5] For $i \in [1, d]$, we have

$$k_i(K) = \prod_{|S| \le i} \left( \sum_{s \notin S} n_s \right)^{\pi_S \binom{r-2-|S|}{i-|S|}}.$$

In particular,

$$k_d(K) = \prod_{t=1}^{r} n_t^{\binom{r-s}{n_s-1}}.$$

□

Note that the 1-dimensional skeleton of a complete colorful complex is a complete multipartite graph. By using the above theorem, we obtain the weighted spanning tree-numbers of complete multipartite graphs (For that of a complete bipartite graph, see [35, Exercise 5.30]).

Let $K_{n_1, \dots, n_r}$ be a complete multipartite graph with an $r$-partition $(V_1, \dots, V_r)$. For each $t \in [r]$, let $V_t = \{v_{1,t}, \dots, v_{n_t,t}\}$, and denote the weights of $v_{1,t}, \dots, v_{n_t,t}$ by $X_{1,t}, \dots, X_{n_t,t}$, respectively. For a complete bipartite graph $K_{m,n}$ with a bipartition $(A, B)$ where $A = \{u_1, \dots, u_m\}$ and $B = \{v_1, \dots, v_n\}$, let $X_1, \dots, X_m$ (resp. $Y_1, \dots, Y_n$) be the weights of $u_1, \dots, u_m$ (resp. $v_1, \dots, v_n$).
**Corollary 14** The weighted spanning tree-number of $K_{n_1, \dots, n_r}$ is given by

$$ \hat{k}(K_{n_1, \dots, n_r}) = \left( \prod_{t=1}^{r} X_{1,t} \cdots X_{n_t, t} \right) \left( \sum_{t=1}^{r} (X_{1,t} + \cdots + X_{n_t, t}) \right)^{r-2} \prod_{t=1}^{r} \left( \sum_{s \neq t} (X_{1,s} + \cdots + X_{n_s, s}) \right)^{n_s-1} $$

In particular, the weighted spanning tree-number of $K_{m,n}$ is given by

$$ \hat{k}(K_{m,n}) = (X_1 \cdots X_m)(Y_1 \cdots Y_n)(X_1 + \cdots + X_m)^{n-1}(Y_1 + \cdots + Y_n)^{m-1}. $$

□

When each color set has only one element, we recover Kalai's formula for the weighted tree-numbers of standard simplexes.

**Corollary 15** [19, Theorem 1, 3'] Let $\Sigma$ be the standard simplex on $n$ vertices. For each vertex $v_j \in (\Sigma)_0$, let $X_j$ be its weight. Then the $i$-th weighted tree-number is given by

$$ \hat{k}_i(\Sigma) = (X_1 X_2 \cdots X_n)^{\binom{n-2}{i-1}} (X_1 + X_2 + \cdots + X_n)^{\binom{n-2}{i}}. $$

In particular, its $i$-th tree-number is given by

$$ k_i(\Sigma) = n^{\binom{n-2}{i}}. $$

□

## Acknowledgements

The authors would like to thank Prof. V. Reiner, Prof. A. Duval, Prof. C. Klivans, and Prof. J. Martin for helpful conversations concerning high-dimensional trees. We also would like to thank anonymous referees for helpful comments and suggestions.

## References

[1] R. Adin, *Counting colorful multi-dimensional trees*, Combinatorica 12(3) (1992), 247-260.

[2] N. Biggs. *Algebraic Graph Theory* (2nd ed.), Cambridge University Press, Cambridge, 1993.

[3] A. Björner, The homology and shellability of matroids and geometric lattices, in *Matroid Applications* (ed. N. White) of *Encyclopedia of Mathematics and Its Applications vol. 40*, Cambridge Univ. Press, Cambridge, 1992, 226-283.

[4] A. Björner and G. Kalai, On f-vectors and homology, in: Combinatorial Mathematics, Proc. of 3rd International Conference (New York, 1985), N.Y. Acad. Sci., New York, (1989), 63-80.

[5] E. D. Bolker, Simplicial geometry and transportation polytopes, *Trans. Amer. Math. Soc.* 218 (1976) 121-142.

[6] H. Crapo, A higher invariant for matroids, *J. Comb. Theory* 2 (1967) 406-417.
[7] H. Crapo, The Tutte polynomial, *Aequationes Math.* 3 (1969) 211-229.

[8] M. Catanzaro, V. Chernyak, and J. Klein, Kirchhoff's theorems in higher dimensions and Reide-meister torsion, arXiv:1206.6783.

[9] G. Denham, The Combinatorial Laplacian of the Tutte complex, *J. Algerba* 242 (2001) 160-175.

[10] X. Dong and M. Wachs, Combinatorial Laplacian of the matching complex, *Electron. J. Combin.* 9 (2002), #R17, 11 pp.

[11] A. Duval, C. Klivans, and J. Martin, Simplicial matrix-tree theorems, *Trans. Amer. Math. Soc.* 361 (2009) 6073-6114.

[12] A. Duval, C. Klivans, and J. Martin, Cellular spanning trees and Laplacians of cubical complexes, *Adv. Appl. Math.* 46 (2011) 247-274.

[13] A. Duval, C. Klivans, and J. Martin, Cuts and flows of cell complexes, preprint arXiv:1206.6157v1 (2012).

[14] A. Duval and V. Reiner, Shifted simplicial complexes are Laplacian integral, *Trans. Amer. Math. Soc.* 354 (2002) 4313-4344.

[15] G. Etienne and M. Las Vergnas, External and internal elements of a matroid basis, *Disc. Math.* 179 (1998) 111-119.

[16] J. Friedman, Computing Betti numbers via combinatorial Laplacians, in *Proc. 28th Annual ACM Symposium on the Theory of Computing*, ACM: New York, (1996) 386-391.

[17] J. Friedman, Computing Betti numbers via combinatorial Laplacians, *Algorithmica* 21 (1998) 331-346.

[18] J. Friedman and P. Hanlon, On the Betti numbers of chessboard complexes, *J. Algebraic Combin.* 8 (1998) 193-203.

[19] G. Kalai, Enumeration of $\mathbb{Q}$-acyclic simplicial complexes, *Israel J. Math.* 45 (1983) 337-351.

[20] H. Kim and W. Kook, Logarithmic tree-numbers for acyclic complexes, *Electron. J. Combin.* 21 (2014) #P1.50, 12 pp.

[21] W. Kook, The homology of the cycle matroid of a coned graph, *European J. Combin.* 28 (2007) 734-741.

[22] W. Kook, Edge-rooted forest and the $\alpha$-invariant of cone graphs, *Disc. Appl. Math.* 155 (2007) 1071-1075.

[23] W. Kook, Combinatorial Green's function of a graph and applications to networks, *Adv. Appl. Math.* 46 (2011) 417-423.

[24] W. Kook and K. Lee, A formula for simplicial tree-numbers of matroid complexes, submitted (2014).
[25] W. Kook, V. Reiner, and D. Stanton, Combinatorial Laplacians of matroid complexes, *J. Amer. Math. Soc.* 13 (2000) 129-148.

[26] R. Lyons, Determinantal probability measures, *Publ. Math. Inst. Hautes Etudes Sci.* 98 (2003) 167-212.

[27] R. Lyons, Random complexes and $l^2$-Betti numbers, *J. Topol. Anal.* 1 (2009) 153-175.

[28] M. Maxwell, Enumerating bases of self-dual matroids, *J. Combin. Theory Ser. A* 116 (2009) 351-378.

[29] J.W. Moon, *Counting labelled trees*, Canadian Mathematical Monographs 1, Canad. Math. Cong., 1970.

[30] J. Martin, M. Maxwell, V. Reiner, and S. Wilson, Pseudodeterminants and perfect square spanning tree counts, arXiv:1311.6686 (2013).

[31] J. Martin and V. Reiner, Factorization of some weighted spanning tree enumerators, *J. Combin. Theory Ser. A* 104 (2003) 287-300.

[32] J. Munkres, *Elements of Algebraic Topology*, Addison-Wesley, Reading, MA, 1984.

[33] J. Oxley, *Matroid Theory*, Oxford University Press, Oxford, 1992.

[34] A. Petersson, *Enumeration of spanning trees in simplicial complexes*, Masters thesis, Uppsala Univ., 2008.

[35] R. Stanley, *Enumerative Combinatorics*, vol. II. Cambridge Studies in Advanced Mathematics, 62. Cambridge University Press, Cambridge, 1999.

[36] H.N.V. Temperley, On the mutual cancellation of cluster integrals in Mayer's fugacity series, *Proc. Phys. Soc.*, 83:3-16 (1964).

[37] D. J. A. Welsh, *Matorid Theory*, Dover Books on Mathematics, 2010.

[38] N. White, *Combinatorial Geometries*, *Encyclopedia of Mathematics and Its Applications* vol. 29, Cambridge Univ. Press, Cambridge, 1987.