# Flag enumerations of matroid base polytopes

Sangwook Kim†

Department of Mathematical Sciences
George Mason University
Fairfax, VA 20121, USA

**Abstract.** In this paper, we study flag structures of matroid base polytopes. We describe faces of matroid base polytopes in terms of matroid data, and give conditions for hyperplane splits of matroid base polytopes. Also, we show how the cd-index of a polytope can be expressed when a polytope is cut by a hyperplane, and apply these to the cd-index of a matroid base polytope of a rank 2 matroid.

**Résumé.** Dans cet article, nous étudions les structures de drapeau de polytopes de base de matroïde. Nous décrivons des faces de polytopes de base de matroïde en terme des données de matroïde, et donner des conditions pour les divisions de hyperplane de polytopes de base de matroïde. Aussi, nous montrons comment le cd-index d'un polytope peut être exprimé' quand un polytope est coupé par un hyperplane, et s'appliquer ceux-ci au cd-index d'un polytope de base de matroid d'un rang 2 matroïde.

**Keywords:** matroid base polytopes, hyperplane splits, cd-index

## 1 Introduction

For a matroid $M$ on $[n]$, a *matroid base polytope* $Q(M)$ is the polytope in $\mathbb{R}^n$ whose vertices are the incidence vectors of the bases of $M$. The polytope $Q(M)$ is a face of a *matroid polytope* first studied by Edmonds [Edm03], whose vertices are the incidence vectors of all independent sets in $M$.

It is known that a face $\sigma$ of a matroid base polytope is the matroid base polytope $Q(M_\sigma)$ for some matroid $M_\sigma$ on $[n]$ (see [FS05] and Section 2 below). We show that $M_\sigma$ can be described using equivalence classes of factor-connected flags of subsets of $[n]$. As a result, one can describe faces of $Q(M)$ in terms of matroid data:

**Theorem 1.1 (Theorem 2.7)** Let $M$ be a matroid on a ground set $[n]$. For a face $\sigma$ of the matroid base polytope $Q(M)$, one can associate a poset $P_\sigma$ defined as follows:

(i) the elements of $P_\sigma$ are the connected components of $M_\sigma$, and

<footnote>†This research forms part of the author's doctoral dissertation at the University of Minnesota, under the supervision of Victor Reiner, and partially supported by NSF grant DMS-0245379.</footnote>
(ii) for distinct connected components $C_1$ and $C_2$ of $M_\sigma$, $C_1 < C_2$ if and only if

$$C_2 \subset S \subset [n] \text{ and } \sigma \subset H_S \text{ implies } C_1 \subset S,$$

where $H_S$ is the hyperplane in $\mathbb{R}^n$ defined by $\sum_{e \in S} x_e = r(S)$.

The cd-index $\Psi(Q)$ of a polytope $Q$, a polynomial in the noncommutative variables $c$ and $d$, is a very compact encoding of the flag numbers of a polytope $Q$ [BK91]. Ehrenborg and Readdy [ER98] express the cd-indices of a prism, a pyramid, and a bipyramid of a polytope $Q$ in terms of cd-indices of $Q$ and its faces. Also, the cd-index of zonotopes, a special class of polytopes, is well-understood [BER97, BER98]. Generalizing the formula of the cd-index of a prism and a pyramid of a polytope, we show how the cd-index of a polytope can be expressed when a polytope is cut by a hyperplane in Section 3.

In Section 4, we find the conditions when a matroid base polytope is split into two matroid base polytopes by a hyperplane:

**Theorem 1.2 (Theorem 4.1)** Let $M$ be a rank $r$ matroid on $[n]$ and $H$ be a hyperplane in $\mathbb{R}^n$ given by $\sum_{e \in S} x_e = k$. Then $H$ decomposes $Q(M)$ into two matroid base polytopes if and only if

$$(i) \ r(S) \geq k \text{ and } r(S^c) \geq r - k,$$

(ii) if $I_1$ and $I_2$ are $k$-element independent subsets of $S$ such that $(M/I_1)|_{S^c}$ and $(M/I_2)|_{S^c}$ have rank $r-k$, then $(M/I_1)|_{S^c} = (M/I_2)|_{S^c}$.

We apply this theorem to the cd-index of matroid base polytopes for rank 2 matroids in Section 5.

## 2 Matroid base polytopes

This section contains the description of faces of matroid base polytopes. In particular, we associate a poset for each face of a matroid base polytope.

We start with a precise characterization of matroid base polytopes. Let $\mathcal{B}$ be a collection of $r$-element subsets of $[n]$. For each subset $B = \{b_1, \dots, b_r\}$, define

$$e_B := e_{b_1} + \dots + e_{b_r} \in \mathbb{R}^n,$$

where $e_i$ is the $i$th standard basis vector of $\mathbb{R}^n$. The collection $\mathcal{B}$ is represented by the convex hull of these points

$$Q(\mathcal{B}) := \text{conv}\{e_B : B \in \mathcal{B}\}.$$

This is a convex polytope of dimension $\leq n-1$ and is a subset of the $(n-1)$-simplex

$$\Delta_n = \{(x_1, \dots, x_n) \in \mathbb{R}^n : x_1 \ge 0, \dots, x_n \ge 0, x_1 + \dots + x_n = r\}.$$

Gelfand, Goresky, MacPherson, and Serganova [GGMS87, Thm. 4.1] show the following characterization of matroid base polytopes.

