Matching Ensembles(Extended Abstract)

Suho Oh<fnref n="1" /> and Hwanchul Yoo<fnref n="2" />

**Abstract.** We introduce an axiom system for a collection of matchings that describes the triangulation of product of simplices.

**Résumé.** Nous introduisons un système d'axiomes pour une collection de couplages qui décrit la triangulation de produit de simplexes.

**Keywords:** Matchings, Bipartite Graphs, Spanning trees, Simplices, Product of two simplices, Subdivisions, Triangulations.

# 1 Introduction

Triangulations of a product of two simplices are beautiful and important objects. In this paper, we describe a new combinatorial model for describing the triangulations of product of two simplices, $\Delta_{n-1} \times \Delta_{d-1}$.

The model we use is called *matching ensemble*; it was motivated by *matching fields* introduced and studied by Bernstein and Zelevinsky Bernstein and Zelevinsky (1993). The $(n, d)$-matching field, for $n \ge d$, is a collection of bijections ("matchings") between $d$-element subsets of $[n] = \{1, \dots, n\}$ and the set $[d] = \{1, \dots, d\}$. A matching field is *coherent* if it satisfies *linkage property*, which is similar to the basis exchange axiom for matroids. These objects were used to study the *Newton polytope* of the product of all maximal minors of an $n$-by-$d$ matrix of indeterminates.

We define an $(n, d)$-matching ensemble as a collection of matchings between subsets of $[n]$ and subsets of $[d]$ such that:

* there is exactly one matching between every pair with same cardinality,

* a submatching of any matching is in the collection, and

* the matchings contained in the collection satisfy the linkage property.

There is a bijection between $(n, d)$-matching ensembles and triangulations of $\Delta_{n-1} \times \Delta_{d-1}$. This is an extended abstract, and the proof of this claim can be found in Oh and Yoo (2013).

<footnote n="1">¹Texas State University, San Marcos, Texas, USA</footnote>

<footnote n="2">²KIAS, Seoul, Korea</footnote>
## 2 Triangulation of $\Delta_{n-1} \times \Delta_{d-1}$

Following Postnikov (2009), we will study $\Delta_{n-1} \times \Delta_{d-1}$ using a class of polytopes associated to bipartite graphs $G \subseteq K_{n,d}$, called **root polytopes**. We think of the complete bipartite graph $K_{n,d}$ as having a set of left vertices $\{1, \dots, n\}$ and a set of right vertices $\{\bar{1}, \dots, \bar{d}\}$. We define $Q_G$ to denote the convex hull of points $e_i - e_j$ for edges $(i, j)$ of $G$ where $e_1, \dots, e_n, e_{\bar{1}}, \dots, e_{\bar{d}}$ are the coordinate vectors in $\mathbb{R}^{n+d}$. When $G$ is the complete bipartite graph $K_{n,d}$, the polytope $Q_G$ is exactly $\Delta_{n-1} \times \Delta_{d-1}$.

**Definition 2.1.** A **triangulation** of a polytope $P$ is a subdivision of $P$ into a union of simplices of the same dimension as $P$ such that each simplex is the convex hull of some subset of vertices of $P$ and any two simplices intersect properly, i.e., the intersection of any two simplices is their common face.

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** An example of a triangulation of $\Delta_1 \times \Delta_2$.</figcaption></figure>

Figure 1 is an example of a triangulation of $\Delta_1 \times \Delta_2$. We will be studying the triangulation of $\Delta_{n-1} \times \Delta_{d-1}$. The simplices of the triangulations can be described via spanning trees due to the following lemma:

**Lemma 2.2 (Lemma 12.5 of Postnikov (2009).)** For a subgraph $H \subseteq K_{n,d}$, the polytope $Q_H$ is a $n+d-2$ dimensional simplex if and only if $H$ is a spanning tree of $K_{n,d}$. All $n+d-2$ dimensional simplices of this form have the same volume $\frac{1}{(n+d-2)!}$.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Spanning tree of $K_{2,3}$ which encodes the simplices in Figure 1.</figcaption></figure>
If we look at the triangulation in Figure 1, one of the simplices is a convex hull of $e_1 - e_{\bar{1}}, e_1 - e_{\bar{3}}, e_2 - e_{\bar{1}}, e_2 - e_{\bar{2}}$. This is encoded as a spanning tree in Figure 2 having edges (1, 1), (1, 3), (2, 1), (2, 2). We express this tree as (13, 12), standing for the fact that the first left vertex is connected to first and third vertex (13) on the right, and the second right vertex is connected to first and second (12) vertex on the right.

