# Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Tropical Oriented Matroids

Suho Oh¹† and Hwanchul Yoo

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, USA

**Abstract.** Develin and Sturmfels showed that regular triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ can be thought of as tropical polytopes. Tropical oriented matroids were defined by Ardila and Develin, and were conjectured to be in bijection with all subdivisions of $\Delta_{n-1} \times \Delta_{d-1}$. In this paper, we show that any triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ encodes a tropical oriented matroid. We also suggest a new class of combinatorial objects that may describe all subdivisions of a bigger class of polytopes.

**Résumé.** Develin et Sturmfels ont montré que les triangulations de $\Delta_{n-1} \times \Delta_{d-1}$ peuvent être considérées comme des polytopes tropicaux. Les matroïdes orientés tropicaux ont été définis par Ardila et Develin, et ils ont été conjec- turés être en bijection avec les subdivisions de $\Delta_{n-1} \times \Delta_{d-1}$. Dans cet article, nous montrons que toute triangulation de $\Delta_{n-1} \times \Delta_{d-1}$ encode un matroïde orienté tropical. De plus, nous proposons une nouvelle classe d'objets combi- natoires qui peuvent décrire toutes les subdivisions d'une plus grande classe de polytopes.

**Keywords:** triangulation, product of simplices, tropical pseudohyperplane arrangement, tropical oriented matroid

## 1 Introduction

Studying triangulations of product of simplices is a very active field of research and there have been numerous results being tied to many different fields ([1], [3], [4], [7], [5], [8], [10], [12], [14], [16]).

In [6], Develin and Sturmfels showed that regular triangulations can be thought as tropical polytopes. Tropical polytopes are essentially tropical hyperplane arrangements. Ardila and Develin defined tropical oriented matroids, that generalize tropical hyperplane arrangements [2]. And they conjectured that tropical oriented matroids are essentially the same as subdivisions of product of simplices. In oriented matroid theory, it is a very well known result that realizable oriented matroids come from hyperplane arrangements and oriented matroids in general come from pseudo-sphere arrangements. They showed that a tropical oriented matroid encodes a subdivision. They also showed that a triangulation of $\Delta_{n-1} \times \Delta_2$ encodes a tropical oriented matroid. In this paper, we provide a strong evidence for the conjecture, by showing that a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ encodes a tropical oriented matroid.

In section 2, we go over the basics of triangulations of $\Delta_{n-1} \times \Delta_{d-1}$, fine mixed subdivisions of $n\Delta_{d-1}$ and develop some tools. In section 3, we go over the definition of tropical oriented matroids.

<footnote>†S.O. was supported in part by Samsung Scholarship.</footnote>
In section 4, we show that the collection of trees in a fine mixed subdivision of $n\Delta_{d-1}$ satisfies the elimination property. In section 5, we suggest a new class of objects that may describe all subdivisions of a generalized permutohedra.

This is an extended abstract. Proofs and more details are given in [9].

## 2 Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Fine Mixed Subdivisions of $n\Delta_{d-1}$

Each full-dimensional simplex in a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ can be described by a spanning tree of the bipartite graph $K_{n,d}$. To see this, we label the vertices of $\Delta_{n-1}$ with $[n]$ and vertices of $\Delta_{d-1}$ with $[d]$, then each vertex of $\Delta_{n-1} \times \Delta_{d-1}$ corresponds to an edge of $K_{n,d}$. We will say that in $K_{n,d}$, the vertices corresponding to $\Delta_{n-1}$ are on the left side and the vertices corresponding to $\Delta_{d-1}$ are on the right side. The vertices of each subpolytope in $\Delta_{n-1} \times \Delta_{d-1}$ determine a subgraph of $K_{n,d}$. We use $(A_1, \dots, A_n)$ where $A_1, \dots, A_n \subseteq [d]$, to denote a subgraph of $K_{n,d}$ that has edges $(i, j)$ for each $j \in A_i$.

Via the Cayley trick, one can think of a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ as a fine mixed subdivision of $n\Delta_{d-1}$ [15]. We will first go over the basics of fine mixed subdivisions, then state some properties that will be useful for our purpose.

**Definition 2.1 ([11])** Let $r$ be the dimension of the Minkowski sum $P_1 + \dots + P_n$. A Minkowski cell in this sum is a polytope $B_1 + \dots + B_n$ of dimension $r$ 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.

We define the simplex $\Delta_{d-1}$ as the convex hull of points $(1, 0, \dots, 0)$, $(0, 1, \dots, 0)$, $\dots$, $(0, \dots, 1)$ in $\mathbb{R}^d$. In this paper, we use the following lemma as a definition of the *fine mixed subdivision*, and we will only consider the fine mixed subdivisions of $\Delta_{d-1} + \dots + \Delta_{d-1}$.