**Theorem 2.1** $\mathcal{B}$ is the collection of bases of a matroid if and only if every edge of the polytope $Q(\mathcal{B})$ is parallel to a difference $e_\alpha - e_\beta$ of two distinct standard basis vectors.
For a rank $r$ matroid $M$ on a ground set $[n]$ with a set of bases $\mathcal{B}(M)$, the polytope $Q(M) := Q(\mathcal{B}(M))$ is called the *matroid base polytope* of $M$.

By the definition, the vertices of $Q(M)$ represent the bases of $M$. For two bases $B$ and $B'$ in $\mathcal{B}(M)$, $e_B$ and $e_{B'}$ are connected by an edge if and only if $e_B - e_{B'} = e_\alpha - e_\beta$. Since the latter condition is equivalent to $B - B' = \{\alpha\}$ and $B' - B = \{\beta\}$, the edges of $Q(M)$ represent the basis exchange axiom.

The basis exchange axiom gives the following equivalence relation on the ground set $[n]$ of the matroid $M$: $\alpha$ and $\beta$ are equivalent if there exist bases $B$ and $B'$ in $\mathcal{B}(M)$ with $\alpha \in B$ and $B' = (B - \{\alpha\}) \cup \{\beta\}$. The equivalence classes are called the *connected components* of $M$. The matroid $M$ is called *connected* if it has only one connected component. Feichtner and Sturmfels [FS05, Prop. 2.4] express the dimension of the matroid base polytope $Q(M)$ in terms of the number of connected components of $M$.

**Proposition 2.2** Let $M$ be a matroid on $[n]$. The dimension of the matroid base polytope $Q(M)$ equals $n - c(M)$, where $c(M)$ is the number of connected components of $M$.

Theorem 2.1 implies that every face of a matroid base polytope is also a matroid base polytope. For $\omega \in \mathbb{R}^n$, let $M_\omega$ denote the matroid whose bases $\mathcal{B}(M_\omega)$ is the collection of bases of $M$ having minimum $\omega$-weight. Then $Q(M_\omega)$ is the face of $Q(M)$ at which the linear form $\sum_{i=1}^n \omega_i x_i$ attains its minimum. Let $\mathcal{F}(\omega)$ denote the unique flag of subsets

$$ \{\emptyset := S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\} $$

for which $\omega$ is constant on each set $S_i - S_{i-1}$ and $\omega|_{S_i - S_{i-1}} < \omega|_{S_{i+1} - S_i}$. The weight class of a flag $\mathcal{F}$ is the set of vectors $\omega$ such that $\mathcal{F}(\omega) = \mathcal{F}$. Ardila and Klivans [AK06] show that $M_\omega$ depends only on $\mathcal{F}(\omega)$, and hence one can call it $M_{\mathcal{F}}$. They also give the following description of $M_{\mathcal{F}}$.

**Proposition 2.3 ([AK06, Prop. 2])** Let $M$ be a matroid on $[n]$ and $\mathcal{F}$ be a flag of subsets

$$ \{\emptyset := S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\}. $$

Then

$$ M_{\mathcal{F}} = \bigoplus_{i=1}^{k+1} (M|_{S_i})/S_{i-1}. $$

A flag $\mathcal{F} = \{\emptyset =: S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\}$ is called *factor-connected* (with respect to $M$) if the matroids $(M|_{S_i})/S_{i-1}$ are connected for all $i = 0, \dots, k+1$. Proposition 2.2 and Proposition 2.3 together with the fact $Q(M_1 \oplus M_2) = Q(M_1) \times Q(M_2)$ show that the dimension of $Q(M_{\mathcal{F}})$ is $n-k-1$ if $\mathcal{F}$ is factor-connected.

For a connected matroid $M$ on $[n]$, facets of $Q(M)$ correspond to factor-connected flags of the form $\emptyset \subset S \subset [n]$. Feichtner and Sturmfels [FS05] show that there are two types of facets of $Q(M)$ for a connected matroid $M$ on $[n]$:

(i) a facet corresponding to a factor-connected flag $\emptyset \subset F \subset [n]$ for some flat $F$ of $M$ (in this case, the facet is called a *flacet*),

(ii) a facet corresponding to a factor-connected flag $\emptyset \subset S \subset [n]$ for some $(n-1)$-subset $S$ of $[n]$.
**Proposition 2.4** Let M be a matroid on $[n]$ and

$$ \mathcal{F} = \{\emptyset := S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\} $$

be a factor-connected flag. Then the matroid $(M|_{S_{j+1}})/S_{j-1}$ has at most two connected components for $1 \le j \le k$.

(i) If it has one connected component, the flag

$$ \mathcal{G} = \{\emptyset := S_0 \subset \cdots \subset S_{j-1} \subset S_{j+1} \subset \cdots \subset S_{k+1} := [n]\} $$

is factor-connected and $Q(M_{\mathcal{G}})$ covers $Q(M_{\mathcal{F}})$ in the face lattice of $Q(M)$.

(ii) If it has two connected components, then they are $S_{j+1} - S_j$ and $S_j - S_{j-1}$. Moreover, the flag

$$ \mathcal{F}' = \{\emptyset := S_0 \subset \cdots \subset S_{j-1} \subset S'_j \subset S_{j+1} \subset \cdots \subset S_{k+1} := [n]\}, $$

