Generalized permutohedra, h-vectors of
cotransversal matroids and pure
O-sequences (extended abstract)

Suho Oh<fnref n="1" />

**Abstract.** Stanley has conjectured that the h-vector of a matroid complex is a pure O-sequence. We will prove this for cotransversal matroids by using generalized permutohedra. We construct a bijection between lattice points inside a *r*-dimensional convex polytope and bases of a rank *r* transversal matroid.

**Résumé.** Stanley a conjecturé que le h-vecteur d'un complexe matroide est une pure O-séquence. Nous allons le prouver pour les matroides cotransversal en utilisant generalized permutohedra. Nous construisons une bijection entre les points du réseau intérieur d'un polytope convexe *r*-dimensions et les bases d'un matroide transversal *r*-rang.

**Keywords:** generalized permutohedra, Stanley's conjecture, h-vector, matroid, cotransversal, bipartite, matching, polytope, pure O-sequence

# 1 Introduction

Matroids, simplicial complexes and their h-vectors are all interesting objects that are of great interest in algebraic combinatorics and combinatorial commutative algebra. An *order ideal* is a finite collection $X$ of monomials such that, whenever $M \in X$ and $N$ divides $M$, then $N \in X$. If all maximal monomials of $X$ have the same degree, then $X$ is pure. A pure $O$-sequence is the vector, $h = (h_0 = 1, h_1, ..., h_t)$, counting the monomials of $X$ in each degree. The following conjecture by Stanley has motivated a great deal of research on h-vectors of matroid complexes:

**Conjecture 1.1** The *h-vector of a matroid is a pure O-sequence*.

The above conjecture has been proven for cographic matroids by both Merino (2001) and Chari (1997). It also has been proven for lattice-path matroids by Schweig (2010). Lattice path matroids are special cases of cotransversal matroids, and we will prove the conjecture for cotransversal matroids. We would also like to note that there has been plenty of interesting results related to this conjecture: Boij et al. (2010), Chari (1995), Hausel and Sturmfels (2002), Hibi (1989), Stokes (2009).

We prove the conjecture for cotransversal matroids by associating a polytope to each transversal matroid called *transversalhedron*. This polytope is closely related to a particular *generalized permutohedron*. The lattice points inside this polytope (excluding the points on the coordinate hyperplanes $x_i = 0$) will

<footnote n="1">¹Department of Mathematics, Massachusetts Institute of Technology, MA, USA</footnote>
be in bijection with bases of the matroid, and the set of lattice points inside this polytope will naturally
induce the pure order ideal we are looking for.

In Section 2, we will go over properties of transversal matroids. In Section 3, we go over properties of generalized permutohedra. In Section 4, we define the transversalhedra and “good” lattice points inside each Minkowski cell. We also give a bijection between bases of $\mathcal{M}$ and “good” lattice points inside the corresponding transversalhedron. In Section 5, we state our main result and give an example.

This is an extended abstract. Proofs and more details are given in Oh (2010).

## 2 Preliminaries on matroids

In this Section, we will provide some notations and tools on transversal matroids that we are going to use throughout the paper. We will assume basic familiarity with matroid theory. Throughout the paper, unless stated otherwise, a matroid $\mathcal{M}$ will be a rank $r$ matroid over the ground set $[n] := \{1, \dots, n\}$.

An element $i$ of a base $B$ is **internally active** if $(B \setminus i) \cup j$ is not a base for any $j < i$. An element $e \notin B$ is **externally active** if $(B \cup e) \setminus j$ is a not a base for all $j > e$. Given a base $B$, we denote $ep_{\mathcal{M}}(B)$ to be the number of elements $e \notin B$ that are not externally active. We call such elements as **externally passive** elements of $B$.

The h-vector of a matroid is defined as the h-vector of its corresponding independent complex. Rather than working with the definition of the h-vector directly, we will use the following characterization:

**Lemma 2.1 (Björner (1992))** Let $(h_0, \dots, h_r)$ be the h-vector of a matroid $\mathcal{M}$. For $0 \le i \le r$, $h_i$ is the number of bases of $\mathcal{M}$ with $r-i$ internally active elements.

**Remark 2.2** The way we will view $h_i$ in this paper is to count the number of bases in the dual-matroid of $\mathcal{M}$ with $i$ externally passive elements.

Our main result in this paper is that the *h-vector* of a cotransversal matroid is a pure *O*-sequence.