Lemma 2.2 tells us that a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ is a collection of simplices $\{Q_{T_1}, \dots, Q_{T_s}\}$, for some spanning trees $T_1, \dots, T_s$ of $K_{n,d}$ such that $Q_{K_{n,d}} = \cup Q_{T_i}$ and each intersection $Q_{T_i} \cap Q_{T_j}$ is the common face of the two simplices. Lemma 2.2 combined with Theorem 12.2 of Postnikov (2009), implies that:

**Lemma 2.3.** *A triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ contains exactly $\binom{n+d-2}{d-1}$ of $n+d-2$ dimensional simplices.*

For two spanning trees $T$ and $T'$ of $K_{n,d}$, let $U(T, T')$ be 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. We say that $T$ and $T'$ are *compatible* if the directed graph $U(T, T')$ has no directed cycles of length $\ge 4$, and *incompatible* if not. An example is given in Figure 3. The pair on the right is incompatible, since we get a cycle (1, $\bar{1}$), (1, 2), (2, $\bar{2}$), (2, 1) (Here we write the right vertices as $\bar{1}, \bar{2}, \bar{3}$) which alternates between the edges of the two trees.

<figure><img src="image_3.png" /><figcaption>**Fig. 3:** The pair to the left is compatible. The pair to the right is incompatible.</figcaption></figure>

Combining Lemma 12.6, Definition 12.7, Lemma 12.7 of Postnikov (2009), we get the following:

**Proposition 2.4.** *A collection of spanning trees of $K_{n,d}$ encodes a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ if and only if it satisfies the following two conditions:*

* The collection contains exactly $\binom{n+d-2}{d-1}$ number of spanning trees.

* Any pair inside the collection is compatible.

An example of such collection of spanning trees of $K_{3,3}$ is given in Figure 4. Any pair of trees inside the collection is compatible, and there are correct number of trees. Hence this collection encodes a triangulation of $\Delta_2 \times \Delta_2$, where each spanning tree corresponds to a simplex inside the triangulation. The picture in the middle is a mixed subdivision of $3\Delta_2$ which corresponds to the triangulation via the **Cayley trick**. For details on the connection between mixed subdivisions of $n\Delta_{d-1}$ and $\Delta_{n-1} \times \Delta_{d-1}$, please refer to Postnikov (2009) or Oh and Yoo (2013).

# 3 Extracting matchings from a triangulation

Given two sets $A$ and $B$ of equal cardinality, the **matching** is a bijection between $A$ and $B$. We think of this as a bipartite graph, with left vertex set $A$ and right vertex set $B$, and edge set given by the set of edges $(a, \pi(a))$ where $\pi$ is the bijection between $A$ and $B$.
<figure><img src="image_4.png" /><figcaption>**Fig. 4:** A collection of spanning trees of $K_{3,3}$ that encodes a triangulation of $\Delta_2 \times \Delta_2$.</figcaption></figure>

Given a collection of spanning trees that encodes a triangulation of $\Delta_{n-1} \times \Delta_{d-1}$, let us collect all matchings that appears as a subgraph in any of the trees of the collection. For example, the matchings we get from Figure 1 and Figure 2 would look like Figure 5.

<figure><img src="image_5.png" /><figcaption>**Fig. 5:** A collection of matchings obtained from Figure 2.</figcaption></figure>

A collection of matchings obtained from Figure 4 would consist of all edges of $K_{3,3}$ and the matchings that appear in Figure 6.

In the next section, we are going to show that we can classify the collection of matchings coming from triangulations, and give an explicit axiomatic system for them. The collection of matchings that satisfy the axiom (hence will correspond to a triangulation) will be called a *Matching Ensemble*.