**Lemma 2.2 ([15])** A mixed subdivision is fine if and only if, for each mixed cell $B = B_1 + \dots + B_n$ in this subdivision, all $B_i$ are simplices and $\sum \dim B_i = \dim B$.

The lemma tells us that each fine cell $B_1 + \dots + B_n$ is isomorphic to the direct product $B_1 \times \dots \times B_n$ of simplices. Let $I_i$ be the set of vertices of $B_i$. We think of each cell as a subgraph $(I_1, \dots, I_n)$ and this is a spanning tree [11].

**Remark 2.3** The above lemma also tells us that if we take $J_i \subseteq I_i$, $J_i \neq \emptyset$ for each $i$, then $(J_1, \dots, J_n)$ encodes a face of this cell. From now on, we will use the subgraph of $K_{n,d}$ and its corresponding face interchangeably. That is, a face $(J_1, \dots, J_n)$ means a face $\Delta_{J_1} + \dots + \Delta_{J_n}$.

To avoid confusion with the tropical oriented matroid terminology, we call the 0-dimensional faces as *topes*. For two trees $T$ and $T'$ of $K_{n,d}$, 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. Now we can say exactly which set of spanning trees describes a fine mixed subdivision of $n\Delta_{d-1}$.

**Theorem 2.4 ([13],[1])** A collection of subgraphs $T_1, \dots, T_k$ of $K_{n,d}$ encodes a fine mixed subdivision of $n\Delta_{d-1}$ if and only if:
1. Each $T_i$ is a spanning tree of $K_{n,d}$.

2. For each $T_i$ and each edge $e$ of $T_i$, either $T_i \setminus e$ has an isolated vertex or there is another $T_j$ containing $T_i \setminus e$.

3. For any pair $i, j$ of $[n]$, there is no cycle in $U(T_i, T_j)$.

Given any subgraph $T$ of $K_{n,d}$, define the **left degree vector (LDV)** $\text{ld}(T) = (d_1 - 1, \dots, d_n - 1)$ where $d_i$ is the degree of the vertex $i \in [n]$ on the left side of $T$. Similarly, define the **right degree vector (RDV)** $\text{rd}(T) = (d_1, \dots, d_r - 1)$ where $d_i$ is the degree of the vertex $i \in [d]$ on the right side of $T$. The following proposition is a special case of a statement in the proof of Theorem 11.3 in [11].

**Proposition 2.5 ([11])** Fix a fine mixed subdivision of $n\Delta_{d-1}$. Let $T_1, \dots, T_s$ be the collection of cells. Then the map $T_i \to \text{ld}(T_i)$ is a bijection between fine cells in this subdivision and the set of sequences $(a_1, \dots, a_n)$ satisfying $\sum a_i = d-1$ and $a_i \ge 0$ for all $i \in [n]$. The same holds for the map $T_i \to \text{rd}(T_i)$.

The reason we are interested in LDV and RDV is because LDV governs the shape of the cell and RDV governs the location of the cell.

Given $n\Delta_{d-1}$ and $i \in [d]$, we call the facet opposite to vertex $i$ as the *i-facet*. A simplex in a plane, whose edge has the length $n$, can be subdivided by upper and lower unit triangles that are congruent to each other. In higher dimension, although there is no analogue for the lower triangles, there is one for the upper triangles. It is just the collection of simplices whose edges are of length 1 and whose vertices have integer coordinates. We call these simplices the **unit simplices**. We express the **location** of a unit simplex as $(a_1, \dots, a_d)$, where $a_i \in \mathbb{Z}$ stands for the distance between the *i*-facet and the unit simplex. We also have the relation that $\sum_i a_i = n-1$. See Figure 1 for an example. The following lemma is a direct consequence of Lemma 14.9 of [11].

**Lemma 2.6** Each cell $T = (T_1, \dots, T_n)$ in the fine mixed subdivision of $n\Delta_{d-1}$ contains exactly one unit simplex. The location of such simplex is equal to $\text{rd}(T)$.

An example of this phenomenon is given in Figure 1.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** The number of $i$'s in a tope for each $i \in [d]$ describes the position of the tope. RDV describes the position of the unit simplex that the cell contains.</figcaption></figure>
# 3 Tropical Oriented Matroids

In this section, we will review the definition of tropical hyperplane arrangements and tropical oriented matroids that were defined in [2].

**Definition 3.1** *The tropical semiring is given by the real numbers $\mathbb{R}$ together with the operations of tropical addition $\oplus$ and tropical multiplication $\odot$ defined by $a \oplus b = \max(a, b)$ and $a \odot b = a + b$.*

