Cesar Ceballos ; Arnau Padrol ; Camilo Sarmiento

Dyck path triangulations and extendability (extended abstract)
dmtcs:2516 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2015,
DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)

https://doi.org/10.46298/dmtcs.2516
Dyck path triangulations and extendability (extended abstract)Article
Authors: Cesar Ceballos ^{1}; Arnau Padrol ^{2}; Camilo Sarmiento ^{3}
NULL##NULL##NULL
Cesar Ceballos;Arnau Padrol;Camilo Sarmiento
1 Department of Mathematics and Statistics [Toronto]
2 Institut für Mathematik
3 Institut fuer Algebra und Geometrie, Magdeburg
We introduce the Dyck path triangulation of the cartesian product of two simplices $\Delta_{n1}\times\Delta_{n1}$. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of $\Delta_{r\ n1}\times\Delta_{n1}$ 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\geq k>n$, any triangulations of $\Delta_{m1}^{(k1)}\times\Delta_{n1}$ extends to a unique triangulation of $\Delta_{m1}\times\Delta_{n1}$. 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.