Now let's go over the basics of **transversal matroids**. We are going to be looking at a subgraph of the complete bipartite graph $K_{n,r}$. Denote the vertices on the left with $S = \{1, \dots, n\}$ and on the right with $J = \{1, \dots, r\}$. Let $\mathcal{A}$ be a family $(A_1, A_2, \dots, A_r)$ of subsets of the set $S$. Then the bipartite graph $\mathcal{G}(\mathcal{A})$ associated with $\mathcal{A}$ has vertex set $S \cup J$ and its edge set is $\{(x, j) | x \in S, j \in J \text{ and } x \in A_j\}$. Given a subgraph $T$ of this graph, let $\mathrm{lt}(T)$ denote the set of left vertices covered by edges of $T$, and let $\mathrm{rt}(T)$ denote the set of right vertices covered by edges of $T$. So we would have $\mathrm{lt}(T) \subseteq S$ and $\mathrm{rt}(T) \subseteq J$. The collection of $\mathrm{lt}(T)$ for all maximal matchings of $\mathcal{G}(\mathcal{A})$ form the set of bases of a matroid. We denote this matroid by $\mathcal{M}(\mathcal{A})$. If $\mathcal{M}$ is an arbitrary matroid and $\mathcal{M} \cong \mathcal{M}(\mathcal{A})$ for some family $\mathcal{A}$ of sets, then we call $\mathcal{M}$ a transversal matroid and $\mathcal{A}$ a **presentation** of $\mathcal{M}$. The sets $A_1, \dots, A_m$ are called **members**.

In Figure 1, we have a presentation of a family $(\{1, 2, 6, 7, 8, 9\}, \{3, 4, 5, 6, 7, 8, 9\})$.

The **type** of $i \in S$ will be defined as the set of vertices of $J$ connected to $i$ in $\mathcal{G}(\mathcal{A})$, and will be denoted by $\phi(i)$. Using this definition, $C_{\mathcal{M},I} \subseteq S$ is defined to be collection of elements of $S$ that have type $I$. We will denote $l_{\mathcal{M},I}$ to be the cardinality of $C_{\mathcal{M},I}$. Type of a subset $H \subseteq S$ will be given as the multiset obtained by collecting the types for each element of $H$, and will be denoted by $\phi(H)$. We put a total ordering on subsets $I \subseteq [r]$ by the following rule:

1. if $|I| < |I'|$, then $I \prec I'$ and,

2. if $|I| = |I'|$, then $I \prec I'$ if $I$ is smaller in lexicographical order.
<figure><img src="image_1.png" /><figcaption>Fig. 1 – Bipartite graph defining $\mathcal{M}$</figcaption></figure>

Then we relabel the set $S$ such that if $\phi(i) \prec \phi(j)$ then $i < j$. Denote the sets $I \subseteq [r]$ that satisfy $l_{\mathcal{M},I} > 0$ as $I_1 \prec I_2 \prec \cdots \prec I_m$. Then we can express the type of each subset $H \subseteq S$ as a sequence $(a_1, \cdots, a_m)$, where $a_i$ encodes the number of times $I_i$ appears in the collection. This will be called the **type sequence** of $H$. In case of Figure 1, we would have $I_1 = \{1\}, I_2 = \{2\}, I_3 = \{1, 2\}$. The type sequence of $\{4, 8\}$ would be $(0, 1, 1)$, since $\phi(4) = \{2\}$ and $\phi(8) = \{1, 2\}$.

For notational convenience, we will denote a set $I$ occurring $q$-times in a collection by $I^q$. For example, the collection $\{{\{1\}, \{1\}, \{1\}, \{2\}, \{2\}, \{1, 2\}, \{1, 2\}\}}$ will be expressed as $\{{\{1\}^3, \{2\}^2, \{1, 2\}^2}\}$. Since we are viewing these collections as multisets, whenever we do a set minus, we will delete only one occurrence of $I$ from the collection per times $I$ appears in the set being negated with. For example, $\{{\{1\}^3, \{2\}^2, \{1, 2\}^2}\} \setminus \{{\{1\}, \{2\}^2}\} = \{{\{1\}^2, \{1, 2\}^2}\}$.

**Definition 2.3** Given a sequence $a = (a_1, \cdots, a_m)$, we denote $\mathcal{I}^a$ to be the collection $I_1^{a_1}, \cdots, I_m^{a_m}$. If $\mathcal{I}^a$ satisfies the Hall's condition, (i.e. if union of any $t$ sets of the collection has cardinality at least $t$), then we say that $a$ is **valid**. We will say that $a$ is **maximal** if $\sum_i a_i = r$. If $a$ is a type sequence of a base of $\mathcal{M}$, then it is called the **base sequence** of $\mathcal{M}$.

A maximal valid sequence is a base sequence of $\mathcal{M}$ if and only if $a_i \le l_{\mathcal{M},I_i}$ for all $i$. Since the type sequences and their corresponding collections carry the same information, we will say that a type of a subset is valid or maximal if its corresponding sequence is.