For convenience, we will work in the tropical projective $(d-1)$-space $\mathbb{TP}^{d-1}$, given by modding out by tropical scalar multiplication. In this space, **tropical hyperplanes** are given by the vanishing locus of $\oplus c_i \odot x_i$, where the vanishing locus is defined to be the set of points where $\max(c_1+x_1, \dots, c_d+x_d)$ is achieved at least twice.

Given an arrangement $H_1, \dots, H_n$ in $\mathbb{TP}^{d-1}$, let $v_i = (v_{i1}, \dots, v_{id})$ be the vertex of the hyperplane $H_i$, for all $i$. The **type** of a point $x \in \mathbb{TP}^{d-1}$ is the $n$-tuple $(A_1, \dots, A_n)$, where $A_i \subseteq [d]$ is the set of indices $j$ for which $x_j - v_{ij}$ is maximal. Since all points in a face of the arrangement have the same type, that type is called the **type of the face**.

**Definition 3.2** *An $(n, d)$-type is an $n$-tuple $A = (A_1, \dots, A_n)$ of nonempty subsets of $[d] := \{1, \dots, d\}$. The sets $A_1, \dots, A_n$ are called the **coordinates** of $A$.*

One should keep in mind that these types will correspond to trees coming from the faces of a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$.

**Definition 3.3 ([2])** Given two $(n, d)$-types $A$ and $B$, the **comparability graph** $CG_{A,B}$ has vertex set $[d]$. For $1 \le i \le n$, we draw an edge between $j$ and $k$ for each $j \in A_i$ and $k \in B_i$. That edge is **undirected** if $j, k \in A_i \cap B_i$, and it is **directed** $j \to k$ otherwise.

**Definition 3.4 ([2])** A **semidigraph** is a graph with some undirected edges and some directed edges. A **directed path** from $a$ to $b$ in a semidigraph is a collection of vertices $v_0 = a, v_1, \dots, v_k = b$ and a collection of edges $e_1, \dots, e_k$, at least one of which is directed, such that $e_i$ is either a directed edge from $v_{i-1}$ to $v_i$ or an undirected edge connecting the two. A **directed cycle** is a directed path with identical endpoints. A semidigraph is **acyclic** if it has no directed cycles.

Here is the definition of **refinement** of a type that fits our needs. The reason that this definition is enough will be explained at the end of this section.

**Definition 3.5** *The refinement of a type $A = (A_1, \dots, A_n)$ is a type whose $i$-th coordinate is a nonempty subset of $A_i$ for all $i$.*

**Remark 3.6** In fact, this definition is only good for our purpose (i.e. for fine mixed subdivisions), and the correct way to define the refinement for any mixed subdivision is as follows:

**Definition 3.7 ([2])** The **refinement** of a type $A = (A_1, \dots, A_n)$ with respect to an ordered partition $P = (P_1, \dots, P_r)$ of $[d]$ is $A_P = (A_1 \cap P_{m(1)}, \dots, A_n \cap P_{m(n)})$ where $m(i)$ is the largest index for which $A_i \cap P_{m(i)}$ is non-empty. A refinement $A_P$ is **total** if all of its entries are singletons.

Now we define the tropical oriented matroid which is our main subject of this extended abstract.

**Definition 3.8 ([2])** A **tropical oriented matroid** $M$ (with parameters $(n, d)$) is a collection of $(n, d)$-types which satisfy the following four axioms:
* Boundary : For each $j \in [d]$, the type $\mathbf{j} := (j, \dots, j)$ is in $M$.

* Elimination : If we have two types A and B in $M$ and a position $j \in [n]$, then there exists a type C in $M$ with $C_j = A_j \cup B_j$, and $C_k \in \{A_k, B_k, A_k \cup B_k\}$ for all $k \in [n]$.

* Comparability : The comparability graph $CG_{A,B}$ of any two types A and B in $M$ is acyclic.

* Surrounding : If A is a type in $M$, then any refinement of A is also in $M$.