where $S'_j = S_{j-1} \cup (S_{j+1} - S_j)$, is factor-connected and $Q(M_{\mathcal{F}'}) = Q(M_{\mathcal{F}})$.

**Proof:** Since $(M|_{S_{j+1}})/S_j = [(M|_{S_{j+1}})/S_{j-1}]/(S_j - S_{j-1})$ and $(M|_{S_j})/S_{j-1} = [(M|_{S_{j+1}})/S_{j-1}]|_{S_j}$ for $j = 1, \dots, k$, the first assertion follows from [Oxl92, Proposition 4.2.10], and the other assertions are obtained from [Oxl92, Proposition 4.2.13] and Proposition 2.3. $\square$

Two factor-connected flags $\mathcal{F}$ and $\mathcal{F}'$ are said to be equivalent if there is a sequence of factor-connected flags $\mathcal{F} = \mathcal{F}_0, \mathcal{F}_1, \dots, \mathcal{F}_k = \mathcal{F}'$ such that $\mathcal{F}_i$ is obtained from $\mathcal{F}_{i-1}$ by applying Proposition 2.4(ii) for $i = 1, \dots, k$. We write $\mathcal{F} \sim \mathcal{F}'$ when factor-connected flags $\mathcal{F}$ and $\mathcal{F}'$ are equivalent.

The following proposition shows that the equivalence classes of factor-connected flags characterize faces of a matroid base polytope.

**Proposition 2.5** Let M be a matroid on $[n]$. If $\mathcal{F}$ and $\mathcal{F}'$ are two factor-connected flags given by

$$ \mathcal{F} = \{\emptyset := S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\}, $$

$$ \mathcal{F}' = \{\emptyset := T_0 \subset T_1 \subset \cdots \subset T_t \subset T_{t+1} := [n]\}, $$

then $M_{\mathcal{F}} = M_{\mathcal{F}'}$ if and only if $\mathcal{F}$ and $\mathcal{F}'$ are equivalent.

**Proof:** If $\mathcal{F} \sim \mathcal{F}'$, then $M_{\mathcal{F}} = M_{\mathcal{F}'}$ from Proposition 2.4.

