# Dyck path triangulations and extendability (extended abstract)

Cesar Ceballos, Arnau Padrol, Camilo Sarmiento

► To cite this version:

Cesar Ceballos, Arnau Padrol, Camilo Sarmiento. Dyck path triangulations and extendability (extended abstract). 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.73-84, 10.46298/dmtcs.2516 . hal-01337838

HAL Id: hal-01337838

https://hal.science/hal-01337838

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Dyck path triangulations and extendability
(extended abstract)

Cesar Ceballos<fnref n="1" />‡ and Arnau Padrol<fnref n="2" />§ and Camilo Sarmiento<fnref n="3" />¶

**Abstract.** We introduce the Dyck path triangulation of the cartesian product of two simplices $\Delta_{n-1} \times \Delta_{n-1}$. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of $\Delta_{rn-1} \times \Delta_{n-1}$ using rational Dyck paths. Our study of the Dyck path triangulation is motivated by extendability problems of partial triangulations of products of two simplices. We show that whenever $m \ge k > n$, any triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1} \times \Delta_{n-1}$. Moreover, with an explicit construction, we prove that the bound $k > n$ is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.

**Résumé.** Nous introduisons la triangulation par chemins de Dyck du produit cartésien de deux simplexes $\Delta_{n-1} \times \Delta_{n-1}$. Les simplexes maximaux de cette triangulation sont donnés par des chemins de Dyck, et cette construction se généralise de façon naturelle pour produire des triangulations de $\Delta_{rn-1} \times \Delta_{n-1}$ qui utilisent des chemins de Dyck rationnels. Notre étude de la triangulation par chemins de Dyck est motivée par des problèmes de prolongement de triangulations partielles de produits de deux simplexes. On montre que si $m \ge k > n$ alors toute triangulation de $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ se prolonge en une unique triangulation de $\Delta_{m-1} \times \Delta_{n-1}$. De plus, avec une construction explicite, nous montrons que la borne $k > n$ est optimale. Nous présentons aussi des interprétations de nos résultats dans le langage des matroïdes orientés tropicaux, qui sont analogues aux résultats classiques de la théorie des matroïdes orientés.

**Keywords:** triangulations, products of simplices, Dyck paths, tropical oriented matroids

<footnote n="1">¹Department of Mathematics and Statistics, York University, Toronto, Ontario M3J 1P3, Canada</footnote>

<footnote n="2">² Institut für Mathematik, Freie Universität Berlin, 14195 Berlin, Germany</footnote>

<footnote n="3">³ Institut für Algebra und Geometrie, Otto-von-Guericke-Universität Magdeburg, 39016 Magdeburg, Germany</footnote>

<footnote>†This is an extended abstract of the article [CPS15]</footnote>

<footnote>‡Supported by the government of Canada through a Banting Postdoctoral Fellowship. He was also supported by a York University research grant. URL: http://garsia.math.yorku.ca/~ceballos/</footnote>

<footnote>§Supported by the DFG Collaborative Research Center SFB/TR 109 "Discretization in Geometry and Dynamics". URL: http://page.mi.fu-berlin.de/arnaupadrol/</footnote>

<footnote>¶Partially supported by the IMPRS of the Max Planck Institute for Mathematics in the Sciences, Leipzig, and by the CDS, Magdeburg. URL: http://www-e.uni-magdeburg.de/sarmient/</footnote>
# 1 Introduction

The cartesian product of a standard $(m-1)$-simplex with a standard $(n-1)$-simplex is the $(m+n-2)$-dimensional polytope

$$ \Delta_{m-1} \times \Delta_{n-1} := \mathrm{conv}\{(e_i, e_j) : e_i \in \Delta_{m-1}, e_j \in \Delta_{n-1}\} \subset \mathbb{R}^{m+n}, $$

where $e_i$ and $e_j$ range over the standard basis vectors of $\mathbb{R}^m$ and $\mathbb{R}^n$, respectively.

Triangulations of the product of two simplices are intricate objects that have been extensively studied with various purposes. They are a key ingredient for understanding triangulations of products of polytopes [dL96, Hai91, OS03, San00]. Via the Cayley trick, they are in bijection with fine mixed subdivisions of a dilated simplex $m\Delta_{n-1}$ [San05], which provides a relation to tropical (pseudo) hyperplane arrangements and tropical oriented matroids [AD09, DS04]. Moreover, they have also attracted interest in algebraic geometry and commutative algebra [BB98, CHT07, GKZ94, Stu96] and in Schubert calculus [AB07].

In this paper, we present an intriguing family of triangulations of $\Delta_{n-1} \times \Delta_{n-1}$ that we call *Dyck path triangulations*, whose maximal simplices are described in terms of Dyck paths in a $n \times n$ grid under a cyclic action. The maximal simplices of the Dyck path triangulation of $\Delta_2 \times \Delta_2$ and the corresponding fine mixed subdivision of $3\Delta_2$ are illustrated in Figure 1.

