Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

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 tableaus 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

Notes

  1. See Definition 3.1 and the discussion in Sect. 3.1 for the relation of nonnegative integer flows with a given netflow vector to Kostant partition functions as well as Theorem 3.4.

References

  1. Baldoni, W., Vergne, M.: Kostant partition functions and flow polytopes. Transform. Groups 13(3–4), 447–469 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Baryshnikov, Yu., Romik, D.: Enumeration formulas for Young tableaux in a diagonal strip. Isr. J. Math. 178(1), 157–186 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Beck, M., Pixton, D.: The Ehrhart polynomial of the Birkhoff polytope. Discrete Comput. Geom. 30(4), 623–637 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  4. Beck, M., Robins, S.: Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer, New York (2007)

    MATH  Google Scholar 

  5. Behrend, R.E., Knight, V.A.: Higher spin alternating sign matrices. Electron. J. Comb. 14(1), Art. No. 83 (2007)

  6. Birkhoff, G.: Three observations on linear algebra. Univ. Nac. Tucumán. Rev. A 5, 147–151 (1946)

    MathSciNet  MATH  Google Scholar 

  7. Canfield, E.R., McKay, B.D.: The asymptotic volume of the Birkhoff polytope. Online J. Anal. Comb. 2009(4), Art. No. 2 (2009)

  8. Chan, C.S., Robbins, D.P., Yuen, D.S.: On the volume of a certain polytope. Exp. Math. 9(1), 91–99 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  10. De Loera, J.A., Liu, F., Yoshida, R.: A generating function for all semi-magic squares and the volume of the Birkhoff polytope. J. Algebr. Comb. 30(1), 113–139 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ehrhart, E.: Sur les polyèdres rationnels homothétiques à \(n\) dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)

    MathSciNet  MATH  Google Scholar 

  12. Fomin, S., Kirillov, A.N.: Reduced words and plane partitions. J. Algebr. Combin. 6(4), 311–319 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gallo, G., Sodini, C.: Extreme points and adjacency relationship in the flow polytope. Calcolo 15, 277–288 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  14. Kitaev, S., Remmel, J., Tiefenbruck, M.: Quadrant marked mesh patterns in 132-avoiding permutations. Pure Math. Appl. (PU.M.A.) 23(3), 219–256 (2012)

    MathSciNet  MATH  Google Scholar 

  15. Mészáros, K., Morales, A.H.: Flow polytopes of signed graphs and the Kostant partition function. Int. Math. Res. Not. (IMNR) 2015(3), 830–871 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  16. Mészáros, K., St. Dizier, A.: From generalized permutahedra to Grothendieck polynomials via flow polytopes (2017). arXiv:1705.02418

  17. Mills, W.H., Robbins, D.P., Rumsey Jr., H.: Alternating sign matrices and descending plane partitions. J. Comb. Theory Ser. A 34(3), 340–359 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  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, R.A.: New symmetric plane partition identities from invariant theory work of De Concini and Procesi. Eur. J. Comb. 11(3), 289–300 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  22. Sloane, N.J.A.: The Online Encyclopedia of Integer Sequences. http://oeis.org

  23. Stanley, R.P.: Two poset polytopes. Discrete Comput. Geom. 1(1), 9–23 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  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)

  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)

  29. Zeilberger, D.: Proof of a conjecture of Chan, Robbins, and Yuen. Electron. Trans. Numer. Anal. 9, 147–148 (1999)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to Alexander Postnikov for generously sharing his insights and questions. The authors are also grateful to the anonymus referee for numerous helpful comments and suggestions. AHM and JS would like to thank ICERM and the organizers of its Spring 2013 program in Automorphic Forms during which part of this work was done. The authors also thank the SageMath community [26] for developing and sharing their code by which some of this research was conducted.

Author information

Authors and Affiliations

  1. Department of Mathematics, Cornell University, Ithaca, NY, 14853, USA

    Karola Mészáros

  2. School of Mathematics, Institute for Advanced Study, Princeton, NJ, 08540, USA

    Karola Mészáros

  3. Department of Mathematics and Statistics, UMass, Amherst, MA, 01003, USA

    Alejandro H. Morales

  4. Department of Mathematics, North Dakota State University, Fargo, ND, 58102, USA

    Jessica Striker

Authors
  1. Karola Mészáros
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alejandro H. Morales
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jessica Striker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alejandro H. Morales.

Additional information

Editor in Charge: János Pach

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

KM was partially supported by a National Science Foundation Grant (DMS 1501059) as well as by a von Neumann Fellowship at the IAS funded by the Fund for Mathematics and the Friends of the Institute for Advanced Study.

AHM was partially supported by a CRM-ISM Postdoctoral Fellowship and an AMS-Simons travel grant.

JS was partially supported by a National Security Agency Grant (H98230-15-1-0041), the North Dakota EPSCoR National Science Foundation Grant (IIA-1355466), the NDSU Advance FORWARD program sponsored by National Science Foundation grant (HRD-0811239), and a grant from the Simons Foundation/SFARI (527204, JS).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mészáros, K., Morales, A.H. & Striker, J. On Flow Polytopes, Order Polytopes, and Certain Faces of the Alternating Sign Matrix Polytope. Discrete Comput Geom 62, 128–163 (2019). https://doi.org/10.1007/s00454-019-00073-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-019-00073-2

Keywords

Mathematics Subject Classification

Search

Navigation