Dyck path triangulations and extendability

DOI10.1016/J.JCTA.2014.10.009zbMATH Open1307.51017arXiv1402.5111OpenAlexW2012333844MaRDI QIDQ482245FDOQ482245

Camilo Sarmiento, Arnau Padrol, Cesar Ceballos

Publication date: 19 December 2014

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We introduce the Dyck path triangulation of the cartesian product of two simplices $Delt{a}_{n-1}imesDelt{a}_{n-1}$. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of $Delt{a}_{rn-1}imesDelt{a}_{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 $mgeqk>n$, any triangulation of $Delt{a}_{m-1}^{(k-1)}imesDelt{a}_{n-1}$ extends to a unique triangulation of $Delt{a}_{m-1}imesDelt{a}_{n-1}$. Moreover, with an explicit construction, we prove that the bound $k>n$ is optimal. We also exhibit interesting interpretations of our results in the language of tropical oriented matroids, which are analogous to classical results in oriented matroid theory.

Full work available at URL: https://arxiv.org/abs/1402.5111

zbMATH Keywords

triangulationsDyck pathstropical oriented matroidsproducts of simplices

Mathematics Subject Classification ID

Oriented matroids in discrete geometry (52C40) Polyhedra and polytopes; regular figures, division of spaces (51M20) Polytopes and polyhedra (52B99)

Cites Work

• Tropical convexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Triangulations. Structures for algorithms and applications
• On counting triangulations in \(d\) dimensions
• Rational associahedra and noncrossing partitions
• Results and conjectures on simultaneous core partitions
• A finiteness theorem for Markov bases of hierarchical models
• Syzygies of Segre embeddings and \(\Delta\)-modules
• Tropical hyperplane arrangements and oriented matroids
• Title not available (Why is that?)
• Finite Gröbner bases in infinite dimensional polynomial rings and applications
• Flag arrangements and triangulations of products of simplices
• A topological representation theorem for tropical oriented matroids
• Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Tropical Oriented Matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotically efficient triangulations of the \(d\)-cube
• Nonregular triangulations of products of simplices
• A point set whose space of triangulations is disconnected
• The geometry of products of minors
• Acyclic systems of permutations and fine mixed subdivisions of simplices
• Some acyclic systems of permutations are not realizable by triangulations of a product of simplices
• A simple and relatively efficient triangulation of the n-cube

Cited In (12)

• Classification of uniform flag triangulations of the boundary of the full root polytope of type A
• Extension to Even Triangulations
• A Lower Bound Technique for Triangulations of Simplotopes
• Matching fields and lattice points of simplices
• Refined face count in uniform triangulations of the Legendre polytope
• On the subdivision algebra for the polytope \(\mathcal{U}_{I,\overline{J}}\)
• Geometry of \(\nu\)-Tamari lattices in types \(A\) and \(B\)
• A subdivision algebra for a product of two simplices via flow polytopes
• Partial Dyck paths with Air Pockets
• Geometry of $\nu $-Tamari lattices in types $A$ and $B$
• Tropical Catalan subdivisions
• Dyck paths and positroids from unit interval orders

This page was built for publication: Dyck path triangulations and extendability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q482245)