<figure><img src="image_2.png" /><figcaption>Fig. 1: The Dyck path triangulation of $\Delta_2 \times \Delta_2$ drawn as a subdivision of $3\Delta_2$.</figcaption></figure>

Besides the combinatorial beauty of these triangulations, they are motivated by extendability problems of partial triangulations of $\Delta_{m-1} \times \Delta_{n-1}$. The $(k-1)$-skeleton of $\Delta_{m-1}$, which we denote by $\Delta_{m-1}^{(k-1)}$, is the polyhedral complex of all faces of $\Delta_{m-1}$ of dimension less than or equal to $k-1$. A partial triangulation of $\Delta_{m-1} \times \Delta_{n-1}$ is a triangulation of the polyhedral complex $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$. Such a triangulation is said to be *extendable* if it is equal to the restriction of a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$ to $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$. The smallest example of a non-extendable partial triangulation is shown in Figure 2(a); a more interesting example due to Santos [San13] is shown in Figure 2(b).

The question of extendability of triangulations of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ was first systematically considered for $k=2$ by Ardila and Ceballos in [AC13], who completely characterized the extendable triangulations of $\Delta_2^{(1)} \times \Delta_{n-1}$. There, in an attempt to prove the *Spread Out Simplices Conjecture* of Ardila and Billey [AB07, Conjecture 7.1], the authors formulated the *Acyclic System Conjecture* [AC13, Conjecture 5.7], which concerned a sufficient condition for the extendability of triangulations of $\Delta_{m-1}^{(1)} \times \Delta_{n-1}$. Shortly after, however, the Acyclic System Conjecture was disproved by Santos [San13]. These results motivate the search for necessary and sufficient conditions for extendability.

Our first contribution is the following extendability theorem.
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** Two examples of non-extendable partial triangulations. The triangulation in part (b), due to Francisco Santos [San13], is shown as a subdivision of $(3\Delta_3)^{(2)} = \partial(3\Delta_3)$.</figcaption></figure>

**Theorem (Theorem 4.2).** Let $m, n, k$ be positive integers such that $m \ge k > n$. Every triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1} \times \Delta_{n-1}$.

In considering whether the bound $k > n$ in Theorem 4.2 is optimal, we are led to the Dyck path triangulation of $\Delta_{n-1} \times \Delta_{n-1}$. This triangulation is our main tool to explicitly construct a family of partial triangulations that shows that the assertion of Theorem 4.2 does not generally hold when $m > k = n$.

**Theorem (Theorem 4.3).** For every $n \ge 2$ there is a non-extendable triangulation of $\partial(\Delta_n) \times \Delta_{n-1}$.

As suggested by its name, the Dyck path triangulation is based on Dyck paths and is related to Catalan combinatorics. We devote the rest of the paper to the study of this triangulation and its relatives. In particular, we present a natural generalization in terms of *rational Dyck paths* in the “Fuss-Catalan” case $(rn, n)$. It would be interesting to know if it can be further generalized to other families of rational Dyck paths.

Via the Cayley trick [San05], Theorems 4.2 and 4.3 transform into statements about the extendability of “partial fine mixed subdivisions” of $(n\Delta_{m-1})^{(k-1)}$, coming from triangulations of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$, which we refer to as *authentic subdivisions*.

**Corollary 1.1.** For $m \ge k > n$, every authentic subdivision of $(n\Delta_{m-1})^{(k-1)}$ can be extended to a unique fine mixed subdivision of $n\Delta_{m-1}$. Moreover, for every $n \ge 2$ there is a non-extendable authentic subdivision of $\partial(n\Delta_n)$.

Apart from providing a characterization of extendable of triangulations of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$, our results admit additional interpretations that render them of broader interest.

On the one hand, Theorems 4.2 and 4.3 naturally translate into the language of tropical oriented matroids (which we abbreviate as TOMs). This concept was introduced by Ardila and Develin as an analogue of classical oriented matroids for the tropical semiring [AD09]. The combinatorics of an arrangement of $m$ tropical pseudohyperplanes in the tropical space $\mathbb{T}^{n-1}$ is captured by its TOM. The *Topological Representation Theorem* establishes a correspondence between TOMs (with parameters $(m, n)$) and subdivisions of $\Delta_{m-1} \times \Delta_{n-1}$ [AD09, Hor12, OY11].

If $\mathcal{M}$ is a TOM of an arrangement whose pseudohyperplanes have labels in $[m]$, denote by $\mathcal{M}|_S$ the TOM of the subarrangement corresponding to the hyperplanes with labels in $S \subseteq [m]$. This turns Theorems 4.2 and 4.3 into the following statements, respectively.
**Corollary 1.2.** For each $S \in \binom{[m]}{n+1}$, let $M_S$ be the TOM of a generic arrangement of $n + 1$ pseudohyperplanes in $\mathbb{T}^{n-1}$ with labels in $S$. If the matroids in this collection are compatible, i.e. $M_{S|_{S \cap T}} = M_{T|_{S \cap T}}$ for every $T, S \in \binom{[m]}{n+1}$, then there exists a unique arrangement of $m$ pseudohyperplanes in $\mathbb{T}^{n-1}$ whose TOM $M$ fulfills $M|_S = M_S$.