**Theorem 3.9 ([2]** The types of the vertices of a tropical oriented matroid $M$ with parameters $(n, d)$ describe a set of spanning graphs defining a mixed subdivision of $n\Delta_{d-1}$.

They proposed the following three conjectures:

1. There is a one-to-one correspondence between the set of all subdivision of $\Delta_{n-1} \times \Delta_{d-1}$ and a tropical oriented matroid with parameters $(n, d)$.

2. The dual of a tropical oriented matroid with parameters $(n, d)$ is a tropical oriented matroid with parameters $(d, n)$.

3. Every tropical oriented matroid can be realized by an arrangement of tropical pseudo-hyperplanes.

Before we end this section, we explain why Definition 3.5 of refinement is enough for our purposes.

**Lemma 3.10** Let $A = (A_1, \dots, A_n)$ be a $(n, d)$-type of a tropical oriented matroid, such that if one views this type as a subgraph of $K_{n,d}$, then it does not contain a cycle. Choose any $i \in [d]$ such that $|A_i| > 1$. Then choose any $k \in A_i$. Let $A'$ be obtained from $A$ by deleting $k$ from $A_i$. Then surrounding axiom tells us that $A'$ is in this tropical oriented matroid.

**Proof:** Let $Z$ be the union of all $A_j$ such that $k \in A_j$ and $j \neq i$. Let $W$ be the union of rest of $A_j$'s. Then $Z \cap W = \{k\}$ since otherwise, we get a cycle in $A$. So let our ordered partition be $(W^c \cup \{k\}, W \setminus \{k\})$. Then we get $A'$ from $A$ by a refinement as given in Definition 3.7. $\square$

This is a more natural way to think of the surrounding axiom for our purpose, since all types coming from a fine mixed subdivision of $n\Delta_{d-1}$ have no cycles and satisfy this property, as can be seen from Remark 2.3. Whenever we use this property (or Remark 2.3), we will refer to this as the surrounding property.

# 4 Elimination Property

Fix a fine mixed subdivision of $n\Delta_{d-1}$. Let $\mathcal{M}$ denote the collection of trees coming the subdivision. We are going to show that this is a tropical oriented matroid. Although we don't use it, our proof is heavily motivated from the topological representation conjecture that a mixed subdivision of $n\Delta_{d-1}$ can be viewed as a tropical pseudo-hyperplane arrangement.

Roughly, the elimination property can be thought as existence of a very nice path between two types A and B. In particular, if $A_i = B_i$, we want a path such that its $i$-th coordinate is always equal to $A_i = B_i$. We are going to use induction based on an index defined for each pair of types, called **rank**. Throughout the examples given in the section, for convenience, we are going to write sets such as $\{1, 2, 3\}$ by 123.
Also, recall that we call the 0-dimensional faces in a fine mixed subdivision of $n\Delta_{d-1}$ as **topes**, instead of vertices, to avoid confusion with the tropical oriented matroid terminology.

Here is a motivation for the definition of the rank. Assume we are given a fine mixed subdivision of $n\Delta_2$ and let $A$ and $B$ be two types such that $A_i = B_i$. Let's look at the corresponding tropical pseudo-hyperplane arrangement. We are going to consider the case when $A_i = B_i = \{2\}$ and this is illustrated in Figure 2. Assume we are given some path between $A$ and $B$ such that for some types along this path, the $i$-th coordinate is not equal to $A_i$. Let $C$ and $D$ be the first and last points at which the path intersects the $i$-th tropical pseudo-hyperplane. Then $C$ and $D$ are both on the boundary of the region $\{2\}$ with respect to the $i$-th tropical pseudo-hyperplane. If we know that there is a nice path between these two points on this boundary, then we can lift this path a little bit to get a path inside the $\{2\}$-region by using the surrounding property.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Rank is a good index for proving elimination property</figcaption></figure>

**Definition 4.1** For each pair of types $A, B \in \mathcal{M}$, the **rank** of the pair $(A, B)$ is defined as $(r_1, \dots, r_n)$ where for each $i \in [d]$, $r_i = \min(|A_i|, |B_i|) - 1$. This is going to be denoted by $rk(A, B)$. For any $\alpha = (a_1, \dots, a_n)$ and $\beta = (b_1, \dots, b_n)$, we write $\alpha \ge \beta$ if we have $a_i \ge b_i$ for all $i \in [n]$. Similarly we write $\alpha > \beta$ if the inequality is strict in at least one coordinate.

For example, $rk((123, 2), (3, 123)) = (0, 0)$ and $rk((123, 45), (3, 125)) = (0, 1)$.

So $rk((123, 2), (3, 123)) < rk((123, 45), (3, 125))$.

**Definition 4.2** We will say that two types $A$ and $B$ are **adjacent** if $A$ and $B$ are different in exactly one coordinate and also differ by one element in it. A **path** between two types is a sequence of types $A = C^0 \to C^1 \to C^2 \to \dots \to C^{q-1} \to C^q = B$ such that each $C^t$ is adjacent to $C^{t-1}$ and $C^{t+1}$. The **length** of the path is given by $q$. Given a path, we say that coordinate $i$ is **strong** if:

1. in that coordinate, after some some element is deleted, no element gets added.

2. for all $t$, we have $A_i \cup B_i \supseteq C_i^t$.

3. if an element $j$ was added, then it does not get deleted later. This implies that $C_i^t \subseteq A_i \cup B_i$ for all $t$.

A **strong path** between types $A$ and $B$ is a path that is **strong** in every coordinates.

A strong path is a path such that in each coordinate, it changes like

$$123 \to 1234 \to 12345 \to 1245 \to 145.$$
The reason we are interested in strong paths is because it is enough to find a strong path between any two types A and B to prove the elimination property for $\mathcal{M}$.

**Lemma 4.3** If there is a strong path between any two types A and B, then elimination holds.

Notice that in the example of a strong path above, the cardinality of each set is bounded below by $\min(|A_i|, |B_i|)$. When we are looking for a strong path between A and B, we do not consider all types. We only consider the types where the cardinality is bounded below by $rk(A, B)$.

**Definition 4.4** For each $\alpha = (a_1, \cdots, a_n)$, $Q_\alpha$ is defined as the collection of types $(A_1, \cdots, A_n)$ such that $|A_i| > a_i$ for all $i \in [n]$.

We use $\Delta(A, B)$ to denote $\sum_i (|A_i \setminus B_i| + |B_i \setminus A_i|)$. Then any path between A and B has length at least $\Delta(A, B)$. The length of a strong path between A and B is equal to $\Delta(A, B)$. We are later going to show that we can transform a lengthwise-shortest path between A and B in $Q_{rk(A,B)}$ to a strong path. So we want to show that given any types A and B in $Q_\alpha$, there is a path connecting them in $Q_\alpha$.

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** How $S_{1,0,1}^*$ looks like.</figcaption></figure>

If we consider only the cells of $Q_\alpha$, we are basically putting a cardinality restriction on the LDV's. Given an $(n, d)$-type A such that all $i \in [d]$ appears in A, we define $A^T$ as a type with parameters $(d, n)$, that has $i \in A_j^T$ if and only if $j \in A_i$. We say that $A^T$ is the **dual** of A. We can take the dual of any type that is not on the boundary of $n\Delta_{d-1}$. Dual of a cell is a cell, LDV becomes RDV, and the cardinality restriction on RDV is easy to view.

**Remark 4.5** Define $Q_\alpha^*$ to be the collection of types in the fine dual mixed subdivision (i.e. mixed subdivision of $d\Delta_{n-1}$ coming from the same triangulation $\Delta_{d-1} \times \Delta_{n-1}$) such that it contains strictly more than $a_i$ number of $i$'s for each $i \in [n]$. Then a cell is in $Q_\alpha$ if and only if its dual is in $Q_\alpha^*$. And two cells are adjacent (i.e. sharing a common facet) in $Q_\alpha$ if and only if their duals are adjacent in $Q_\alpha^*$.

Due to Lemma 2.6, the unit simplices in these cells are exactly the ones that are inside a subsimplex of $d\Delta_{n-1}$. We will denote this subsimplex as $S_\alpha^*$. Although we will not define $S_\alpha$, we will keep the star in the notation to emphasize the fact that $S_\alpha^*$ is in $Q_\alpha^*$. Take a look at the first picture of Figure 3. Cells in $Q_{1,0,1}^*$ are the two rhombi and the simplex having RDV (1, 1, 1), (2, 0, 1) and (1, 0, 2). Also, $S_{1,0,1}^*$ is the length 2 simplex surrounded by the red lines. Before we prove that $Q_\alpha$ is connected, we need the following well known results in integer programming.
**Theorem 4.6 ([18], Theorem 5.20)** A matrix $\mathbf{Y}$ is called totally unimodular if each square submatrix of $\mathbf{Y}$ has determinant equal to 0, +1 or -1. Let $\mathbf{Y}$ be a totally unimodular $m \times n$ matrix and let $b \in \mathbb{Z}^m$. Then the polyhedron $\mathbf{P} := \{x | Yx \le b\}$ has integer vertices.

**Lemma 4.7 ([17], p.279)** A matrix $\mathbf{Y}$ is an interval matrix if it is an $\{0, 1\}$-matrix and each row of $\mathbf{Y}$ has 1's consecutively. Then $\mathbf{Y}$ is also totally unimodular.

We want to show that the matrix defining a fine cell is totally unimodular. To do this, we need a way to describe the matrix defining a fine cell. Note that $n\Delta_{d-1}$ lives on the plane $x_1 + \cdots + x_d = n$. Let us project it onto the plane $x_d = 0$. Denote the image as $n\Delta'_{d-1}$, which lives in $\mathbb{R}^{d-1}$. The projection does not change any fine mixed subdivision structure.

**Lemma 4.8** Let $\mathbf{T}$ be a fine mixed cell of $n\Delta'_{d-1}$. For any edge $e$ of $\mathbf{T}$ that is not connected to a leaf on the left side, we assign a facet $F_e$ of $\mathbf{T}$ by deleting the edge from $\mathbf{T}$. Let us denote by $I_e$ the set of vertices on the right side which are not connected to $d$ in $\mathbf{T} \setminus \{e\}$. The equation of $F_e$ is given by $\sum_{j \in I_e} x_j = c$ for some $c \in \mathbb{Z}$.

**Corollary 4.9** A matrix $\mathbf{Y}$ defining a fine mixed cell $\mathbf{T}$ in $n\Delta_{d-1}$ is totally unimodular.

**Proof:** Each cell is a polytope, and it is defined by a matrix inequality as in Theorem 4.6(although may not unimodular in priori). From the way the projection was defined, it is enough to show that the matrix $\mathbf{Y}'$ defining a cell in $n\Delta'_{d-1}$ is totally unimodular. If there are two rows in $\mathbf{Y}'$ such that their support sets are incomparable, but not disjoint, the previous lemma tells us that there is a cycle in $\mathbf{T}$ of length $\ge 4$. So the support sets of any pair of rows are either comparable or disjoint. After some reordering of the columns, this becomes an interval matrix. Lemma 4.7 implies that $\mathbf{Y}'$ is totally unimodular. $\square$

Using this, we are going to show that when $S_{\alpha}^{*}$ is a length 2 simplex, $Q_{\alpha}^{*}$ is connected.

**Lemma 4.10** Let $A$ and $B$ be two cells in $Q_{\alpha}^{*}$ such that $\alpha = (a_1, \cdots, a_n)$ and $\sum a_i = n-2$. Then there is a path in $Q_{\alpha}^{*}$ from $A$ to $B$, consisting of cells and their facets.

**Proof:** Any tope in $S_{\alpha}^{*}$ contains at least $a_i$ number of $i$'s. And any tope that is not on the $i$-facet of $S_{\alpha}$ contains at least $a_i + 1$ number of $i$'s. Now choose any tope $C$ in $S_{\alpha}^{*}$. Let $\mathbf{T}$ be a cell that contains $C$ and intersects with the interior of $S_{\alpha}^{*}$.

We can view $\mathbf{T} \cap S_{\alpha}^{*}$ as the solution space of inequalities defining the cell $\mathbf{T}$ and inequalities of the form $x_i \ge a_i \in \mathbb{Z}$. If we rewrite these inequalities in terms of $Yx \le b$, then $b$ is an integer vector. And $\mathbf{Y}$ is a totally unimodular matrix due to Corollary 4.9. We know that this intersection is non-empty, full-dimensional and bounded by $S_{\alpha}$. Theorem 4.6 tells us that the solution space is a full-dimensional integer polytope. Hence $\mathbf{T}$ contains at least $d$ topes of $S_{\alpha}^{*}$ such that for each $i$, there is at least one tope not on the $i$-facet of $S_{\alpha}^{*}$. If some tope of $\mathbf{T}$ contains $k$ number of $i$'s then $\mathbf{T}$ also contains at least $k$ number of $i$'s. So $\mathbf{T}$ is in $Q_{\alpha}^{*}$.

Now let $A$ and $B$ be any two cells of $Q_{\alpha}^{*}$. They share at least one tope in $S_{\alpha}^{*}$. We can draw a path near this tope inside $S_{\alpha}^{*}$ that starts at $A$, ends at $B$ and goes through only the cells and their facets. From what we proved just before, all cells that this path goes through are cells of $Q_{\alpha}^{*}$. $\square$

**Corollary 4.11** Pick any $\alpha = (a_1, \cdots, a_n)$ and let $A$ and $B$ be two types in $Q_{\alpha}$. Then there is a path connecting them.
Now we are ready to prove that elimination holds.

**Proposition 4.12** *Elimination property holds for *M*, a collection of trees coming from a fine mixed sub-division of *n*Δ<sub>*d*−1</sub>.*

**Proof:** Let us dedicate $l_{A,B}$ to be the length of a shortest path between $A$ and $B$ in $Q_{rk(A,B)}$. It is well defined by Corollary 4.11. We are going to show that there is a strong path between $A$ and $B$ by induction, decreasing $rk(A, B)$ and then increasing $l_{A,B}$.

When $rk(A, B)$ is maximal (i.e. $\sum_i rk(A, B)_i = d - 1$), $A$ and $B$ have to be spanning trees. Since Proposition 2.5 tells us that $A = B$, the claim is obvious in this case. The claim is also obvious when $l_{A,B} = 0$, since $\Delta(A, B) \le l_{A,B}$. So assume for the sake of induction, that we know there is a strong path between any pair $D, E$ such that

* $rk(D, E) > rk(A, B)$ or

* $rk(D, E) = rk(A, B)$ and $l_{D,E} < l_{A,B}$.

Let $A = C^0 \to A' = C^1 \to \dots \to C^{l_{A,B}} = B$ be a shortest path between $A$ and $B$ in $Q_{rk(A,B)}$.
Notice that $A' \in Q_{rk(A,B)}$ implies $rk(A', B) \ge rk(A, B)$. Then the induction hypothesis tells us that
there is a strong path between $A'$ and $B$. Replace $A' \to \dots \to B$ with the strong path between $A'$ and
$B$, then we still get a shortest path between $A$ and $B$ in $Q_{rk(A,B)}$. Now we are going to do a case-by-case
analysis on how $A \to A'$ looks like.

