2015/10/12 by Karola Mészáros, Alejandro H. Morales, Mészáros, Karola +3 · 3 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Graph theory and applications #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1510.03357
In this paper we study an alternating sign matrix analogue of the\nChan-Robbins-Yuen polytope, which we call the ASM-CRY polytope. We show that\nthis polytope has Catalan many vertices and its volume is equal to the number\nof standard Young tableaux of staircase shape; we also determine its Ehrhart\npolynomial. We achieve the previous by proving that the members of a family of\nfaces of the alternating sign matrix polytope which includes ASM-CRY are both\norder and flow polytopes. Inspired by the above results, we relate three\nestablished triangulations of order and flow polytopes, namely Stanley's\ntriangulation of order polytopes, the Postnikov-Stanley triangulation of flow\npolytopes and the Danilov-Karzanov-Koshevoy triangulation of flow polytopes. We\nshow that when a graph G is a planar graph, in which case the flow polytope\nFG is also an order polytope, Stanley's triangulation of this order polytope\nis one of the Danilov-Karzanov-Koshevoy triangulations of FG. Moreover, for\na general graph G we show that the set of Danilov-Karzanov-Koshevoy\ntriangulations of FG is a subset of the set of Postnikov-Stanley\ntriangulations of FG. We also describe explicit bijections between the\ncombinatorial objects labeling the simplices in the above triangulations.\n