**Corollary 1.3.** There exists a collection of pairwise compatible TOMs on the subsets in $\binom{[n+1]}{n}$ that cannot be completed to the TOM of an arrangement of $n + 1$ pseudohyperplanes in $\mathbb{T}^{n-1}$.

These corollaries should be compared with analogue results in classical oriented matroid theory: every oriented matroid of rank $n-1$ is completely determined by its submatroids with $n$ elements, and every compatible collection of submatroids with $n+1$ elements can be completed to a full oriented matroid (cf. [BLS$^+$93, Corollaries 3.6.3 and 3.6.4]).

On the other hand, Theorem 4.2 can be regarded as a “finiteness” result for triangulations of $\Delta_{m-1} \times \Delta_{n-1}$: it says that, as long as $m \ge n+1$, triangulations of $\Delta_{m-1} \times \Delta_{n-1}$ are “built” from the collection of triangulations of $\Delta_n \times \Delta_{n-1}$, no matter how large $m$ is. From this viewpoint, Theorem 4.2 should be contrasted with recent results in commutative algebra regarding finiteness properties of the generating sets of certain families of polynomial ideals (see, for instance, [HS12, HS07, Sno13]).

Here is the layout of this extended abstract. The next section contains some preliminaries concerning notation and representations for triangulations of products of simplices. The Dyck path triangulation is then presented in Section 3, along with the explicit construction behind Theorem 4.3. Finally, Section 4.1 contains the proof of our extendability results; in particular, Theorems 4.2 and 4.3.

## 2 Preliminaries

In this section, in order to set our notation and conventions, we recall some well-known facts related to triangulations of $\Delta_{m-1} \times \Delta_{n-1}$ (we refer to [DRS10, Section 6.2] for a more detailed exposition).

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Several representations of a triangulation of $\Delta_1 \times \Delta_2$.</figcaption></figure>

### Bipartite graphs and the matching ensemble representation

Let $K_{m,\bar{n}}$ be the complete bipartite graph on $m+n$ vertices, whose parts we label by $[m]$ and $[\bar{n}]^{(i)}$. A vertex $(e_i, e_j)$ of $\Delta_{m-1} \times \Delta_{n-1}$ can be represented as the undirected edge $(i, \bar{j})$ of $K_{m,\bar{n}}$. Every triangulation of $\Delta_{m-1} \times \Delta_{n-1}$ gives rise to a collection of subgraphs of $K_{m,\bar{n}}$, each one indexing the vertex set of a maximal simplex of the triangulation. As it turns out, this collection (and hence also the triangulation) is completely determined by the matchings contained in these subgraphs.

<footnote>(i) Throughout we use overlined numbers and variables to distinguish the vertices of both factors of $\Delta_{m-1} \times \Delta_{n-1}$.</footnote>
Recently, Suho Oh and Hwanchul Yoo [OY13] have found a concise characterization of the collections of perfect matchings that correspond to triangulations of $\Delta_{m-1} \times \Delta_{n-1}$, hence discovering a novel matching ensemble representation for triangulations of $\Delta_{m-1} \times \Delta_{n-1}$.

**Definition 2.1** ([OY13, Definition 4.1]). A family of perfect matchings $\mathcal{M}$ on the subgraphs of $K_{m,\bar{n}}$ induced by vertex sets $I \cup \bar{J}$, where $I \subset [m]$, $\bar{J} \subset [\bar{n}]$ and $|I| = |\bar{J}|$, is a matching ensemble if:

(SA). for each $I \subset [m]$ and $\bar{J} \subset [\bar{n}]$ with $|I| = |\bar{J}|$, there exists a unique $\mathfrak{m} \in \mathcal{M}$ on the subgraph of $K_{m,\bar{n}}$ induced by $I$ and $\bar{J}$ (supports axiom),

(CA). for each $\mathfrak{m} \in \mathcal{M}$ and for each (perfect sub-matching) $\mathfrak{m}' \subseteq \mathfrak{m}$, $\mathfrak{m}' \in \mathcal{M}$ (closure axiom), and

