Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Product formulas for volumes of flow polytopes

Author: Karola Mészáros
Journal: Proc. Amer. Math. Soc. 143 (2015), 937-954
MSC (2010): Primary 05E10, 51M25, 52B11
Published electronically: November 6, 2014
MathSciNet review: 3293712
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Intrigued by the product formula $ \prod _{i=1}^{n-2} C_i$ for the volume of the Chan-Robbins-Yuen polytope $ CRY_n$, where $ C_i$ is the $ i^{th}$ Catalan number, we construct a family of polytopes $ \mathcal {P}_{m,n}$, indexed by $ m \in \mathbb{Z}_{\geq 0}$ and $ n \in \mathbb{Z}_{\geq 2}$, whose volumes are given by the product

$\displaystyle \prod _{i=m+1}^{m+n-1}\frac {1}{2i+1}{{m+n+i+1} \choose {2i}}.$

The Chan-Robbins-Yuen polytope $ CRY_n$ coincides with $ \mathcal {P}_{0,n-2}$. Our construction of the polytopes $ \mathcal {P}_{m,n}$ is an application of a systematic method we develop for expressing volumes of a class of flow polytopes as the number of certain triangular arrays. This method can also be used as a heuristic technique for constructing polytopes with combinatorial volumes. As an illustration of this we construct polytopes whose volumes equal the number of $ r$-ary trees on $ n$ internal nodes, $ \frac {1}{(r-1)n+1} {{rn} \choose n}$. Using triangular arrays we also express the volumes of flow polytopes as constant terms of formal Laurent series.

References [Enhancements On Off] (What's this?)

  • [Bal-Ver1] Michèle Vergne, Residue formulae for volumes and Ehrhart polynomials of convex polytopes,
  • [Bal-Ver2] Welleda Baldoni and Michèle Vergne, Kostant partitions functions and flow polytopes, Transform. Groups 13 (2008), no. 3-4, 447-469. MR 2452600 (2009k:52029),
  • [Cha-Rob-Yue] Clara S. Chan, David P. Robbins, and David S. Yuen, On the volume of a certain polytope, Experiment. Math. 9 (2000), no. 1, 91-99. MR 1758803 (2001d:52022)
  • [Kir] Anatol N. Kirillov, Ubiquity of Kostka polynomials, Physics and combinatorics 1999 (Nagoya), World Sci. Publ., River Edge, NJ, 2001, pp. 85-200. MR 1865038 (2003g:05132),
  • [Loe] Nicholas A. Loehr, Bijective combinatorics, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011. MR 2777360 (2012d:05002)
  • [Mész1] Karola Mészáros, Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc. 363 (2011), no. 8, 4359-4382. MR 2792991 (2012g:52022),
  • [Mész2] Karola Mészáros, Root polytopes, triangulations, and the subdivision algebra, II, Trans. Amer. Math. Soc. 363 (2011), no. 11, 6111-6141. MR 2817421 (2012g:52021),
  • [Mész-Mora] Karola Mészáros and Alejandro H. Morales, Flow polytopes and the Kostant partition function,
  • [Morr] W. G. Morris, Constant Term Identities for Finite and Affine Root Systems: Conjectures and Theorems, Ph.D. Thesis, 1982.
  • [Pos] A. Postnikov, personal communication, 2010.
  • [Sta1] Richard P. Stanley, Acyclic flow polytopes and Kostant's partition function, Conference transparencies, 2000,$ \sim $rstan/trans.html.
  • [Sta-Pit] Richard P. Stanley and Jim Pitman, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27 (2002), no. 4, 603-634. MR 1902680 (2003e:52017),
  • [Sta2] Richard P. Stanley, personal communication, 2008.
  • [Zei] Doron Zeilberger, Proof of a conjecture of Chan, Robbins, and Yuen, Orthogonal polynomials: numerical and symbolic algorithms (Leganés, 1998). Electron. Trans. Numer. Anal. 9 (1999), 147-148 (electronic). MR 1749805 (2001b:05015)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05E10, 51M25, 52B11

Retrieve articles in all journals with MSC (2010): 05E10, 51M25, 52B11

Additional Information

Karola Mészáros
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853

Keywords: Flow polytope, Chan-Robbins-Yuen polytope, triangular arrays, triangulation, volume, Kostant partition function
Received by editor(s): December 1, 2011
Received by editor(s) in revised form: November 30, 2012, and February 23, 2013
Published electronically: November 6, 2014
Additional Notes: The author was supported by a National Science Foundation Postdoctoral Research Fellowship (DMS 1103933)
Communicated by: Jim Haglund
Article copyright: © Copyright 2014 Karola Mészáros

American Mathematical Society