1. If an element of $B_i \setminus A_i$ is added to the *i*-th coordinate, or if $A_i \supsetneq B_i$ and an element of $A_i \setminus B_i$ is deleted from *i*-th coordinate, then this path is a strong path between *A* and *B*.

2. Consider the case when some element $q \notin B_i \setminus A_i$ is added to the *i*-th coordinate. We are going to show that this case cannot happen. Let $C^t \to C^{t+1}$ be the first pair of types where $q$ gets deleted from the *i*-th coordinate. Look at the path $A' = C^1 \to \dots \to C^t$. Any type $C$ among this path should satisfy $|C_i| \ge \min(|C_i^1|, |C_i^t|) > \min(|A_i|, |B_i|)$. Even after we delete $q$ from the *i*-th coordinate for all types in this path, they are still in $Q_{rk(A,B)}$. So we may replace $A' \to \dots \to C^t$ with a path in $Q_{rk(A,B)}$ that is strictly shorter. We get a contradiction since $A \to \dots \to B$ is a shortest path between $A$ and $B$ in $Q_{rk(A,B)}$.

3. The remaining case is when some element $q$ is deleted from the $i$-th coordinate where $A_i \not\supsetneq B_i$. We are going to show that we may ignore this case. Let $C^t \to C^{t+1}$ be the first pair of types where some element $q'$ gets added to the $i$-th coordinate. Such $t$ exists since $A_i \not\supsetneq B_i$. Notice that $C^{t+1} \in Q_{rk(A,B)}$ implies $rk(A, C^{t+1}) \ge rk(A, B)$. Then induction hypothesis tells us that we have a strong path between $A$ and $C^{t+1}$. We can replace $A \to \dots \to C^{t+1}$ with this strong path between $A$ and $C^{t+1}$. Then we get a path $A \to A' \to \dots \to B$ that is a shortest path between $A$ and $B$ in $Q_{rk(A,B)}$. As before, replace $A' \to \dots \to B$ with a strong path between $A'$ and $B$, then we get a path that falls into one of the previous cases.