(LA). for each $\mathfrak{m} \in \mathcal{M}$ and for each $v \in [n] \cup [\bar{m}] \setminus (I \cup \bar{J})$, there are two edges $e' \in K_{m,\bar{n}}$ and $e \in \mathfrak{m}$ sharing a common vertex such that $v \in e'$ and $(\mathfrak{m} \setminus e \cup e') \in \mathcal{M}$ (linkage axiom).

**Theorem 2.2** ([OY13, Theorem 5.4]). There is a bijection between matching ensembles of $K_{m,\bar{n}}$ and triangulations of $\Delta_{m-1} \times \Delta_{n-1}$.

### Grid representation

The $m \times n$ grid, which we denote by $\mathcal{G}_{m \times n}$, is a rectangular array of width $m$ and height $n$ composed of $mn$ unit squares. Every unit square in $\mathcal{G}_{m \times n}$ has a position $(i, \bar{j})$ in the grid, where index $i$ increases to the right and index $j$ increases upwards. Thus, the vertex $(e_i, e_j)$ in $\Delta_{m-1} \times \Delta_{n-1}$ is represented by the square at position $(i, \bar{j})$ in $\mathcal{G}_{m \times n}$. The grid representation of a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$ is the collection of grids representing the vertex sets of the maximal simplices of the triangulation.

### Mixed subdivisions

In order to illustrate some of our constructions, we shall draw triangulations of $\Delta_{m-1} \times \Delta_{n-1}$ as fine mixed subdivisions of $m\Delta_{n-1}$. Let $\mathcal{T}$ be a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$. To each simplex $s \in \mathcal{T}$ associate the simplex $s_i = \text{conv}\{e_j : (e_i, e_j) \in s\} \subset \Delta_{n-1}$. The set of Minkowski sums $\{s_1 + \cdots + s_m : s \in \mathcal{T}\}$ forms a mixed subdivision of $m\Delta_{n-1}$. The Cayley trick states that this correspondence is a bijection between triangulations of $\Delta_{m-1} \times \Delta_{n-1}$ and fine mixed subdivisions of $m\Delta_{n-1}$ (see [San05] for more details).

## 3 The Dyck path triangulation and some relatives

There are two main ingredients towards our construction for Theorem 4.3: the *Dyck path triangulation* and the *extended Dyck path triangulation*. We present them here, together with a *generalized version*.

### 3.1 The Dyck path triangulation

The first ingredient is a triangulation of $\Delta_{n-1} \times \Delta_{n-1}$ that we call the *Dyck path triangulation* and denote by $\mathcal{D}_n$. This triangulation can be described in terms of *Dyck paths* in the grid representation, that is, monotonically increasing paths from the square $(1, \bar{1})$ to the square $(n, \bar{n})$ of $\mathcal{G}_{n \times n}$, in which every square $(i, \bar{j})$ satisfies $i \le \bar{j}$. The maximal simplices of $\mathcal{D}_n$ are the Dyck paths in $\mathcal{G}_{n \times n}$, together with the orbit of simplices they generate under an action that cyclically shifts the indices in both factors of $\Delta_{n-1} \times \Delta_{n-1}$ simultaneously. An example for $n=3$ is depicted in Figure 4(a).
<figure><img src="image_5.png" /><figcaption>Fig. 4: The Dyck path triangulation of $\Delta_2 \times \Delta_2$ and its flipped version in the grid and mixed subdivisions representations.</figcaption></figure>

The perfect matching representation of $\mathcal{D}_n$ is also easy to describe. We begin with the set of all perfect matchings on the subgraphs of $K_{n,\bar{n}}$ induced by $I \subset [n]$, $\bar{J} \subset [\bar{n}]$ (with $|I| = |\bar{J}|$) which are non-crossing (nc) and weakly increasing (wi), that is, those matchings $m$ that satisfy

$$ \left\{ \begin{array}{l} i < i' \Rightarrow \bar{j} < \bar{j}' \text{ for every } (i, \bar{j}), (i', \bar{j}') \in \mathfrak{m}, \\ i \le \bar{j} \text{ for every } (i, \bar{j}) \in \mathfrak{m} \end{array} \right. . \qquad (\text{nc+wi}) $$

Next, for $\ell \in [n]$, we introduce the collection of matchings of the form

$$ \left\{ \left( i + \ell \pmod{n}, \bar{j} + \ell \pmod{n} \right) : (i, \bar{j}) \in \mathfrak{m}, \mathfrak{m} \text{ fulfills (nc+wi)} \right\}, \qquad (\text{cyc}) $$

obtained by “cyclically shifting” the indices of the perfect matchings that satisfy (nc+wi), and call $M_n$ the set of all matchings obtained after ranging over all $\ell \in [n]$ (see Figure 5).

<figure><img src="image_6.png" /><figcaption>Fig. 5: A perfect matching on $K_{\{1,2,5\},\{\bar{2},\bar{4},\bar{5}\}}$ satisfying (nc+wi), together with its cyclic orbit (cyc).</figcaption></figure>

Due to lack of space, we omit the proof of the following theorem and refer to [CPS15] for details.

**Theorem 3.1.** The collection of matchings $M_n$ constitutes a matching ensemble of $K_{n,\bar{n}}$, and its associated triangulation of $\Delta_{n-1} \times \Delta_{n-1}$ is the Dyck path triangulation $\mathcal{D}_n$.

Moreover, $\mathcal{D}_n$ is a regular triangulation, which can be obtained by the height function $h: \Delta_{n-1} \times \Delta_{n-1} \to \mathbb{R}$ that assigns to the point $(e_i, e_j)$ the height $h_{ij} = c^{j-i} (\text{mod } n)$, for some real number $c > 1$ sufficiently large.

**Remark 3.2.** The Dyck path triangulation of $\Delta_{n-1} \times \Delta_{n-1}$ is a natural refinement of a coarse regular subdivision introduced by Gelfand, Kapranov and Zelevinsky in [GKZ94, Example 3.14]. Indeed, the union of all Dyck paths is a cell of this subdivision, and the remaining cells are obtained by applying the cyclic action that shifts the indices.
<figure><img src="image_7.png" /><figcaption>Fig. 6: Illustration of the extended Dyck path triangulation $\mathcal{D}_n^{\text{ext}}$.</figcaption></figure>

For us, the crucial property of $\mathcal{D}_n$ that underlies the construction for Theorem 4.3, is that it admits a geometric bistellar flip supported on the circuit $C = (C^+, C^-)$ of maximal dimension given by

$$C^+ := \{(e_1, e_2), (e_2, e_3), \dots, (e_{n-1}, e_n), (e_n, e_1)\} \quad (1)$$

$$C^- := \{(e_1, e_1), (e_2, e_2), \dots, (e_{n-1}, e_{n-1}), (e_n, e_n)\}.$$

Therefore, performing this flip consists in replacing only the simplices in $T^+ := \{C \setminus \{v\} : v \in C^+\} \subset \mathcal{D}_n$ by those in $T^- := \{C \setminus \{v\} : v \in C^-\}$, while leaving the rest of $\mathcal{D}_n$ intact; in particular, the flip does not alter the restriction of $\mathcal{D}_n$ to the boundary of $\Delta_{n-1} \times \Delta_{n-1}$. We refer the reader to [DRS10, Section 4.4.1] for the precise definition of a geometric bistellar flip. We call the resulting triangulation the flipped Dyck path triangulation, and denote it by $\mathcal{D}_n^{\text{flip}}$; it is illustrated for $n = 3$ in Figure 4(b).

## 3.2 The extended Dyck path triangulation

The second ingredient is a natural extension of $\mathcal{D}_n$ to a triangulation of $\Delta_n \times \Delta_{n-1}$, which we call the extended Dyck path triangulation and denote by $\mathcal{D}_n^{\text{ext}}$. In the grid representation, an extended Dyck path is formed by several Dyck paths, concatenated one after the other in the grid $G_{(n+1) \times n}$, and a square in the $(n+1)$-th column and last row of each Dyck path; this is illustrated in Figure 6(a). The maximal simplices of $\mathcal{D}_n^{\text{ext}}$ are given by the extended Dyck paths in $G_{(n+1) \times n}$, together with the orbit of simplices they define under an action that cyclically shifts the indices in both factors of $\Delta_{[n]} \times \Delta_{n-1} \subset \Delta_n \times \Delta_{n-1}$ simultaneously (note that here the action ignores the $(n+1)$-th vertex of the first factor). The simplices of the extended Dyck path triangulation for $n = 3$ are shown in Figure 6(b). Interestingly, the simplices obtained this way constitute a regular triangulation of $\Delta_n \times \Delta_{n-1}$.

We can similarly describe its matching ensemble. Now we start with the set of matchings $m$ between $I \subset [n+1]$ and $\bar{J} \subset [\bar{n}]$ with the property

$$\left\{ \begin{array}{l} i < i' \Rightarrow \bar{j} < \bar{j}' \text{ for every } (i, \bar{j}), (i', \bar{j}') \in \mathfrak{m}, \\ i \le \bar{j} \text{ for every } (i, \bar{j}) \in \mathfrak{m} \text{ with } i \ne n+1. \end{array} \right. \qquad (\text{nc+wi}^{\text{ext}})$$

As before, we consider the set of perfect matchings on induced subgraphs of $K_{n+1, \bar{n}}$ of the form
$$ \{ (\rho_{\ell}(i), \bar{j} + \ell \pmod{n}): (i, \bar{j}) \in \mathfrak{m}, \mathfrak{m} \text{ fulfills } (\mathfrak{nc}+\mathfrak{wi}^{\text{ext}}) \}, \quad (\text{cyc}^{\text{ext}}) $$

$$ \text{where } \rho_{\ell}(i) := \begin{cases} i + \ell \pmod{n} & \text{if } i \neq n+1 \\ n+1 & \text{otherwise} \end{cases}, $$

with $\ell$ ranging over $[n]$, and denote it by $M_n^{\text{ext}}$.

**Theorem 3.3.** The collection of matchings $M_n^{\text{ext}}$ constitutes a matching ensemble of $K_{n+1, \bar{n}}$, and its associated triangulation of $\Delta_n \times \Delta_{n-1}$ is the extended Dyck path triangulation $\mathfrak{D}_n^{\text{ext}}$.

Moreover, $\mathfrak{D}_n^{\text{ext}}$ is a regular triangulation, and can be obtained by assigning the height $h_{ij}$ to the point $(e_i, e_j)$, defined by:

$$ h_{ij} = \begin{cases} c^{j-i} & \text{if } j \ge i \\ c^{n+j-i} & \text{if } j < i < n+1 \\ 1 & \text{if } i = n+1; \end{cases} \quad (2) $$

where $c > 1$ is a sufficiently large real number.

Again, we refer to [CPS15] for the complete proof of this statement.

## 3.3 The generalized Dyck path triangulations

Dyck path triangulations have a natural generalization to triangulations $\mathfrak{D}_{(rn,n)}$ of $\Delta_{rn-1} \times \Delta_{n-1}$ for any $r > 0$. This shows an interesting connection to rational Catalan combinatorics (cf. [AHJ13, ARW13]).

<figure><img src="image_8.png" /><figcaption>**Fig. 7:** The triangulation $\mathfrak{D}_{(6,3)}$ and its extension $\mathfrak{D}_{(6,3)}^{\text{ext}}$.</figcaption></figure>

Define an $(rn, n)$-Dyck path$^{(ii)}$ in the grid $\mathcal{G}_{rn \times n}$ as a monotonically increasing path from $(1, \bar{1})$ to $(rn, \bar{n})$ such that every step $(i, \bar{j})$ satisfies $i \le rj$.

The $(rn, n)$-Dyck path triangulation $\mathfrak{D}_{(rn,n)}$ is the triangulation of $\Delta_{rn-1} \times \Delta_{n-1}$ that has as maximal simplices the $(rn, n)$-Dyck paths together with their orbits under the action that maps $(i, \bar{j}) \mapsto (i + r \pmod{rn}, \bar{j} + 1 \pmod{n})$. An example is illustrated in Figure 7.

**Theorem 3.4.** The $(rn, n)$-Dyck path triangulation $\mathfrak{D}_{(rn,n)}$ is a triangulation of $\Delta_{rn-1} \times \Delta_{n-1}$. Moreover, it is regular.

<footnote>(ii) The standard definition of a rational $(a, b)$-Dyck path is slightly different: it uses a grid from $(0, 0)$ to $(a, b)$ and imposes that the lattice points in the path are above the main diagonal. It is used, for example, in [ARW13].</footnote>
# 4 Extendability of partial triangulations

## 4.1 Extendable partial triangulations

In order to present the proof of our extendability Theorem 4.2, we first observe that, whenever $m \ge k \ge n$, if a triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ extends to a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$, then this extension is unique. We omit the proof, which can be easily deduced from Theorem 2.2 (it is also implicit in the proof of a classical result of Dey, cf. [Dey93, Section 3] and [DRS10, Lemma 8.4.1]).

**Lemma 4.1.** Let $m, n, k$ be natural numbers such that $n \ge 2$ and $m \ge k \ge n$. Every triangulation of $\Delta_{m-1} \times \Delta_{n-1}$ is uniquely determined by its restriction to $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$.

Not every triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ can be extended to a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$, as is already known from the familiar non-extendable triangulation of $\Delta_2^{(1)} \times \Delta_1$ depicted in Figure 2(a), often called “the mother of all examples”. However, by strengthening the hypotheses to $k > n$, it becomes possible to certify extendability.

**Theorem 4.2.** Let $m, n, k$ be positive integers such that $m \ge k > n$. Every triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ extends to a unique triangulation of $\Delta_{m-1} \times \Delta_{n-1}$.

*Proof.* Let $\mathcal{T}'$ be a triangulation of $\Delta_{m-1}^{(k-1)} \times \Delta_{n-1}$ in the conditions of the theorem, and let $\mathcal{M}$ be the set of all perfect matchings contained in the simplices of $\mathcal{T}'$, when viewed as subgraphs of $K_{m,\bar{n}}$. We prove that $\mathcal{M}$ is necessarily a matching ensemble (cf. Definition 2.1) and hence, by Theorem 2.2, that it is the family of perfect matchings of a triangulation of $\Delta_{m-1} \times \Delta_{n-1}$.

(SA). For each $I \subset [n], \bar{J} \subset [\bar{m}]$ with $|I| = |\bar{J}| \le n$, the restriction $\mathcal{T}'|_{\Delta_I \times \Delta_J}$ is a triangulation of the face $\Delta_I \times \Delta_J$ of $\Delta_{m-1} \times \Delta_{n-1}$. Let $\mathcal{M}|_{K_{I,\bar{J}}}$ be the set of perfect matchings associated to this restricted triangulation. Since this face is a product of simplices, Theorem 2.2 applies, so that there is a unique perfect matching $m \in \mathcal{M}|_{K_{I,\bar{J}}}$ on the induced subgraph $K_{I,\bar{J}}$.

(CA). Again, for each perfect matching $m \in \mathcal{M}$ on $K_{I,\bar{J}}$, $\mathcal{T}'|_{\Delta_I \times \Delta_J}$ is a legal triangulation, as are all of its restrictions. In particular, by Theorem 2.2, it follows that $m' \in \mathcal{M}$ whenever $m' \subseteq m$.

(LA). Fix a perfect matching $m \in \mathcal{M}$ on $K_{I,\bar{J}}$, where $|I| = |\bar{J}| \le n$, and let $v \in ([m] \cup [\bar{n}]) \setminus ([I] \cup [\bar{J}])$. Observe that $\mathcal{T}'|_{\Delta_{I \cup v} \times \Delta_J}$ (resp. $\mathcal{T}'|_{\Delta_I \times \Delta_{J \cup v}}$) is a legal triangulation, because $k \ge n+1$. In particular, that means that there are two edges $e' \in K_{I \cup v, \bar{J}}$ (resp. $e' \in K_{I, \bar{J} \cup v}$) and $e \in m$ sharing a common vertex such that $v \in e'$ and $(m \setminus e \cup e') \in \mathcal{M}$.