For the other direction, suppose that $M_{\mathcal{F}} = M_{\mathcal{F}'}$. Then $\mathcal{F}$ and $\mathcal{F}'$ have the same length since $\dim Q(M_{\mathcal{F}}) = n - k - 1$ and $\dim Q(M_{\mathcal{F}'}) = n - t - 1$.

We will use induction on $k$. Without loss of generality, we may assume that $S_1 \neq T_1$. Then one can show that

$$ T_1 = S_m - S_{m-1} \text{ for some } m > 1. \qquad (1) $$

Base case: $k = 1$. Equation (1) gives $T_1 = S_2 - S_1$ and $T_1 \cup S_1 = [n]$. Then M has two connected components, and hence $\mathcal{F}$ and $\mathcal{F}'$ are equivalent by Proposition 2.4(ii).
Inductive step. Now suppose that $k > 1$. The flag

$$ \tilde{\mathcal{F}} := \{\emptyset =: S_0 \subset S_1 \subset S_1 \cup T_1 \subset S_2 \cup T_1 \subset \dots \subset \underbrace{S_{m-1} \cup T_1}_{=S_m} \subset S_{m+1} \dots \subset S_{k+1} := [n]\} $$

is factor-connected and equivalent to $\mathcal{F}$. Moreover, $M_{\tilde{\mathcal{F}}} = M_{\mathcal{F}}$.

Also, one can show $S_1 = T_l - T_{l-1}$ for some $l > 1$ and the flag

$$ \tilde{\mathcal{F}} := \{\emptyset =: T_0 \subset T_1 \subset S_1 \cup T_1 \subset S_1 \cup T_2 \subset \dots \subset \underbrace{S_1 \cup T_{l-1}}_{=T_l} \subset T_{l+1} \dots \subset T_{k+1} := [n]\} $$

is a factor-connected flag equivalent to $\mathcal{F}'$ and $M_{\tilde{\mathcal{F}}'} = M_{\mathcal{F}'}$.

By the induction assumption, we have $\tilde{\mathcal{F}} \sim \tilde{\mathcal{F}}'$ and hence $\mathcal{F}$ and $\mathcal{F}'$ are equivalent. $\square$

If $M$ is a matroid on $[n]$ and $S$ is a subset of $[n]$, then the hyperplane $H_S$ defined by $\sum_{e \in S} x_e = r(S)$ is a supporting hyperplane of $Q(M)$ and $Q(M) \cap H_S$ is the matroid base polytope for $(M|_S) \oplus (M/S)$. The next lemma tells us when a face of $Q(M)$ is contained in $H_S$.

**Lemma 2.6** Let $M$ be a matroid on $[n]$ and $S$ be a subset of $[n]$. A face $\sigma$ of $Q(M)$ is contained in $H_S$ if and only if there is a factor-connected flag

$$ \mathcal{F} = \{\emptyset =: S_0 \subset S_1 \subset \dots \subset S_k \subset S_{k+1} := [n]\} $$

such that $S = S_m$ for some $m$ and $\sigma = Q(M_{\mathcal{F}})$.

For a face $\sigma$ of $Q(M)$, let $L_\sigma$ be the poset of all subsets of $[n]$ which are contained in some factor-connected flag $\mathcal{F}$ with $\sigma = Q(M_{\mathcal{F}})$ ordered by inclusion. Then one can show that $L_\sigma$ is a lattice. Since $L_\sigma$ is a sublattice of the Boolean lattice $B_n$, it is distributive. The fundamental theorem for finite distributive lattices [Sta97] shows that there is a finite poset $P_\sigma$ for which $L_\sigma$ is the lattice of order ideals of $P_\sigma$. Recall that $M_\sigma$ is the matroid on $[n]$ such that $Q(M_\sigma) = \sigma$.

**Theorem 2.7** Let $M$ be a matroid on $[n]$ and $\sigma$ be a face of $Q(M)$. Then $L_\sigma$ is the lattice of order ideals of $P_\sigma$, where $P_\sigma$ is a poset defined as follows:

(i) the elements of $P_\sigma$ are the connected components of $M_\sigma$, and

(ii) for distinct connected components $C_1$ and $C_2$ of $M_\sigma$, $C_1 < C_2$ if and only if

$$ C_2 \subset S \subset [n] \text{ and } \sigma \subset H_S \text{ implies } C_1 \subset S. $$

Note that $P_\sigma$ is a well-defined poset. Reflexivity and transitivity are clear. Suppose $C_1$ and $C_2$ are distinct connected components of $M_\sigma$ with $C_1 < C_2$. Consider a minimal subset $S$ such that $C_2 \subset S$ and $\sigma \subset H_S$. Then $\sigma \subset H_{S-C_2}$ by Lemma 2.6. Since $C_1 \subset S - C_2$ and $C_2 \not\subset S - C_2$, we have $C_2 \not\subset C_1$.

**Example 2.8** Let $M_{2,1,1}$ be the rank 2 matroid on $[4] = \{1, 2, 3, 4\}$ whose unique non-base is 12 (short for $\{1, 2\}$) and let $\sigma$ be an edge of $Q(M_{2,1,1})$ connecting $e_{14}$ and $e_{24}$. Then the connected components of $M_\sigma$ are 12, 3 and 4. Since $\{1, 2, 3, 4\}$ is the only subset $S$ containing $\{3\}$ such that $\sigma \subset H_S$, $12 < 3$ and $4 < 3$ in $P_\sigma$. One can see that there are no other relations in $P_\sigma$. Figure 1 is the proper part of the face poset of $Q(M_{2,1,1})$ whose faces are labeled by corresponding posets and $P_\sigma$ is shown in the shaded box.
<figure><img src="image_1.png" /><figcaption>Fig. 1: The proper part of the face poset of $Q(M_{2,1,1})$</figcaption></figure>

**Proof of Theorem 2.7:** Let $S$ be a set in $L_\sigma$. By Lemma 2.6, there is a factor-connected flag

$$ \mathcal{F} = \{\emptyset =: S_0 \subset S_1 \subset \cdots \subset S_k \subset S_{k+1} := [n]\} $$

such that $M_\sigma = M_\mathcal{F}$ and $S = S_m$ for some $m$. Note that the connected components of $M_\sigma$ are $S_i - S_{i-1}$ for $1 \le i \le k+1$ and $S = \cup_{j=1}^m (S_j - S_{j-1})$. Suppose $S_i - S_{i-1} < S_j - S_{j-1}$ in $P_\sigma$ for some $j \le m$. Since $S_j - S_{j-1} \subset S$ and $\sigma \subset H_S$, the definition of $P_\sigma$ implies $S_i - S_{i-1} \subset S$, and hence $S$ is an order ideal of $P_\sigma$.

Conversely, suppose $T$ is an order ideal of $P_\sigma$. Let $T'$ be the intersection of all subsets $\tilde{T}$ satisfying $T \subset \tilde{T} \in L_\sigma$. Then, $T'$ lies in $L_\sigma$ and $T \subset T'$. Suppose $T \neq T'$. By Lemma 2.6, there is a factor-connected flag

$$ \mathcal{F}' = \{\emptyset =: T_0 \subset T_1 \subset \cdots \subset T_k \subset T_{k+1} := [n]\} $$

such that $\sigma = Q(M_\mathcal{F})$ and $T' = T_m$ for some $m$. Since $T \neq T'$ and $T$ is an order ideal of $P_\sigma$, we may choose $\mathcal{F}'$ so that $(T_m - T_{m-1}) \cap T = \emptyset$. Then $T \subset T_{m-1} \in L_\sigma$ which contradicts the fact that $T' = \cap \{\tilde{T} : T \subset \tilde{T} \in L_\sigma\}$ since $T_{m-1} \subsetneq T'$.
$\square$

The posets $P_\sigma$ coincide with the posets obtained from preposets corresponding to normal cones of the matroid base polytope $Q(M)$ (see [PRW]). Also, the poset $P_\sigma$ is the same as the poset $P_B$ of Billera, Jia and Reiner [BJR] if $\sigma$ is a vertex $e_B$.
## 3 The cd-index

In this section, we define the cd-index for Eulerian posets and give the relationship among cd-indices of polytopes when a polytope is cut by a hyperplane.

Let $P$ be a graded poset of rank $n + 1$ with the rank function $\rho$. For a subset $S$ of $[n]$, define $f_P(S)$ to be the number of chains of $P$ whose ranks are exactly given by the set $S$. The function $f_P: 2^{[n]} \to \mathbb{N}$ is called the flag $f$-vector of $P$. The flag $h$-vector is defined by the identity

$$h_P(S) = \sum_{T \subset S} (-1)^{|S-T|} \cdot f_P(T).$$

Since this identity is equivalent to the relation

$$f_P(S) = \sum_{T \subset S} h_P(T),$$

the flag $f$-vector and the flag $h$-vector contain the same information.

For a subset $S$ of $[n]$, define the noncommutative ab-monomial $u_S = u_1 u_2 \cdots u_n$, where

$$u_i = \begin{cases} \mathbf{a} & \text{if } i \notin S, \\ \mathbf{b} & \text{if } i \in S. \end{cases}$$

The ab-index of the poset $P$ is defined to be the sum

$$\Psi(P) = \sum_{S \subset [n]} h_P(S) \cdot u_S.$$

An alternative way of defining the ab-index is as follows. For a chain

$$c := \{\hat{0} < x_1 < \cdots < x_k < \hat{1}\},$$

we give a weight $w_P(c) = w(c) = z_1 \cdots z_n$, where

$$z_i = \begin{cases} \mathbf{b} & \text{if } i \in \{\rho(x_1), \dots, \rho(x_k)\}, \\ \mathbf{a} - \mathbf{b} & \text{otherwise.} \end{cases}$$

Define the ab-index of the poset $P$ to be the sum

$$\Psi(P) = \sum_c w(c),$$

where the sum is over all chains $c = \{\hat{0} < x_1 < \cdots < x_k < \hat{1}\}$ in $P$. Recall that a poset $P$ is Eulerian if its Möbius function $\mu$ is given by $\mu(x, y) = (-1)^{\rho(y) - \rho(x)}$ (see [Sta97] for more details). One important class of Eulerian posets is face lattices of convex polytopes (see [Lin71, Rot71]). It is known that the ab-index of an Eulerian poset $P$ can be written uniquely as a noncommutative polynomial of $c = \mathbf{a} + \mathbf{b}$ and $d = \mathbf{ab} + \mathbf{ba}$ (see [BK91]). When the ab-index can be written as a polynomial in $c$ and $d$, we call $\Psi(P)$ the cd-index of $P$. We will use the notation $\Psi(Q)$ for the cd-index of the face poset of a convex polytope $Q$.
Let $v$ be a vertex of a polytope $Q$ and let $l(x) = c$ be a supporting hyperplane of $Q$ defining $v$. The vertex figure $Q/v$ of $v$ is defined by

$$Q/v = Q \cap \{l(x) = c + \delta\}$$

where $\delta$ is an arbitrary small positive number. For a face $\sigma$ of $Q$, the face figure $Q/\sigma$ of $\sigma$ is defined by

$$Q/\sigma = (\dots ((Q/\sigma_0)/\sigma_1)\dots)/\sigma_k$$

where $\sigma_0 \subset \sigma_1 \subset \dots \subset \sigma_k = \sigma$ is a maximal chain with $\dim \sigma_i = i$. For faces $\sigma$ and $\tau$ of $Q$ with $\sigma \subset \tau$, the face lattice of the face figure $\tau/\sigma$ is the interval $[\sigma, \tau]$.

Ehrenborg and Readdy [ER98, Prop. 4.2] give formulas for the cd-indices of a pyramid, a prism and a bipyramid of a polytope.

**Proposition 3.1** Let $Q$ be a polytope. Then

$$\Psi(\text{Pyr}(Q)) = \frac{1}{2} \left[ \Psi(Q) \cdot \mathbf{c} + \mathbf{c} \cdot \Psi(Q) + \sum_{\sigma} \Psi(\sigma) \cdot \mathbf{d} \cdot \Psi(Q/\sigma) \right],$$

$$\Psi(\text{Prism}(Q)) = \Psi(Q) \cdot \mathbf{c} + \sum_{\sigma} \Psi(\sigma) \cdot \mathbf{d} \cdot \Psi(Q/\sigma),$$

$$\Psi(\text{Bipyr}(Q)) = \mathbf{c} \cdot \Psi(Q) + \sum_{\sigma} \Psi(\sigma) \cdot \mathbf{d} \cdot \Psi(Q/\sigma),$$

where the sum is over all proper faces $\sigma$ of $Q$.

Note that the cd-index of Bipyr($Q$) is obtained from the cd-index of Prism($Q$) because Bipyr($Q$) is the dual of the prism over the dual of $Q$ and the cd-index of the dual polytope is obtained by writing every ab-monomial in reverse order (see [ER98] for details).

Let $Q$ be a polytope in $\mathbb{R}^n$. Let $H$ be a hyperplane in $\mathbb{R}^n$ defined by $l(x) = c$ and $H^+$ (resp. $H^-$) be the closed halfspace $l(x) \ge c$ (resp. $l(x) \le c$). For simplicity, let $Q^+ := Q \cap H^+$, $Q^- = Q \cap H^-$, and $\hat{Q} := Q \cap H$. By carefully looking at chains in the face poset of $Q$, one can get the following theorem which provides the relationship among cd-indices of polytopes $Q$, $Q^+$, $Q^-$ and faces of $\hat{Q}$.

**Theorem 3.2** Let $Q$ be a polytope in $\mathbb{R}^n$ and $H$ be a hyperplane in $\mathbb{R}^n$. Then the following identity holds:

$$\Psi(Q) = \Psi(Q^+) + \Psi(Q^-) - \Psi(\hat{Q}) \cdot \mathbf{c} - \sum_{\sigma} \Psi(\hat{\sigma}) \cdot \mathbf{d} \cdot \Psi(\hat{Q}/\hat{\sigma}),$$

where the sum is over all proper faces $\sigma$ of $Q$ intersecting both open halfspaces $H^+ - H$ and $H^- - H$ nontrivially.

**Remark 3.3** The formula for the prism of a polytope in Proposition 3.1 is a special case of Theorem 3.2, since in this case

$$\begin{aligned} Q = \text{Prism}(Q') &\approx Q' \times [0, 0.5] = Q^- \\ &\approx Q' \times [0.5, 1] = Q^+ \end{aligned}$$

and $Q' \approx Q' \times \{0.5\} = \hat{Q}$.

Also, the formula for the pyramid of a polytope is obtained from Theorem 3.2 by considering $Q = \text{Bipyr}(Q')$ split by the hyperplane containing $Q'$: in this case, $Q^+ = Q^- = \text{Pyr}(Q')$ and there are no faces of Bipyr($Q'$) intersecting both open halfspaces nontrivially.
**Question 3.4** When $Q(M_1) \cup Q(M_2)$ is a hyperplane split of $Q(M)$ with a corresponding hyperplane $H$, can we restate Theorem 3.2 in terms of matroids?

If $M$ has rank 2, then one can restate Theorem 3.2 in terms of matroids (see Proposition 5.2 below), but Question 3.4 is open for higher ranks.

# 4 Hyperplane splits of a Matroid base polytope

In this section, we define hyperplane splits of a matroid base polytope and give conditions when they occur.

For a matroid $M$ on $[n]$, a hyperplane split of $Q(M)$ is a decomposition $Q(M) = Q(M_1) \cup Q(M_2)$ where

(i) $M_1$ and $M_2$ are matroids on $[n]$, and

(ii) the intersection $Q(M_1) \cap Q(M_2)$ is a proper face of both $Q(M_1)$ and $Q(M_2)$.

Let $\sum_{i=1}^n a_i x_i = b$ be an equation defining the corresponding hyperplane $H$. Since $Q(M_1) \cap Q(M_2)$ is a matroid base polytope on $H$ and its edges are parallel to $e_i - e_j$ for some $i \neq j$, the only constraints on the normal vector $(a_1, a_2, \dots, a_n)$ of $H$ are of the form $a_i = a_j$. Using the fact that $Q(M)$ is a subset of the $(n-1)$-simplex $\Delta_n$ defined by $\sum_{i=1}^n x_i = r(M)$ and scaling the right hand side $b$, one can assume that $H$ is defined by $\sum_{e \in S} x_e = k$ for some subset $S$ of $[n]$.

**Theorem 4.1** Let $M$ be a rank $r$ matroid on $[n]$ and $H$ be a hyperplane defined by $\sum_{e \in S} x_e = k$. Then $H$ gives a hyperplane split of $Q(M)$ if and only if the following conditions are satisfied:

(i) $r(S) > k$ and $r(S^c) > r - k$,

(ii) if $I_1$ and $I_2$ are $k$-element independent subsets of $S$ such that $(M/I_1)|_{S^c}$ and $(M/I_2)|_{S^c}$ have rank $r-k$, then $(M/I_1)|_{S^c} = (M/I_2)|_{S^c}$.

**Remark 4.2** Note that if $I$ is a $k$-element independent subset of $S$ and $J$ is an $(r-k)$-element independent subset of $S^c$, then $I$ is a base for $(M/J)|_S$ if and only if $J$ is a base for $(M/I)|_{S^c}$. Therefore one can see that the condition (ii) can be replaced with the following condition for $S^c$:

(ii') if $J_1$ and $J_2$ are $(r-k)$-element independent subsets of $S^c$ such that $(M/J_1)|_S$ and $(M/J_2)|_S$ have rank $k$, then $(M/J_1)|_S = (M/J_2)|_S$.

**Proof of Theorem 4.1:** Define $\mathcal{B}_k = \{B \in \mathcal{B}(M) : |B \cap S| = k\}$. We will show that the condition (ii) holds if and only if $\mathcal{B}_k$ is a collection of bases of some matroid. Then the assertion follows from Theorem 2.1.

Suppose that the condition (ii) is true. Choose any bases $B_1$ and $B_2$ in $\mathcal{B}_k$ and $x \in B_1 - B_2$ (without loss of generality, we may assume $x \in B_1 \cap S$). Let $I_i = B_i \cap S$ and $J_i = B_i - S$ for $i = 1, 2$. Then the condition (ii) implies that there is a base $B = I_2 \cup J_1$ in $\mathcal{B}_k$. Since $B_1, B \in \mathcal{B}$, there is $y \in B - B_1 \subset I_2 \subset B_2$ such that $B_3 = B - \{x\} \cup \{y\} \in \mathcal{B}$. Since $y \in I_2 \subset S$, $B_3 \in \mathcal{B}_k$. Thus $\mathcal{B}_k$ forms a collection of bases of a matroid.

Conversely suppose that $\mathcal{B}_k$ is a collection of bases of some matroid. Let $I_1$ and $I_2$ be $k$-element independent subsets of $S$ such that $(M/I_1)|_{S^c}$ and $(M/I_2)|_{S^c}$ have rank $r-k$. Choose $J_1 \in \mathcal{B}((M/I_1)|_{S^c})$
and $J_2 \in \mathcal{B}((M/I_2)|_{S^c})$. Then $B_1 = I_1 \cup J_1$ and $B_2 = I_2 \cup J_2$ are bases for $\mathcal{B}$. We claim that $I_2 \cup J_1$ is also a base of $M$: this implies $\mathcal{B}((M/I_1)|_{S^c}) \subset \mathcal{B}((M/I_2)|_{S^c})$ and (ii) follows by symmetry. We use induction on the size of $I_1 - I_2$.

**Base Case:** If $|I_1 - I_2| = 0$, we have $I_2 \cup J_1 = B_1 \in \mathcal{B}$.

**Inductive Step:** Suppose $|I_1 - I_2| = l$ for some $l \le k$. Choose an element $x \in I_1 - I_2 \subset B_1 - B_2$. Since $B_k$ forms a matroid, there exist $y \in I_2 - I_1$ such that $B_3 = B_1 - \{x\} \cup \{y\} \in B_k \subset \mathcal{B}$. Since $B_3 = (I_1 - \{x\} \cup \{y\}) \cup J_1$, we have $|(B_3 \cap S) - I_2| = l - 1$ and the induction hypothesis implies $I_2 \cup J_1 \in \mathcal{B}$. $\square$

# 5 Rank 2 matroids

In this section we apply Theorem 3.2 and Theorem 4.1 to the cd-index of a matroid base polytope when a matroid has rank 2.

A (loopless) rank 2 matroid $M$ on $[n]$ is determined up to isomorphism by the composition $\alpha(M)$ of $[n]$ that gives the sizes $\alpha_i$ of its parallelism classes. Let $\alpha := \alpha_1, \alpha_2, \dots, \alpha_k$ be a composition of $n$ with the length $l(\alpha) = k$ and let $M_\alpha$ be the corresponding rank 2 matroid on $[n]$. For two weak compositions (i.e., compositions allowing 0 as parts) $\alpha$ and $\beta$ of the same length, we define $\beta \le \alpha$ if $\beta_i \le \alpha_i$ for all $i = 1, 2, \dots, l(\alpha)$. Let $\bar{\beta}$ be the composition obtained from $\beta$ by deleting 0 parts. If $\alpha = (2, 4, 1, 6, 7)$ and $\beta = (1, 3, 0, 6, 3)$, then $\beta < \alpha$ and $\bar{\beta} = (1, 3, 6, 3)$.

When $M$ has rank 2, Theorem 4.1 can be rephrased in the following way.

**Corollary 5.1** Let $M$ be a rank 2 matroid on $[n]$ and $H$ be a hyperplane defined by $\sum_{e \in S} x_e = 1$. Then $H$ gives a hyperplane split of $Q(M)$ if and only if $S$ and $S^c$ are both unions of at least two parallelism classes.

After the relabeling, one may assume that $M$ has parallelism classes $P_1, P_2, \dots, P_k$ and $S = \cup_{i=1}^m P_i$ for some $m$. In this case, one can restate Theorem 3.2 in terms of matroids as follows.

**Proposition 5.2** Let $M$ be a rank 2 matroid on $[n]$ with at least four parallelism classes $P_1, P_2, \dots, P_k$ and $S = \cup_{i=1}^m P_i$ for some $m$ such that $2 \le m \le k - 2$. Then the hyperplane $H$ defined by $\sum_{e \in S} x_e = 1$ gives a hyperplane split $Q(M_1) \cup Q(M_2)$ of $Q(M)$ where $M_1$ is a matroid with parallelism classes $S, P_{m+1}, \dots, P_k$ and $M_2$ is a matroid whose parallelism classes are $P_1, \dots, P_m, S^c$. Moreover,

$$ \Psi(Q(M)) = \Psi(Q(M_1)) + \Psi(Q(M_2)) - \Psi(\Delta_{|S|} \times \Delta_{n-|S|}) \cdot \mathbf{c} - \sum_{T} \Psi(Q(M|_T)) \cdot \mathbf{d} \cdot \Psi(\Delta_{n-|T|}), $$

where the sum in the second line runs over all proper subsets $T$ of $[n]$ such that $M|_T$ has at least four parallelism classes, at least two of which are subsets of $S$ and $S^c$ respectively.

**Proof:** Note that there is no flacet of $Q(M)$ which intersects both open halfspace given by $H$ nontrivially since every flacet of $Q(M)$ corresponds to a base set of the form

$$ \{B \in \mathcal{B}(M) : |B \cap P_i| = 1\} $$

for some $i$. If $\sigma$ is a face of $Q(M)$ which has nonempty intersection with both open halfspaces given by $H$, then $\sigma$ is the intersection of some facets of $Q(M)$ which are not flacets. Since each facet of $Q(M)$
which is not a flacet corresponds to the deletion of an element of $[n]$, $\sigma$ corresponds to a matroid $M|_T$ for some subset $T$ of $[n]$. Also, $\sigma$ has nonempty intersection with both open halfspaces given by $H$ if and only if $M|_T$ has at least four parallelism classes, at least two of which are subsets of $S$ and $S^c$ respectively. Now, the result follows from Theorem 3.2. $\square$

The following proposition, which is obtained from Corollary 5.1 and Proposition 5.2, expresses the cd-index of a matroid base polytope of a rank 2 matroid $M$ with composition $\alpha(M) = \alpha$ in terms of cd-indices of matroid base polytopes of matroids corresponding to compositions of length $\le 3$. For simplicity, we use the following notations:

$$ \lambda(\alpha, i) = \left( \sum_{j=1}^{i-1} \alpha_j, \alpha_i, \sum_{j=i+1}^{l(\alpha)} \alpha_j \right) \quad \text{for } 2 \le i \le l(\alpha) - 1, $$

$$ \mu(\alpha, i) = \left( \sum_{j=1}^{i} \alpha_j, \sum_{j=i+1}^{l(\alpha)} \alpha_j \right) \quad \text{for } 1 \le i \le l(\alpha) - 1. $$

For example, if $\alpha = (2, 4, 1, 6, 7)$, then $\lambda(\alpha, 4) = (7, 6, 7)$ and $\mu(\alpha, 4) = (13, 7)$.

**Proposition 5.3** Let $\alpha$ be a composition of $n$ with at least three parts and $M_\alpha$ be the corresponding rank 2 matroid on $[n]$. Then the cd-index of $Q(M_\alpha)$ can be expressed as follows:

$$ \Psi(Q(M_{\alpha})) = \sum_{i=2}^{l(\alpha)-1} \Psi(Q(M_{\lambda(\alpha,i)})) - \left( \sum_{i=2}^{l(\alpha)-2} \Psi(\Delta_{\mu(\alpha,i)_1} \times \Delta_{\mu(\alpha,i)_2}) \right) \cdot \mathbf{c} \\ - \sum_{\substack{\beta < \alpha \\ l(\beta) \ge 4}} \prod_{j=1}^{l(\alpha)} \binom{\alpha_j}{\beta_j} \left( \sum_{i=2}^{l(\bar{\beta})-2} \Psi(\Delta_{\mu(\bar{\beta},i)_1} \times \Delta_{\mu(\bar{\beta},i)_2}) \right) \cdot \mathbf{d} \cdot \Psi(\Delta_{n-|\bar{\beta}|}). $$

Purtill [Pur93] shows that the cd-index of the $(n-1)$-simplex $\Delta_n$ is the $(n+1)$-st André polynomial. Using the formula for the cd-index of a product of two polytopes given by Ehrenborg and Readdy [ER98], one can calculate the second and the third terms in Proposition 5.3. We still don't have a simple interpretation for the cd-index for $Q(M_\alpha)$ when $\alpha$ has three parts.

## References

[AK06] Federico Ardila and Caroline J. Klivans. The Bergman complex of a matroid and phylogenetic trees. *J. Combin. Theory Ser. B*, 96(1):38–49, 2006.

[BER97] Louis J. Billera, Richard Ehrenborg, and Margaret Readdy. The c-2d-index of oriented matroids. *J. Combin. Theory Ser. A*, 80(1):79–105, 1997.

[BER98] Louis J. Billera, Richard Ehrenborg, and Margaret Readdy. The cd-index of zonotopes and arrangements. In *Mathematical essays in honor of Gian-Carlo Rota* (Cambridge, MA, 1996), volume 161 of *Progr. Math.*, pages 23–40. Birkhäuser Boston, Boston, MA, 1998.
[BJR] Louis J. Billera, Ning Jia, and Victor Reiner. A quasisymmetric function for matroids. arXiv:math.CO/0606646.

[BK91] Margaret M. Bayer and Andrew Klapper. A new index for polytopes. *Discrete Comput. Geom.*, 6(1):33–47, 1991.

[Edm03] Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In *Combinatorial optimization—Eureka, you shrink!,* volume 2570 of *Lecture Notes in Comput. Sci.*, pages 11–26. Springer, Berlin, 2003.

[ER98] Richard Ehrenborg and Margaret Readdy. Coproducts and the *cd*-index. *J. Algebraic Combin.*, 8(3):273–299, 1998.

[FS05] Eva Maria Feichtner and Bernd Sturmfels. Matroid polytopes, nested sets and Bergman fans. *Port. Math. (N.S.)*, 62(4):437–468, 2005.

[GGMS87] I. M. Gel'fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova. Combinatorial geometries, convex polyhedra, and Schubert cells. *Adv. in Math.*, 63(3):301–316, 1987.

[Lin71] Bernt Lindström. On the realization of convex polytopes, Euler's formula and Möbius functions. *Aequationes Math.*, 6:235–240, 1971.

[Ox192] James G. Oxley. *Matroid theory*. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1992.

[PRW] Alexander Postnikov, Victor Reiner, and Lauren Williams. Faces of generalized permutohedra. arXiv:math.CO/0609184.

[Pur93] Mark Purtill. André permutations, lexicographic shellability and the *cd*-index of a convex polytope. *Trans. Amer. Math. Soc.*, 338(1):77–104, 1993.

[Rot71] Gian-Carlo Rota. On the combinatorics of the Euler characteristic. In *Studies in Pure Mathematics (Presented to Richard Rado)*, pages 221–233. Academic Press, London, 1971.

[Sta97] Richard P. Stanley. *Enumerative combinatorics. Vol. 1*, volume 49 of *Cambridge Studies in Advanced Mathematics*. Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original.