Abstract
We introduce the Tesler polytope \(\mathsf {Tes}_n(\mathbf{a})\), whose integer points are the Tesler matrices of size n with hook sums \(a_1,a_2,\ldots ,a_n \in \mathbb {Z}_{\ge 0}\). We show that \(\mathsf {Tes}_n(\mathbf{a})\) is a flow polytope and therefore the number of Tesler matrices is counted by the type \(A_n\) Kostant partition function evaluated at \((a_1,a_2,\ldots ,a_n,-\sum _{i=1}^n a_i)\). We describe the faces of this polytope in terms of “Tesler tableaux” and characterize when the polytope is simple. We prove that the h-vector of \(\mathsf {Tes}_n(\mathbf{a})\) when all \(a_i>0\) is given by the Mahonian numbers and calculate the volume of \(\mathsf {Tes}_n(1,1,\ldots ,1)\) to be a product of consecutive Catalan numbers multiplied by the number of standard Young tableaux of staircase shape.
Similar content being viewed by others
Notes
In the literature, transportation polytopes are more general [21]. The matrices can be rectangular and the \(i{\mathrm{th}}\) row sum and the \(i{\mathrm{th}}\) column sum can differ.
References
Armstrong, D.: Tesler matrices. Talk slides Bruce Saganfest. http://www.math.miami.edu/~armstrong/Talks/Tesler_Saganfest.pdf (2014)
Armstrong, D., Garsia, A., Haglund, J., Rhoades, B., Sagan, B.: Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics. J. Comb. 3, 451–494 (2012)
Baldoni-Silva, W., Beck, M., Cochet, C., Vergne, M.: Volume computation for polytopes and partition functions for classical root systems. Discrete Comput. Geom. 35, 551–595 (2006). Maple worksheets: http://www.math.jussieu.fr/~vergne/work/IntegralPoints.html
Baldoni, W., Vergne, M.: Kostant partitions functions and flow polytopes. Transform. Groups 13, 447–469 (2008)
Baldoni, W., Vergne, M.: Morris identities and the total residue for a system of type \(A_r\). Prog. Math. 220, 1–19 (2004)
Brion, M., Vergne, M.: Residue formulae, vector partition functions and lattice points in rational polytopes. J. Am. Math. Soc. 10, 797–833 (1997)
Butler, F., Can, M., Haglund, J., Remmel, J.: Rook Theory Notes. http://www.math.ucsd.edu/~remmel/files/Book.pdf
Carlsson, E., Mellit, A.: A proof the shuffle conjecture. arXiv:1508.06239
Chan, C.S., Robbins, D.P.: On the volume of the polytope of doubly stochastic matrices. Exp. Math. 8, 291–300 (1999)
Chan, C.S., Robbins, D.P., Yuen, D.S.: On the volume of a certain polytope. Exp. Math. 9, 91–99 (2000)
Garsia, A.M., Haglund, J.: A positivity result in the theory of Macdonald polynomials. Proc. Natl. Acad. Sci. USA 98, 4313–4316 (2001)
Garsia, A.M., Haglund, J.: A proof of the \(q, t\)-Catalan positivity conjecture. Discrete Math. 256, 677–717 (2002)
Garsia, A.M., Haglund, J., Xin, G.: Constant term methods in the theory of Tesler matrices and Macdonald polynomial operators. Ann. Comb. 18, 83–109 (2014)
Gorsky, E., Negut, A.: Refined knot invariants and Hilbert schemes. J. Math. Pures Appl. 104, 403–435 (2015)
Haglund, J.: A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants. Adv. Math. 227, 2092–2106 (2011)
Haglund, J.: The \(q,t\)-Catalan Numbers and the Space of Diagonal Harmonics. University Lecture Series, vol. 41. American Mathematical Society (2008)
Haglund, J., Haiman, M., Loehr, N., Remmel, J., Ulyanov, A.: A combinatorial formula for the character of the diagonal coinvariants. Duke Math. J. 126, 195–232 (2005)
Haglund, J., Loehr, N.: A conjectured combinatorial formula for the Hilbert series for diagonal harmonics. Discrete Math. 298(1), 189–204 (2005)
Haglund J., Remmel J., Wilson A.T.: The delta conjecture. arXiv:1509.07058
Hille, L.: Quivers, cones and polytopes. Linear Algebra Appl. 365, 215–237 (2003)
Klee, V., Witzgall, C.: Facets and Vertices of Transportation Polytopes, Mathematics of the Decision Sciences Part 1. Lectures in Applied Mathematics, vol. 11, pp. 257–282. AMS, Providence, RI (1968)
Levande, P.: Special cases of the parking functions conjecture and upper-triangular matrices. In: DMTCS proceedings, 23rd international conference on formal power series and algebraic combinatorics (FPSAC 2011), pp.635–644 (2011)
Morris, W.G.: Constant term identities for finite and affine root systems: conjectures and theorems. Ph.D. thesis, University of Wisconsin-Madison (1982)
Pitman, J., Stanley, R.P.: A polytope related to empirical distributions, plane trees, parking functions, and the associahedron. Discrete Comput. Geom. 27, 603–634 (2002)
Sloane, Neil J.A.: The on-line encyclopedia of integer sequences. http://oeis.org/
Wilson, A.T.: A weighted sum over generalized Tesler matrices. arXiv:1510.02684
Xin, G.: The ring of Malcev–Neumann series and the residue theorem. Ph.D. thesis, Brandeis University (2004)
Zeilberger, D.: Proof of conjecture of Chan, Robbins, and Yuen. Electron. Trans. Numer. Anal. 9, 147–148 (1999)
Ziegler, G.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Acknowledgments
We thank Drew Armstrong for many inspiring conversations throughout this project. We thank François Bergeron for suggesting that flow polytopes were related to Tesler matrices and Ole Warnaar for showing us simplifications of Gamma functions that led to the compact expression on the right-hand-side of (3.7) from a more complicated precursor.
Author information
Authors and Affiliations
Corresponding author
Additional information
Mészáros was partially supported by NSF Postdoctoral Research Fellowship DMS-1103933 and NSF Grant DMS-1501059. Morales was supported by a postdoctoral fellowship from CRM-ISM and LaCIM. Rhoades was partially supported by NSF Grant DMS-1068861.
Rights and permissions
About this article
Cite this article
Mészáros, K., Morales, A.H. & Rhoades, B. The polytope of Tesler matrices. Sel. Math. New Ser. 23, 425–454 (2017). https://doi.org/10.1007/s00029-016-0241-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00029-016-0241-2