Finally, the uniqueness of the resulting triangulation was established in Lemma 4.1. □

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

## 4.2 Non-extendable partial triangulations

The restriction of $\mathcal{D}_n^{\text{ext}}$ to $\partial(\Delta_n) \times \Delta_{n-1}$ gives a partial triangulation of $\Delta_n \times \Delta_{n-1}$ whose restriction to the facet $\Delta_{[n]} \times \Delta_{n-1}$ coincides with $\mathcal{D}_n$. Denote by $\partial(\mathcal{D}_n^{\text{ext}})$ this restricted triangulation, whose facet $\Delta_{[n]} \times \Delta_{n-1}$ admits a bistellar flip supported on the circuit (1). By this, we mean that the triangulation of the facet $\Delta_{[n]} \times \Delta_{n-1}$ can be changed from $\mathcal{D}_n$ to $\mathcal{D}_n^{\text{flip}}$, without affecting the triangulation of the remaining facets of $\partial(\Delta_n) \times \Delta_{n-1}$. Hence, the result of the flip is still a triangulation of $\partial(\Delta_n) \times \Delta_{n-1}$, which we call *flipped extended Dyck path triangulation* and denote $\partial(\mathcal{D}_n^{\text{ext}})^{\text{flip}}$. An example is depicted in Figure 8.
<figure><img src="image_10.png" /><figcaption>Fig. 8: A non-extendable triangulation $\partial(\mathfrak{D}_n^{\text{ext}})^{\text{flip}}$ of $\partial(\Delta_3) \times \Delta_{3-1}$.</figcaption></figure>