Now let's fix a base $B$ of $\mathcal{M}$ and study its externally passive elements. We define $ep_{\mathcal{M}}(\phi(B))$ to be the minimum among all bases having the same type. In other words, we look at the number of externally passive elements in the first base having type $\phi(B)$. We also define $ep_{\mathcal{M}}^{\phi(B)}(B)$ to be $ep_{\mathcal{M}}(B) - ep_{\mathcal{M}}(\phi(B))$. So we can rewrite this as:

$$ep_{\mathcal{M}}(B) = ep_{\mathcal{M}}(\phi(B)) + ep_{\mathcal{M}}^{\phi(B)}(B).$$
Let's look at the example given in Figure 1. We saw that base $\{4, 8\}$ has type sequence $(0, 1, 1)$. If we look at Table 1, we can see that $ep_M(\{4, 8\}) = 5$ and that $\{3, 6\}$ also has the same type sequence. So in this case, we would have $ep_M(\phi(\{4, 8\})) = ep_M(\{3, 6\}) = 2$ and hence $ep_M^{\phi(\{4,8\})}(\{4, 8\}) = 5 - 2 = 3$. We will define $EP_M(\phi(B))$ as the collection of $I \subseteq [r]$ where there exists some $I' \subseteq [r]$ such that:

* $I \prec I'$ and