# 4 Matching Ensemble

In this section, we will define matching ensembles. To do so, we will borrow the notion of *matching fields* and *linkage axiom* which was used in Bernstein and Zelevinsky (1993). Although the matching fields used in Bernstein and Zelevinsky (1993) only concerns *d*-by-*d* matchings, we extend the definition
<figure><img src="image_6.png" /><figcaption>**Fig. 6:** A collection of matchings obtained from Figure 4. Only the matchings of size > 1 are listed.</figcaption></figure>

and look at matchings of all sizes.

**Definition 4.1.** We say that a collection $\mathcal{M}$ of matchings between subsets of $[n]$ and subsets of $[d]$ forms a matching field (with parameters $(n, d)$) if it satisfies the following two axioms:

* There is exactly one matching for any pair $I \subseteq [n], J \subseteq [d]$ such that $|I| = |J|$.

* Let $\mathcal{M}$ be a matching between $I$ and $J$. Let $\mathcal{M}'$ be a matching obtained by taking a subgraph of $\mathcal{M}$. Then $\mathcal{M}'$ is also in $\mathcal{M}$.

If a matching field $\mathcal{M}$ also satisfies the following axioms, we call it a **matching ensemble**:

(left linkage) Let $\mathcal{M}$ be a matching between $I$ and $J$ in $\mathcal{M}$. Pick any $v \in [n] \setminus I$. Then there is an edge $(i, j) \in \mathcal{M}$ that we can replace with $(v, j)$ to get another matching $\mathcal{M}'$ in $\mathcal{M}$.

(right linkage) Let $\mathcal{M}$ be a matching between $I$ and $J$ in $\mathcal{M}$. Pick any $v \in [d] \setminus J$. Then there is an edge $(i, j) \in \mathcal{M}$ that we can replace with $(i, v)$ to get another matching $\mathcal{M}'$ in $\mathcal{M}$.

The collection of matchings described in Figures 5 and 6 are examples of matching ensembles.

**Theorem 4.2.** The extraction method described in the previous section is actually a bijection between triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and $(n, d)$-matching ensembles.

The proof of this theorem is quite technical, and will be omitted in this extended abstract.

Matching Ensemble is a powerful tool for dealing with triangulations of $\Delta_{n-1} \times \Delta_{d-1}$. For example, Ceballos et al. (2014) recently solved an extendability problem on triangulations by using our model of Matching Ensembles. There is an interesting conjecture by Santos:

**Conjecture 4.3** (Santos (2003)). Fix $n$ and $d$ and consider $\Delta_{n-1} \times \Delta_{d-1}$. Any two triangulations of this polytope are connected by a sequence of flips.

We say that there is a **flip** between two triangulations, if these two triangulations have a common subdivision and the only triangulations obtained by refining that subdivision is the two we started with. If one considers the case when $d = 3$, this corresponds to the usual flips of triangular and rhombus tiles
Ardila and Billey (2007). This is considered a very hard problem, since the usual model of describing triangulations via collection of spanning trees does not capture flips efficiently. In order to solve this conjecture using matching ensembles, we would first need to work on the following problems:

**Question 4.4.** *Can we describe subdivisions of $\Delta_{n-1} \times \Delta_{d-1}$ using a model similar to matching ensembles?*

Answering this question would give us an insight on what operation of matchings would correspond to flips of triangulations, and possibly lead to a proof of Santos’s conjecture.

## References

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

D. Bernstein and A. Zelevinsky. Combinatorics of maximal minors. *J. Algebraic Combin.*, 2(2):111–121, 1993.

C. Ceballos, A. Padrol, and C. Sarmiento. Dyck path triangulations and extendability. *ArXiv e-prints*, Sept. 2014. arXiv:math/1402.5111.

S. Oh and H. Yoo. Triangulations of product of two simplices and matching ensembles. *ArXiv e-prints*, Sept. 2013. arXiv:math/1311.6772.

A. Postnikov. Permutohedra, associahedra, and beyond. *Int. Math. Res. Not.*, 2009(6):1026–1106, 2009.

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