**Theorem 4.3.** *The flipped extended Dyck path triangulation $\partial(\mathfrak{D}_n^{\text{ext}})^{\text{flip}}$ of $\partial(\Delta_n) \times \Delta_{n-1}$ is non-extendable.*

*Proof.* The triangulation $\partial(\mathfrak{D}_n^{\text{ext}})^{\text{flip}}$ of $\partial(\Delta_n) \times \Delta_{n-1}$ produces a collection of perfect matchings on all induced subgraphs of $K_{n+1, \bar{n}}$, that we refer to as $M'$ (for which the reader can check that the axioms (SA) and (CA) hold). Observe that, by construction, $M_n^{\text{ext}}$ and $M'$ agree on all the induced subgraphs $K_{I, [\bar{n}]}$, where $n \notin I \subset [n+1]$. In contrast, the triangulation $\mathfrak{D}_n^{\text{flip}}$ of $\Delta_{n-1} \times \Delta_{n-1}$ contributes the following matching on the induced subgraph $K_{[n], [\bar{n}]}$:

$$m := \{(1, \bar{2}), (2, \bar{3}), (3, \bar{4}), \dots, (n-1, \bar{n}), (n, \bar{1})\}.$$

Suppose, for the sake of absurdity, that axiom (LA) holds for $m \in M'$. Then, there is a unique perfect matching $m' \in M'$ on $K_{[n] \setminus w \cup n+1, [\bar{n}]}$ that differs from $m$ in a single edge. However, letting $w = n \in [n]$ (which we may by symmetry), we see that the unique perfect matching on $K_{[n] \setminus w \cup n+1, [\bar{n}]}$ in the matching ensemble $M_n^{\text{ext}}$ is