* $\phi(B) \setminus \{I'\} \cup \{I\}$ is a maximal valid type.

Given a base $B \in \mathcal{M}$, the element $e \notin B$ is an externally passive element only if $\phi(e)$ is an element of $EP_M(\phi(B))$.

**Lemma 2.4** Let $\mathcal{M}$ be a transversal matroid and $B$ be the type sequence for a base $B \in \mathcal{M}$. We can compute $ep_{\mathcal{M}}(\phi(B))$ and $ep_{\mathcal{M}}^{\phi(B)}(B)$ as:

* first set both of them to 0,

* for each $I_i \in EP_M(\phi(B))$, add $l_{M,I_i} - a_i$ to $ep_M(\phi(B))$ and 0 to $ep_M^{\phi(B)}(B)$,

* for each $I_i \notin EP_M(\phi(B))$, add 0 to $ep_M(\phi(B))$ and $s - a_i$ to $ep_M^{\phi(B)}(B)$, where the largest element of $B \cap C_{M,I_i}$ is the s-th element in $C_{M,I_i}$.

**Corollary 2.5** Let $\mathcal{M}$ be a transversal matroid and $B \in \mathcal{M}$. Then
$$ ep_{\mathcal{M}}(B) = \sum_{I_i \in EP_{\mathcal{M}}(I^a)} (l_{\mathcal{M},I_i} - a_i) + ep_{\mathcal{M}}^{\phi(B)}(B). $$

Let's look back at the example from Figure 1 and Table 1. $EP_M(\phi(\{4, 8\}))$ is going to be $\{I_1\}$. So $ep_M(\phi(\{4, 8\})) = l_{M,I_1} - a_1 = 2 - 0 = 2$, which coincides with our previous observation that $ep_M(\phi(\{4, 8\})) = ep_M(\{3, 6\}) = 2$. Since 4 is the 2nd element of $C_{M,I_2}$ and 8 is the 3rd element of $C_{M,I_3}$, we have $ep_M^{\phi(\{4,8\})}(\{4, 8\}) = (2 - 1) + (3 - 1) = 3$.

# 3 Generalized permutohedra

In this Section, we review the generalized permutohedra. The contents related to generalized permutohedra follows that of Postnikov (2009).

**Definition 3.1 (Postnikov (2009))** Let $d$ be the dimension of the Minkowski sum $P_1 + \cdots + P_m$. A Minkowski cell in this sum is a polytope $B_1 + \cdots + B_m$ of dimension $d$ where $B_i$ is the convex hull of some subset of vertices of $P_i$. A mixed subdivision of the sum is the decomposition into union of Minkowski cells such that interSection of any two cells is their common face. A mixed subdivision is fine if for all cells $B_1 + \cdots + B_m$, all $B_i$ are simplices and $\sum \dim B_i = d$.

**Remark 3.2** All mixed subdivisions in our paper, unless otherwise stated, will be referring to fine mixed subdivisions.

We will use the term *Minkowski face* to be the sum $B_1 + \cdots + B_m$ that has dimension $\le d$. Let $G \subseteq K_{m,r+1}$ be a bipartite graph with no isolated vertices. We label the vertices of $G$ by $1, \dots, m, 0', 1', \dots, r'$ and call $1, \dots, m$ the **left vertices** and $[0, r'] := 0', 1', \dots, r'$ the **right vertices**. Let us associate this graph
with the collection $\mathcal{I}_G$ of subsets $I_1, \dots, I_m \subseteq [0, r] := \{0, 1, \dots, r\}$ such that $j \in I_i$ if and only if $(i, j')$ is an edge of $G$. The generalized permutohedron $P_G(y_1, \dots, y_m)$ is defined as the Minkowski sum

$$P_G(y_1, \dots, y_m) = y_1 \Delta'_{I_1} + \dots + y_m \Delta'_{I_m},$$

where $\Delta'_I$ is defined to be the convex hull of points $e_i$ for $i \in I$ and $y_i$ are nonnegative integers.

**Proposition 3.3 (Postnikov (2009))** Let $H_1, \dots, H_r \subset [0, r]$. The following conditions are equivalent:

1. For any distinct $i_1, \dots, i_k$, we have $|H_{i_1} \cup \dots \cup H_{i_k}| \ge k + 1$.

2. For any $j \in [0, r]$, there is a system of distinct representatives in $H_1, \dots, H_r$ that avoids $j$.

The above condition is called the **dragon marriage condition**.

**Definition 3.4 (Postnikov (2009))** Let us say that a sequence of nonnegative integers $(a_1, \dots, a_m)$ is a G-draconian sequence if $\sum a_i = r$ and, for any subset $\{i_1 < \dots < i_k\} \subseteq [m]$, we have $|I_{i_1} \cup \dots \cup I_{i_k}| \ge a_{i_1} + \dots + a_{i_k} + 1$. Equivalently, if the sequence $I_1^{a_1}, \dots, I_m^{a_m}$ satisfies the dragon marriage condition.

One important property of generalized permutohedra is that fine Minkowski cells can be described by spanning trees of $G$. For a sequence of nonempty subsets $\mathcal{J} = (J_1, \dots, J_m)$, let $G_{\mathcal{J}}$ be the graph with edges $(i, j')$ for $j \in J_i$.

**Lemma 3.5 (Postnikov (2009))** Each fine mixed cell in a mixed subdivision of $P_G(y_1, \dots, y_m)$ has the form $y_1 \Delta'_{J_1} + \dots y_m \Delta'_{J_m}$, for some sequence of nonempty subsets $\mathcal{J} = (J_1, \dots, J_m)$ in $[0, r]$ such that $G_{\mathcal{J}}$ is a spanning tree of $G$.

Given a spanning tree $T \subseteq G$, we denote $\prod'_T$ to be the corresponding Minkowski cell. We can say a bit more about the lattice points in each $\prod'_T$:

**Proposition 3.6 (Postnikov (2009))** Any lattice point of a fine Minkowski cell $\prod'_{G_{\mathcal{J}}}$ in $P_G(y_1, \dots, y_m)$ is of form $p_1 + \dots + p_m$ where $p_i$ is a lattice point in $y_i \Delta'_{J_i}$.

Given any subgraph $T$ in $G$, define the **left degree vector** $\text{ld}(T) = (d_1, \dots, d_m)$ and the **right degree vector** $\text{rd}(T) = (d'_0, \dots, d'_r)$ where $d_i, d'_j$ is the degree of the vertex $i, j'$ in $T$ minus 1. The following proposition is stated in the proof of Theorem 11.3 in Postnikov (2009).

**Proposition 3.7 (Postnikov (2009))** Let us fix a fine mixed subdivision $\{\prod'_{T_1}, \dots, \prod'_{T_s}\}$ of the polytope $P_G(y_1, \dots, y_m)$. Then the map $\prod'_{T_i} \to \text{ld}(T_i)$ is a bijection between fine cells $\prod'_{T_i}$ in this subdivision and G-draconian sequences.

For two spanning trees $T$ and $T'$ of $G$, let $U(T, T')$ be the directed graph which is the union of edges of $T$ and $T'$ with edges of $T$ oriented from left to right and edges of $T'$ oriented from right to left. A directed cycle is a sequence of directed edges $(i_1, i_2), (i_2, i_3), \dots, (i_{k-1}, i_k), (i_k, i_1)$ such that all $i_1, \dots, i_k$ are distinct.

**Lemma 3.8 (Postnikov (2009))** For two spanning trees $T, T'$, the corresponding Minkowski cells can be in the same mixed subdivision only if $U(T, T')$ has no directed cycles of length $\ge 4$.

We will say that $T, T'$ are **compatible** if it satisfies the condition of Lemma 3.8, and **incompatible** if not.
# 4 Transversalhedra

In this Section, we construct a polytope from a transversal matroid. The lattice points inside this polytope (excluding the coordinate hyperplanes) will give a pure order ideal that we are looking for in Stanley's conjecture. We define the **transversalhedron** of $\mathcal{M}$ to be

$$P_{\mathcal{M}} = \sum_{I \subseteq [r]} l_{\mathcal{M},I} \Delta_{\{0\} \cup I},$$

where $\Delta_J$ for $J \subseteq [0, r]$ is defined as:

* if $0 \in J$, the convex hull of origin and $e_i$ for $i \in J \cap \{1, \dots, r\}$,

* if $0 \notin J$, the convex hull of $e_i$ for $i \in J \cap \{1, \dots, r\}$.

Under the projection map that sends values of the 0-coordinate to 0, the generalized permutohedron $P'_{\mathcal{M}} := \sum_{I \subseteq [r]} l_{\mathcal{M},I} \Delta'_{\{0\} \cup I}$ gets sent to a transversalhedron. This projection map is actually a bijection between (lattice) points $(x_0, x_1, \dots, x_r)$ of $P'_{\mathcal{M}}$ and $(x_1, \dots, x_r)$ of $P_{\mathcal{M}}$ since $P'_{\mathcal{M}}$ is on a hyperplane $x_0 + x_1 + \dots + x_r = n$.

Denote the bipartite graph defining $\mathcal{M}$ to be $G_{\mathcal{M}}$. Identify all vertices on the left side of $G_{\mathcal{M}}$ having the same type, and add a vertex to the right side labeled 0 that is connected to all vertices of the left side, to get a bipartite graph $\overline{G_{\mathcal{M}}}$. Recall that we relabeled the ground set of $\mathcal{M}$ such that if $\phi(i) < \phi(j)$, then we have $i < j$. The $i$-th vertex on the left side is associated with $i$-th subset $I$ that has $l_{\mathcal{M},I} > 0$ with respect to ordering on all subsets of $[r]$ given in Section 2.

<figure><img src="image_2.png" /><figcaption>**Fig. 2** – $\overline{G_{\mathcal{M}}}$ corresponding to the bipartite graph given in Figure 1.</figcaption></figure>

Recall that each fine Minkowski cell $\prod'_{(\overline{G_{\mathcal{M}}})_J}$ of $P'_{\mathcal{M}}$ can be described by $l_{\mathcal{M},I_1} \Delta'_{J_1} + \dots + l_{\mathcal{M},I_m} \Delta'_{J_m}$. It corresponds to a fine Minkowski cell in $P_{\mathcal{M}}$ given by $l_{\mathcal{M},I_1} \Delta_{J_1} + \dots + l_{\mathcal{M},I_m} \Delta_{J_m}$, and we will denote this cell by $\prod_J$.

**Lemma 4.1** *Maximal valid type sequences of $\mathcal{M}$ are exactly $\overline{G_{\mathcal{M}}}$-draconian sequences.*

So we immediately get the following result by using Proposition 3.7.

**Corollary 4.2** Let us fix a fine mixed subdivision of $P_{\mathcal{M}}$. Then the fine Minkowski cells of this subdivision are in bijection with the maximal type sequences of $\mathcal{M}$.
Using this result, we define the **type** of a fine Minkowski cell as $\mathcal{I}^a$, where $a$ is the $\overline{G_M}$-draconian sequence of the cell. Since the polytope $P_M$ contains the origin and the coordinate hyperplanes at the boundary, if we define the **degree** of a lattice point to be the sum of its coordinates, the degree is nonnegative for all lattice points inside the polytope. We define $x_I$ to be $\sum_{i \in I} x_i$. The facets of this polytope are given by the coordinate hyperplanes $x_i = 0$ and hyperplanes $x_I = \sum_{I \cap H \neq \emptyset} l_{M,H}$. We will refer to facets that do not come from coordinate hyperplanes as the **nontrivial boundary** of the polytope.

Let's study the lattice points inside the Minkowski cells of $P_M$. We have the following result by Proposition 3.6.

**Corollary 4.3** Let us fix a fine mixed subdivision of $P_M$. Then any lattice point of a fine Minkowski cell $\prod_J$ is of form $p_1 + \cdots + p_m$ where $p_i$ is a lattice point of $l_{M,I_i} \Delta_{J_i}$.

Inside the mixed subdivision of our transversalhedron, some lattice points are contained in several Minkowski cells. We want to decide which cell takes ownership.

**Definition 4.4** Let $\prod_J$ be a fine mixed cell of a transversalhedron. We will say that a lattice point of $l_{\Delta_{J_i}}$ is **good** if it satisfies:

* when $0 \in J_i$, it is not on $l_{\Delta_{J_i} \setminus \{j\}}$ for $j \in J_i \setminus \{0\}$,

* when $0 \notin J_i$, it is not on $l_{\Delta_{J_i} \setminus \{j\}}$ for $j \in J_i \setminus \{t_{i,0}\}$, where $t_{i,0}$ is the unique element of $J_i$ such that any path from an element of $J_i$ to 0 must pass through $t_{i,0}$.

Using the notations of the previous corollary, we call a lattice point in a cell $\prod_J$ to be good if for all $i$, $p_i$ is a good lattice point of $l_{\Delta_{J_i}}$.

