×

zbMATH — the first resource for mathematics

On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope. (English) Zbl 1414.05029
Summary: We study an alternating sign matrix analogue of the Chan-Robbins-Yuen polytope, which we call the ASM-CRY polytope. We show that this polytope has Catalan many vertices and its volume is equal to the number of standard Young tableaux of staircase shape; we also determine its Ehrhart polynomial. We achieve the previous by proving that the members of a family of faces of the alternating sign matrix polytope which includes ASM-CRY are both order and flow polytopes. Inspired by the above results, we relate three established triangulations of order and flow polytopes, namely Stanley’s triangulation of order polytopes, the Postnikov-Stanley triangulation of flow polytopes and the Danilov-Karzanov-Koshevoy triangulation of flow polytopes. We show that when a graph \(G\) is a planar graph, in which case the flow polytope \({{\mathcal {F}}}_G\) is also an order polytope, Stanley’s triangulation of this order polytope is one of the Danilov-Karzanov-Koshevoy triangulations of \({{\mathcal {F}}}_G\). Moreover, for a general graph \(G\) we show that the set of Danilov-Karzanov-Koshevoy triangulations of \({{\mathcal {F}}}_G\) equals the set of framed Postnikov-Stanley triangulations of \({{\mathcal {F}}}_G\). We also describe explicit bijections between the combinatorial objects labeling the simplices in the above triangulations.

MSC:
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
05A20 Combinatorial inequalities
05E10 Combinatorial aspects of representation theory
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52A38 Length, area, volume and convex sets (aspects of convex geometry)
05C20 Directed graphs (digraphs), tournaments
05C21 Flows in graphs
52B11 \(n\)-dimensional polytopes
52B22 Shellability for polytopes and polyhedra
Software:
SageMath; OEIS
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Baldoni, W.; Vergne, M., Kostant partition functions and flow polytopes, Transform. Groups, 13, 447-469, (2008) · Zbl 1200.52008
[2] Baryshnikov, Yu; Romik, D., Enumeration formulas for Young tableaux in a diagonal strip, Isr. J. Math., 178, 157-186, (2010) · Zbl 1206.05011
[3] Beck, M.; Pixton, D., The Ehrhart polynomial of the Birkhoff polytope, Discrete Comput. Geom., 30, 623-637, (2003) · Zbl 1065.52007
[4] Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer, New York (2007) · Zbl 1114.52013
[5] Behrend, R.E., Knight, V.A.: Higher spin alternating sign matrices. Electron. J. Comb. 14(1), Art. No. 83 (2007) · Zbl 1183.05003
[6] Birkhoff, G., Three observations on linear algebra, Univ. Nac. Tucumán. Rev. A, 5, 147-151, (1946) · Zbl 0060.07906
[7] Canfield, E.R., McKay, B.D.: The asymptotic volume of the Birkhoff polytope. Online J. Anal. Comb. 2009(4), Art. No. 2 (2009) · Zbl 1193.15034
[8] Chan, CS; Robbins, DP; Yuen, DS, On the volume of a certain polytope, Exp. Math., 9, 91-99, (2000) · Zbl 0960.05004
[9] Danilov, V.I., Karzanov, A.V., Koshevoy, G.A.: Coherent fans in the space of flows in framed graphs. In: Proceedings of the 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012). Discrete Mathematics & Theoretical Computer Science Proceedings, pp. 481-490. DMTCS, Nancy (2012) · Zbl 1412.05082
[10] Loera, JA; Liu, F.; Yoshida, R., A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebr. Comb., 30, 113-139, (2009) · Zbl 1187.05009
[11] Ehrhart, E., Sur les polyèdres rationnels homothétiques à \(n\) dimensions, C. R. Acad. Sci. Paris, 254, 616-618, (1962) · Zbl 0100.27601
[12] Fomin, S.; Kirillov, AN, Reduced words and plane partitions, J. Algebr. Combin., 6, 311-319, (1997) · Zbl 0882.05010
[13] Gallo, G.; Sodini, C., Extreme points and adjacency relationship in the flow polytope, Calcolo, 15, 277-288, (1978) · Zbl 0406.90022
[14] Kitaev, S.; Remmel, J.; Tiefenbruck, M., Quadrant marked mesh patterns in 132-avoiding permutations, Pure Math. Appl. (PU.M.A.), 23, 219-256, (2012) · Zbl 1299.05013
[15] Mészáros, K.; Morales, AH, Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not. (IMNR), 2015, 830-871, (2015) · Zbl 1307.05097
[16] Mészáros, K., St. Dizier, A.: From generalized permutahedra to Grothendieck polynomials via flow polytopes (2017). arXiv:1705.02418
[17] Mills, WH; Robbins, DP; Rumsey, H., Alternating sign matrices and descending plane partitions, J. Comb. Theory Ser. A, 34, 340-359, (1983) · Zbl 0516.05016
[18] Moorefield, D.L.: Partition Analysis in Ehrhart Theory. Master Thesis, San Francisco State University (2007)
[19] Morales, A.H.: Data of Ehrhart polynomials of the CRY polytope (2017). https://sites.google.com/site/flowpolytopes/ehrhart
[20] Morris, W.G.: Constant Term Identities for Finite and Affine Root Systems: Conjectures and Theorems. PhD Thesis, University of Wisconsin-Madison (1982)
[21] Proctor, RA, New symmetric plane partition identities from invariant theory work of De Concini and Procesi, Eur. J. Comb., 11, 289-300, (1990) · Zbl 0726.05008
[22] Sloane, N.J.A.: The Online Encyclopedia of Integer Sequences. http://oeis.org · Zbl 1044.11108
[23] Stanley, RP, Two poset polytopes, Discrete Comput. Geom., 1, 9-23, (1986) · Zbl 0595.52008
[24] Stanley, R.P.: Acyclic flow polytopes and Kostant’s partition function. In: Conference Transparencies (2000). http://math.mit.edu/ rstan/trans.html
[25] Stanley, R.P.: Enumerative Combinatorics, vol. 1 (2nd edn.) and vol. 2 (1st edn.). Cambridge University Press, Cambridge (2012 and 1999) · Zbl 0928.05001
[26] Stein, W.A., et al.: Sage Mathematics Software, Version 6.6. The Sage Developers (2015). http://www.sagemath.org
[27] Striker, J.: The alternating sign matrix polytope. Electron. J. Comb. 16(1), Art. No. 41 (2009) · Zbl 1226.05168
[28] von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. In: Contributions to the Theory of Games, vol. 2. Annals of Mathematics Studies, vol. 28, pp. 5-12. Princeton University Press, Princeton (1953) · Zbl 0050.14105
[29] Zeilberger, D., Proof of a conjecture of Chan, Robbins, and Yuen, Electron. Trans. Numer. Anal., 9, 147-148, (1999) · Zbl 0941.05006
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.