So induction tells us that the claim is true.

☐
We will roughly sketch how the process works. Let's assume that when going from A to A', the i-th coordinate changed. If the i-th coordinate of the path changes like

$$123 \to 1235 \to \dots \to 14,$$

induction hypothesis on the length tells us that $A' \to \dots \to B$ can be replaced with a strong path of same length. So now the i-th coordinate of the path changes like

$$123 \to 1235 \to 12345 \to 1245 \to 124 \to 14.$$

Using the surrounding property, we can get

$$123 \to 123 \to 1234 \to 124 \to 124 \to 14.$$

Then we get a redundant type in this path, so it is not a shortest-length path. If the path changes like

$$123 \to 23 \to \dots \to 14,$$

induction hypothesis tells us that $A' \to \dots \to B$ can be replaced with a strong path of same length. So now the path changes like

$$123 \to 23 \to 234 \to 1234 \to 134 \to 14.$$

Induction hypothesis on the length tells us there is a strong path between 123 and 234, and we can replace this part to get

$$123 \to 1234 \to 234 \to 1234 \to 134 \to 14.$$

So for proof purposes, we could ignore the case when an element in an incomparable coordinate was deleted going from A to A'.

**Corollary 4.13** Given a collection of all trees in a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$, it forms a tropical oriented matroid.