A fine Minkowski cell, whose type $\mathcal{I}^a$ is not a base type of $M$ (happens when $a_i > l_{\Delta_{J_i}}$ for some $i$), does not contain any good lattice points.

**Proposition 4.5** Fix a fine mixed subdivision in $P_M$. Let $p$ be a lattice point of $P_M$ not on any of the coordinate hyperplanes $x_i = 0$. Then $p$ is a good lattice point of exactly one fine Minkowski cell.

Hence regardless of which fine mixed subdivision we use, the good lattice points of $P_M$ are going to be the lattice points not on any of the coordinate hyperplanes.

Assuming we are given a fine mixed subdivision of $P_M$, we will now construct a bijection between bases of $M$ of type $\mathcal{I}^a$ and good lattice points in fine Minkowski cells of $P_M$ of type $\mathcal{I}^a$. The number of good lattice points in each $l_{\Delta_{J_i}}$ is equal to $\binom{|C_{M,I_i}|}{|J_i|-1}$. So we can construct a bijection between good lattice points of $l_{\Delta_{J_i}}$ and $\binom{C_{M,I_i}}{|J_i|-1}$ for each $i$. This determines a bijection between good lattice points of cells of type $\mathcal{I}^a$ and bases of type $\mathcal{I}^a$ for each maximal valid type $a$, and it results in a bijection between good lattice points of $P_M$ and bases of $M$. Figure 3 shows an example of such construction. Given such a bijection, we can label each good lattice point of $P_M$ with $B \in M$ and define $d_M(B)$ as the degree of the corresponding lattice point.

The main goal we want to achieve with our bijection is to relate $ep_M(B)$ with $d_M(B)$. The key idea is to divide $d_M(B)$ into two parts as we did for $ep_M(B)$. Let's define $d_M(\phi(B))$ as the minimum degree of all good lattice points inside the cell, of which the lattice point labeled $B$ is a good lattice point inside. And let's define $d_M^{(B)}(B)$ as $d_M(B) - d_M(\phi(B))$. Then we can write:

$$d_M(B) = d_M(\phi(B)) + d_M^{(B)}(B).$$
<figure><img src="image_3.png" /><figcaption>Fig. 3 – How the bijection between bases of $\mathcal{M}$ and good lattice points of $P_{\mathcal{M}}$ is constructed.</figcaption></figure>

**Lemma 4.6** Let $\mathcal{M}$ be a transversal matroid, $P_{\mathcal{M}}$ the corresponding transversalhedron and fix a fine mixed subdivision of $P_{\mathcal{M}}$. Then there is a bijection between good lattice points in cell $\prod_{J}^{\mathcal{I}^a}$ of type $\mathcal{I}^a$ (we have $a = (|J_1| - 1, \cdots, |J_m| - 1)$) and bases of type $\mathcal{I}^a$ such that we can compute $d_{\mathcal{M}}(\phi(B))$ and $d_{\mathcal{M}}^{\phi(B)}(B)$ as:

* first set both of them to 0,

* for each $J_i$ such that $0 \notin J_i$, add $l_{\mathcal{M},I_i}$ to $d_{\mathcal{M}}(\phi(B))$ and $0$ to $d_{\mathcal{M}}^{\phi(B)}(B)$,

* for each $J_i$ such that $0 \in J_i$, add $a_i$ to $d_{\mathcal{M}}(\phi(B))$ and $s-a_i$ to $d_{\mathcal{M}}^{\phi(B)}(B)$, where the largest element of $B \cap C_{\mathcal{M},I_i}$ is the $s$-th element in $C_{\mathcal{M},I_i}$.

Let's look at an example. The transversalhedron for $\mathcal{M}$ in Figure 1 is given in Figure 5. Take a look at cell with type sequence (0, 1, 1). The corresponding sum $2\Delta_{J_1} + 3\Delta_{J_2} + 4\Delta_{J_3}$ and the corresponding spanning tree of $\overline{G_{\mathcal{M}}}$ is given in Figure 4. Each good lattice point of the cell corresponds to choosing a good lattice point in $2\Delta_{J_1}, 3\Delta_{J_2}, 4\Delta_{J_3}$. A base of this type corresponds to choosing 0, 1, 1 element from $C_{\mathcal{M},I_1}, C_{\mathcal{M},I_2}, C_{\mathcal{M},I_3}$. Now let's take a look at $d_{\mathcal{M}}(\{4, 8\}) = 7$. Using the above lemma, we can check that $d_{\mathcal{M}}(\phi(\{4, 8\})) = d_{\mathcal{M}}(\{3, 6\}) = l_{\mathcal{M},I_1} + a_2 + a_3 = 4$ and $d_{\mathcal{M}}^{\phi(\{4,8\})}(\{4, 8\}) = 0 + (2-1) + (3-1) = 3$ and their sum equals 7.
<figure><img src="image_4.png" /><figcaption>Fig. 4 - A cell of type (0, 1, 1), its spanning tree and the corresponding sum $2\Delta_{J_1} + 3\Delta_{J_2} + 4\Delta_{J_3}$.</figcaption></figure>

