×

Dyck path triangulations and extendability. (English) Zbl 1307.51017

Summary: 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 the construction naturally generalizes to certain 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 triangulation of the product of the \(k\)-skeleton of \(\Delta_{m-1}\) with \(\Delta_{n-1}\) extends to a unique triangulation of \(\Delta_{m-1} \times\Delta_{n-1}\). Moreover, using the Dyck path triangulation, we prove that the bound \(k>n\) is optimal. We also exhibit interpretations of our results in the language of tropical oriented matroids that are analogous to classical results in oriented matroid theory.

MSC:

51M20 Polyhedra and polytopes; regular figures, division of spaces
14T05 Tropical geometry (MSC2010)
52B99 Polytopes and polyhedra
52C40 Oriented matroids in discrete geometry
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ardila, Federico; Billey, Sara, Flag arrangements and triangulations of products of simplices, Adv. Math., 214, 2, 495-524 (2007) · Zbl 1194.14078
[2] Ardila, Federico; Ceballos, Cesar, Acyclic systems of permutations and fine mixed subdivisions of simplices, Discrete Comput. Geom., 49, 3, 485-510 (2013) · Zbl 1267.05301
[3] Ardila, Federico; Develin, Mike, Tropical hyperplane arrangements and oriented matroids, Math. Z., 262, 4, 795-816 (2009) · Zbl 1175.52024
[4] Armstrong, Drew; Hanusa, Christopher R. H.; Jones, Brant C., Results and conjectures on simultaneous core partitions (2013), 17 pp · Zbl 1297.05024
[5] Armstrong, Drew; Rhoades, Brendon; Williams, Nathan, Rational associahedra and noncrossing partitions, Electron. J. Combin., 20, 3 (2013), Paper 54, 27 · Zbl 1295.05051
[6] Babson, Eric K.; Billera, Louis J., The geometry of products of minors, Discrete Comput. Geom., 20, 2, 231-249 (1998) · Zbl 0924.52005
[7] Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter M., Oriented Matroids, Encyclopedia Math. Appl., vol. 46 (1993), Cambridge University Press: Cambridge University Press Cambridge, 516 p · Zbl 0773.52001
[8] Conca, Aldo; Hosten, Serkan; Thomas, Rekha R., Nice initial complexes of some classical ideals, (Algebraic and Geometric Combinatorics. Algebraic and Geometric Combinatorics, Contemp. Math., vol. 423 (2007)), 11-42 · Zbl 1116.13015
[9] de Loera, J. A., Nonregular triangulations of products of simplices, Discrete Comput. Geom., 15, 3, 253-264 (1996) · Zbl 0851.52014
[10] De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco, Triangulations: Structures for Algorithms and Applications, Algorithms Comput. Math., vol. 25 (2010), Springer-Verlag: Springer-Verlag Berlin · Zbl 1207.52002
[11] Develin, Mike; Sturmfels, Bernd, Tropical convexity, Doc. Math., 9, 1-27 (2004), (electronic) · Zbl 1054.52004
[12] Dey, Tamal Krishna, On counting triangulations in \(d\) dimensions, Comput. Geom., 3, 6, 315-325 (1993) · Zbl 0801.68155
[13] Gelfand, I. M.; Kapranov, M. M.; Zelevinsky, A. V., Discriminants, Resultants, and Multidimensional Determinants, Math. Theory Appl. (1994), Birkhäuser Boston Inc.: Birkhäuser Boston Inc. Boston, MA · Zbl 0827.14036
[14] Haiman, Mark, A simple and relatively efficient triangulation of the \(n\)-cube, Discrete Comput. Geom., 6, 4, 287-289 (1991) · Zbl 0727.68044
[15] Hillar, Christopher J.; Sullivant, Seth, Finite Gröbner bases in infinite dimensional polynomial rings and applications, Adv. Math., 229, 1, 1-25 (2012) · Zbl 1233.13012
[16] Horn, Silke, A topological representation theorem for tropical oriented matroids, (24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2012. 24th International Conference on Formal Power Series and Algebraic Combinatorics. 24th International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2012, Discrete Math. Theor. Comput. Sci. Proc., AR (2012), Assoc. Discrete Math. Theor. Comput. Sci.: Assoc. Discrete Math. Theor. Comput. Sci. Nancy), 135-146 · Zbl 1337.05113
[17] Hoşten, Serkan; Sullivant, Seth, A finiteness theorem for Markov bases of hierarchical models, J. Combin. Theory Ser. A, 114, 2, 311-321 (2007) · Zbl 1111.62053
[18] Oh, Suho; Yoo, Hwanchul, Triangulations of \(\Delta_{n - 1} \times \Delta_{d - 1}\) and tropical oriented matroids, (23rd International Conference on Formal Power Series and Algebraic Combinatorics. 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011. 23rd International Conference on Formal Power Series and Algebraic Combinatorics. 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011, Discrete Math. Theor. Comput. Sci. Proc., AO (2011), Assoc. Discrete Math. Theor. Comput. Sci.: Assoc. Discrete Math. Theor. Comput. Sci. Nancy), 717-728 · Zbl 1366.52025
[19] Oh, Suho; Yoo, Hwanchul, Triangulations of \(\Delta_{n - 1} \times \Delta_{d - 1}\) and matching ensembles (2013), 13 pp · Zbl 1366.52025
[20] Orden, David; Santos, Francisco, Asymptotically efficient triangulations of the \(d\)-cube, Discrete Comput. Geom., 30, 4, 509-528 (2003) · Zbl 1042.52009
[21] Santos, Francisco, A point set whose space of triangulations is disconnected, J. Amer. Math. Soc., 13, 3, 611-637 (2000) · Zbl 0958.52017
[22] Santos, Francisco, The Cayley trick and triangulations of products of simplices, (Integer Points in Polyhedra - Geometry, Number Theory, Algebra, Optimization. Integer Points in Polyhedra - Geometry, Number Theory, Algebra, Optimization, Contemp. Math., vol. 374 (2005)), 151-177 · Zbl 1079.52508
[23] Santos, Francisco, Some acyclic systems of permutations are not realizable by triangulations of a product of simplices, (Algebraic and Combinatorial Aspects of Tropical Geometry. Algebraic and Combinatorial Aspects of Tropical Geometry, Contemp. Math., vol. 589 (2013)), 317-328 · Zbl 1282.52013
[24] Snowden, Andrew, Syzygies of Segre embeddings and Δ-modules, Duke Math. J., 162, 2, 225-277 (2013) · Zbl 1279.13024
[25] Sturmfels, Bernd, Gröbner Bases and Convex Polytopes, Univ. Lecture Ser., vol. 8 (1996), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0856.13020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.