Ceballos, Cesar and Padrol, Arnau and Sarmiento, Camilo - 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)
Dyck path triangulations and extendability (extended abstract)

Authors: Ceballos, Cesar and Padrol, Arnau and Sarmiento, Camilo

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_{r\ n-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\geq k>n$, any triangulations 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.


Source : oai:HAL:hal-01337838v1
Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Submitted on: November 21, 2016
Keywords: triangulations,products of simplices,Dyck paths,tropical oriented matroids,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 24 times.
This article's PDF has been downloaded 75 times.