# 5 Main Result

The degree sequence obtained by the externally passive degree $ep_M$ is the h-vector of $M^*$ (Remark 2.2). The degree sequence obtained by the lattice degree $d_M$ is by construction a pure O-sequence. Showing that these two degree sequences are the same would imply Stanley's conjecture in the cotransversal case. So our goal is to show that there is a bijection between bases of $M$ and good lattice points in $P_M$ such that $ep_M(B) = d_M(B) - r$ for all bases $B \in M$. One should notice a similarity in the decomposition of $ep_M$ given in Lemma 2.4 and the decomposition of $d_M$ given in Lemma 4.6. All we have to show is that there is a bijection that makes these two decompositions essentially the same. That bijection comes from a fine mixed subdivision of $P_M$ called the **canonical subdivision**, defined in Oh (2010).

**Lemma 5.1** Let $M$ be a transversal matroid and $P_M$ be its transversalhedron. Look at a Minkowski cell $\prod_{J}^{\infty}$ of type $\mathcal{I}^a$ inside the canonical subdivision of the transversalhedron. And let $l_{M, I_1} \Delta_{J_1} + \cdots + l_{M, I_m} \Delta_{J_m}$ be the corresponding Minkowski sum. We have $0 \notin J_i$ if and only if $I_i \in EP_M(\mathcal{I}^a)$.

By combining Lemma 2.4, Lemma 4.6 and Lemma 5.1, we have $d_M^{\phi(B)}(B) = ep_M^{\phi(B)}(B)$. Using Lemma 5.1 and Lemma 4.6, we get:

$$d_M(\phi(B)) = \sum_{I_i \in EP_M(\mathcal{I}^a)} l_{M, I_i} + \sum_{I_i \notin EP_M(\mathcal{I}^a)} a_i.$$

Combining this with Lemma 2.4, we get $d_M(\phi(B)) - r = ep_M(\phi(B))$.

**Proposition 5.2** Given a transversal matroid $M$ of rank $r$, we look at the canonical mixed subdivision of $P_M$. For each base type, there exists a bijection between good lattice points in fine Minkowski cells of that type and bases of that type. And for all bases $B \in M$, we have $ep_M(B) = d_M(B) - r$.
For each good lattice point at $(c_1, \dots, c_r)$, let's make a monomial $x_1^{c_1-1} \cdots x_r^{c_r-1}$. Then we get a pure order ideal of which Stanley's conjecture is asking for.

**Proposition 5.3** Let $\mathcal{M}$ be a cotransversal matroid. We denote $\mathcal{M}^*$ for the dual matroid, which is in this case a transversal matroid. For each good lattice point $(c_1, \dots, c_r)$ in $P_{\mathcal{M}^*}$, take a monomial $x_1^{c_1-1} \cdots x_r^{c_r-1}$ to form a collection $X$. Then $X$ is a pure order ideal and its degree sequence equals the $h$-vector of $\mathcal{M}$.

This implies Stanley's conjecture for cotransversal matroids.

**Theorem 5.4** *The $h$-vector of a cotransversal matroid is a pure $O$-sequence. In other words, Stanley's conjecture is true for cotransversal matroids.*

We will end with an example regarding our main result. We look at a transversal matroid $\mathcal{M}$ given by the bipartite graph in Figure 1. Then $C_{\mathcal{M},\{1\}} = \{1,2\}$, $C_{\mathcal{M},\{2\}} = \{3,4,5\}$, $C_{\mathcal{M},\{1,2\}} = \{6,7,8,9\}$. So our transversal hedron is given by $2\Delta_{\{1\}} + 3\Delta_{\{2\}} + 4\Delta_{\{1,2\}}$. The cells are given by base sequences $(1,1,0)$, $(1,0,1)$, $(0,1,1)$, $(0,0,2)$. Then one can check that $d_{\mathcal{M}}(B) - 2 = ep_{\mathcal{M}}(B)$ in Figure 5 and the Table below. To get the $h$-vector of $\mathcal{M}^*$ using the polytope, we look at the degree sequence obtained by counting how many good lattice points (lattice points not on any coordinate hyperplanes) are on each diagonal. This gives us the sequence $(1, 2, 3, 4, 5, 6, 6, 5)$, and one can check from the table that this is indeed the $h$-vector of $\mathcal{M}^*$ (the degree sequence of $ep_{\mathcal{M}}$).