# 5 Further Remarks

Tropical oriented matroids are in bijection with mixed subdivisions of $n\Delta_{d-1}$. Unimodular oriented matroids are in bijection with mixed subdivisions of a zonotope, where any edge used in the summand is an edge of $\Delta_{d-1}$. There happens to be a natural class of polytopes that contains these two polytopes at the same time, which is called the **generalized permutohedra** [11]. The trees coming from faces of a fine mixed subdivision of a generalized permutohedra are also $(n, d)$-types, so this suggests that the general framework would be similar.

The surrounding property and the comparability property still hold for generalized permutohedra. In the proof of the elimination property for $n\Delta_{d-1}$ case, all we needed was the connectivity of $Q_\alpha$. And this seems to be a property that generalized permutohedra would also have, since the fact that RDV encodes the position of the cell is still true for generalized permutohedra. Boundary axiom can be modified, in the sense that the boundary topes have to be the vertices defining the convex hull of a generalized permutohedron. Also we have to impose that every covector is a subgraph of the graph G defining the generalized permutohedron. Below is our definition of the **generalized tropical oriented matroid (G-TOM):**
**Definition 5.1** Let $P = P_G(y_1, \dots, y_n) = y_1\Delta_{I_1} + \dots + y_n\Delta_{I_n}$ be a generalized permutohedron, where $\Delta_{I_i}$'s are faces of $\Delta_{d-1}$ and $y_i \ge 0$ for all $i$. A collection $\mathcal{M}_P$ of $(n, d)$-types is called a **generalized tropical oriented matroid** of $P$ if it satisfies the following conditions:

* **Subgraph** : Every graph representing an $(n, d)$-type $A \in \mathcal{M}_P$ is a subgraph of $G$,

* **Boundary** : If $A$ is a tope and its RDV is unique among those satisfying the first condition, then $A \in \mathcal{M}_P$,

* **Surrounding** : Same as tropical oriented matroids,

* **Comparability** : Same as tropical oriented matroids,

* **Elimination** : Same as tropical oriented matroids.

And our question is:

**Question 5.2** Given a generalized permutohedron $P_G$, is there a bijection between the mixed subdivisions of $P_G$ and $G$-TOM's?

## Acknowledgements

We would like to thank Alexander Postnikov, Federico Ardila and César Ceballos for useful discussions. We would also like to thank Michel Goemans for suggesting Theorem 4.6.

## References

[1] F. Ardila and S. Billey. Flag arrangements and triangulations of products of simplices. *Advances in Mathematics*, 214(2):495–524, 2007.

[2] F. Ardila and M. Develin. Tropical hyperplane arrangements and oriented matroids. *Mathematische Zeitschrift*, 262:795–816, 2009. 10.1007/s00209-008-0400-z.

[3] E. K. Babson and L. J. Billera. The geometry of products of minors. *Discrete Comput. Geom.*, 20(2):231–249, 1998.

[4] M. M. Bayer. Equidecomposable and weakly neighborly polytopes. *Israel J. Math.*, 81(3):31–320, 1993.

[5] M. Develin. The moduli space of $n$ tropically collinear points in $\mathbb{R}^d$. *Collect. Math.*, 56(1):1–19, 2005.

[6] M. Develin and B. Sturmfels. Tropical convexity. *Doc. Math.*, 9:1–27 (electronic), 2004.

[7] I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky. *Discriminants, resultants, and multidimensional determinants*. Mathematics: Theory and Applications. Boston, MA: Birkhäuser. vii, 523 p. DM 158.00; öS 1232.40; sFr. 138.00; Sterling 60.00, 1994.

[8] M. Haiman. A simple and relatively efficient triangulation of the $n$-cube. *Discrete Comput. Geom.*, 6(4):287–289, 1991.
[9] S. Oh and H. Yoo. Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and tropical oriented matroids. *ArXiv e-prints*, 2010.

[10] D. Orden and F. Santos. Asymptotically efficient triangulations of the $d$-cube. *Discrete Comput. Geom.*, 30(4):509–528, 2003.

[11] A. Postnikov. Permutohedra, Associahedra, and Beyond. *International Mathematics Research Notes*, 2009(6):1026–1106, 2009.

[12] J. Rambau. Triangulations of cyclic polytopes and higher Bruhat orders. *Mathematika*, 44(1):162–194, 1997.

[13] F. Santos. Triangulations of oriented matroids, 1997.

[14] F. Santos. A point set whose space of triangulations is disconnected. *J. Am. Math. Soc.*, 13(3):611–637, 2000.

[15] F. Santos. The Cayley trick and triangulations of products of simplices. *Contemp. Math.*, 374:151–177, 2003.

[16] F. Santos. Non-connected toric Hilbert schemes. *Math. Ann.*, 332(3):645–665, 2005.

[17] A. Schrijver. *Theory of Linear and Integer Programming*. John Wiley & Sons, June 1998.

[18] A. Schrijver and P. Muidergracht. A course in combinatorial optimization, 2003.