$$\{(1, \bar{1}), (2, \bar{2}), (3, \bar{3}), \dots, (n-1, \overline{n-1}), (n+1, \bar{n})\},$$

so $m$ cannot satisfy axiom (LA). Therefore, $M'$ is not a matching ensemble and $\partial(\mathfrak{D}_n^{\text{ext}})^{\text{flip}}$ cannot be extended to a triangulation of $\Delta_n \times \Delta_{n-1}$. $\square$

**Corollary 4.4.** *For every $m \ge n$ there exist non-extendable triangulations of $\Delta_m^{(n-1)} \times \Delta_{n-1}$.*

## Acknowledgements

The authors want to thank Francisco Santos for many interesting and enlightening conversations.

## References

[AB07] Federico Ardila and Sara Billey. Flag arrangements and triangulations of products of simplices. *Adv. Math.*, 214(2):495–524, 2007.

[AC13] Federico Ardila and Cesar Ceballos. Acyclic systems of permutations and fine mixed subdivisions of simplices. *Discrete Comput. Geom.*, 49(3):485–510, 2013.

[AD09] Federico Ardila and Mike Develin. Tropical hyperplane arrangements and oriented matroids. *Math. Z.*, 262(4):795–816, 2009.

[AHJ13] Drew Armstrong, Christopher R. H. Hanusa, and Brant C. Jones. Results and conjectures on simultaneous core partitions. *arXiv:1308.0572v1*, page 17 pages, 2013.
[ARW13] Drew Armstrong, Brendon Rhoades, and Nathan Williams. Rational associahedra and non-crossing partitions. *Electron. J. Combin.*, 20(3):Paper 54, 27, 2013.