## Acknowledgements

The author would like to thank Alexander Postnikov, Richard Stanley and Hwanchul Yoo for useful discussions. The author would also like to thank Jose Soto for his advice on transversal matroids, and David Speyer for his advice on fine mixed subdivisions.

## References

A. Björner. The homology and shellability of matroids and geometric lattices. *Matroid Applications*, pages 226–283, 1992.

M. Boij, J. Migliore, R. Miró-Roig, U. Nagel, and F. Zanello. On the shape of a pure $O$-sequence. *ArXiv e-prints*, Mar. 2010.

M. K. Chari. Matroid inequalities. *Discrete Math.*, 147:283–286, December 1995. ISSN 0012-365X.

M. K. Chari. Two decompositions in topological combinatorics with applications to matroid complexes. *Trans. Amer. Math. Soc*, 349:3925–3943, 1997.

T. Hausel and B. Sturmfels. Toric hyperkäler varieties. *Doc. Math.*, 7:495–534, 2002.

T. Hibi. What can be said about pure $O$-sequences? *Journal of Combinatorial Theory, Series A*, 50(2): 319–322, 1989. ISSN 0097-3165.

C. Merino. The chip firing game and matroid complexes. In *Discrete Mathematics and Theoretical Computer Science, Proceedings vol. AA*, 2001, pages 245–256, 2001.
<figure><img src="image_5.png" /></figure>

<table><caption>Fig. 5 – Canonical mixed subdivision of the transversalhedron $P_M$ and the table of $B \in \mathcal{M}$</caption><thead><tr><th>B</th><th>Type sequence</th><th>ep<sub>M</sub>(B)</th></tr></thead><tbody><tr><td>13</td><td>(1,1,0)</td><td>0</td></tr><tr><td>14</td><td>(1,1,0)</td><td>1</td></tr><tr><td>15</td><td>(1,1,0)</td><td>2</td></tr><tr><td>16</td><td>(1,0,1)</td><td>3</td></tr><tr><td>17</td><td>(1,0,1)</td><td>4</td></tr><tr><td>18</td><td>(1,0,1)</td><td>5</td></tr><tr><td>19</td><td>(1,0,1)</td><td>6</td></tr><tr><td>23</td><td>(1,1,0)</td><td>1</td></tr><tr><td>24</td><td>(1,1,0)</td><td>2</td></tr><tr><td>25</td><td>(1,1,0)</td><td>3</td></tr><tr><td>26</td><td>(1,0,1)</td><td>4</td></tr><tr><td>27</td><td>(1,0,1)</td><td>5</td></tr><tr><td>28</td><td>(1,0,1)</td><td>6</td></tr><tr><td>29</td><td>(1,0,1)</td><td>7</td></tr><tr><td>36</td><td>(0,1,1)</td><td>2</td></tr><tr><td>37</td><td>(0,1,1)</td><td>3</td></tr><tr><td>38</td><td>(0,1,1)</td><td>4</td></tr><tr><td>39</td><td>(0,1,1)</td><td>5</td></tr><tr><td>46</td><td>(0,1,1)</td><td>3</td></tr><tr><td>47</td><td>(0,1,1)</td><td>4</td></tr><tr><td>48</td><td>(0,1,1)</td><td>5</td></tr><tr><td>49</td><td>(0,1,1)</td><td>6</td></tr><tr><td>56</td><td>(0,1,1)</td><td>4</td></tr><tr><td>57</td><td>(0,1,1)</td><td>5</td></tr><tr><td>58</td><td>(0,1,1)</td><td>6</td></tr><tr><td>59</td><td>(0,1,1)</td><td>7</td></tr><tr><td>67</td><td>(0,0,2)</td><td>5</td></tr><tr><td>68</td><td>(0,0,2)</td><td>6</td></tr><tr><td>69</td><td>(0,0,2)</td><td>7</td></tr><tr><td>78</td><td>(0,0,2)</td><td>6</td></tr><tr><td>79</td><td>(0,0,2)</td><td>7</td></tr><tr><td>89</td><td>(0,0,2)</td><td>7</td></tr></tbody></table>
S. Oh. Generalized permutohedra, $h$-vector of cotransversal matroids and pure $O$-sequences. *ArXiv e-prints*, May 2010.

A. Postnikov. Permutohedra, associahedra, and beyond. *International Mathematics Research Notices*, 2009(6):1026–1106, 2009. URL http://imrn.oxfordjournals.org/content/2009/6/1026 abstract.

J. Schweig. On the $h$-vector of a lattice path matroid. *Electron. J. Combin.*, 17:no. 1, N3., 2010.

E. Stokes. The $h$-vectors of 1-dimensional matroid complexes and a conjecture of Stanley. *ArXiv e-prints*, Mar. 2009.