[Bay93] Margaret M. Bayer. Equidecomposable and weakly neighborly polytopes. *Isr. J. Math.*, 81(3):301–320, 1993.

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

[BCS88] L.J. Billera, R. Cushman, and J.A. Sanders. The Stanley decomposition of the harmonic oscillator. *Indag. Math.*, 50(4):375–393, 1988.

[Biz54] M. T. L. Bizley. Derivation of a new formula for the number of minimal lattice paths from (0,0) to (km,kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula for the number of paths which may touch but do not rise above this line. *Journal of the Institute of Actuaries (JIA)*, 80:55–62, 1954.

[BLS+93] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. *Oriented matroids*. Encyclopedia of Mathematics and Its Applications. 46. Cambridge: Cambridge University Press. 516 p., 1993.

[CHT07] Aldo Conca, Serkan Hosten, and Rekha R. Thomas. Nice Initial Complexes of Some Classical Ideals. *Algebraic and geometric combinatorics, Contemp. Math.*, 423:11–42, 2007.

[CPS15] Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento. Dyck path triangulations and extendability. *Journal of Combinatorial Theory, Series A*, 131:187–208, 2015.

[Dey93] Tamal Krishna Dey. On counting triangulations in $d$ dimensions. *Computational Geometry: Theory and Applications*, 3(6):315–325, 1993.

[dL96] J. A. de Loera. Nonregular triangulations of products of simplices. *Discrete Comput. Geom.*, 15(3):253–264, 1996.

[DRS10] Jesús A. De Loera, Jörg Rambau, and Francisco Santos. *Triangulations*, volume 25 of *Algorithms and Computation in Mathematics*. Springer-Verlag, Berlin, 2010. Structures for algorithms and applications.

[DS04] Mike Develin and Bernd Sturmfels. Tropical convexity. *Doc. Math.*, 9:1–27 (electronic), 2004.

[GKZ94] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky. *Discriminants, resultants, and multidimensional determinants*. Mathematics: Theory & Applications. Birkhäuser Boston Inc., Boston, MA, 1994.

[Hai91] Mark Haiman. A simple and relatively efficient triangulation of the $n$-cube. *Discrete Comput. Geom.*, 6(4):287–289, 1991.
[Hor12] Silke Horn. A topological representation theorem for tropical oriented matroids. In *24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)*, Discrete Math. Theor. Comput. Sci. Proc., AR, pages 135–146. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012.

[HS07] Serkan Hoşten and Seth Sullivant. A finiteness theorem for Markov bases of hierarchical models. *J. Combin. Theory Ser. A*, 114(2):311–321, 2007.

[HS12] Christopher J Hillar and Seth Sullivant. Finite Gröbner bases in infinite dimensional polynomial rings and applications. *Adv. Math.*, 229(1):1–25, 2012.

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

[OT12] Steffen Oppermann and Hugh Thomas. Higher dimensional cluster combinatorics and representation theory. *J. Eur. Math. Soc. (JEMS)*, 2012. To appear.

[OY11] Suho Oh and Hwanchul Yoo. Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and tropical oriented matroids. In *23rd International Conference on Formal Power Series and Algebraic Combinatorics (FP-SAC 2011)*, Discrete Math. Theor. Comput. Sci. Proc., AO, pages 717–728. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011.

[OY13] Suho Oh and Hwanchul Yoo. Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Matching Ensembles. *arXiv:1311.6772v1*, page 13 pages, 2013.

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

[San02] Francisco Santos. Triangulations of oriented matroids. *Mem. Am. Math. Soc.*, 741:80 p., 2002.

[San05] Francisco Santos. The Cayley trick and triangulations of products of simplices. *Integer Points in Polyhedra – Geometry, Number Theory, Algebra, Optimization, Contemp. Math.*, 374:151–177, 2005.

[San13] Francisco Santos. Some acyclic systems of permutations are not realizable by triangulations of a product of simplices. *Algebraic and Combinatorial Aspects of Tropical Geometry, Contemp. Math.*, 589:317–328, 2013.

[Sno13] Andrew Snowden. Syzygies of Segre embeddings and $\Delta$-modules. *Duke Math. J.*, 162(2):225–277, 2013.

[Stu96] Bernd Sturmfels. *Gröbner bases and convex polytopes*, volume 8 of *University Lecture Series*. American Mathematical Society, Providence, RI, 1996.