Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-17T04:19:30.006Z Has data issue: false hasContentIssue false
  • English
  • Français

Flow Polytopes and the Space of Diagonal Harmonics

Part of: Graph theory Algebraic combinatorics Polytopes and polyhedra

Published online by Cambridge University Press:  07 January 2019

Ricky Ini Liu ,
Alejandro H. Morales  and
Karola Mészáros
Ricky Ini Liu
Affiliation:
Department of Mathematics, North Carolina State University, Box 8205, Raleigh, NC 27695, USA Email: [email protected]
Alejandro H. Morales
Affiliation:
Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA 01003, USA Email: [email protected]
Karola Mészáros
Affiliation:
Department of Mathematics, Cornell University, 212 Garden Ave., Ithaca, NY 14853, USA Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A result of Haglund implies that the $(q,t)$-bigraded Hilbert series of the space of diagonal harmonics is a $(q,t)$-Ehrhart function of the flow polytope of a complete graph with netflow vector $(-n,1,\ldots ,1)$. We study the $(q,t)$-Ehrhart functions of flow polytopes of threshold graphs with arbitrary netflow vectors. Our results generalize previously known specializations of the mentioned bigraded Hilbert series at $t=1$, $0$, and $q^{-1}$. As a corollary to our results, we obtain a proof of a conjecture of Armstrong, Garsia, Haglund, Rhoades, and Sagan about the $(q,q^{-1})$-Ehrhart function of the flow polytope of a complete graph with an arbitrary netflow vector.

Keywords

flow polytopethreshold graphdiagonal harmonicTesler matrix

MSC classification

Primary: 05E10: Combinatorial aspects of representation theory
Secondary: 05C21: Flows in graphs 52B20: Lattice polytopes (including relations with commutative algebra and algebraic geometry)
Type
Article
Information
Canadian Journal of Mathematics , Volume 71 , Issue 6 , December 2019 , pp. 1495 - 1521
Copyright
© Canadian Mathematical Society 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Mészáros was partially supported by a National Science Foundation Grant (DMS 1501059). Morales was partially supported by an AMS-Simons travel grant.

References

Armstrong, D., Garsia, A., Haglund, J., Rhoades, B., and Sagan, B., Combinatorics of Tesler matrices in the theory of parking functions and diagonal harmonics . J. Comb. 3(2012), 451–494.Google Scholar
Bergeron, F., Algebraic combinatorics and coinvariant spaces. CMS Treatises in Mathematics, Canadian Mathematical Society, Ottawa, ON; A K Peters Ltd., 2009.Google Scholar
Bollobás, B., Modern graph theory . Graduate Texts in Mathematics, 184, Springer-Verlag, 1998.Google Scholar
Carlsson, E. and Mellit, A., A proof of the shuffle conjecture. J. Amer. Math. Soc., electronically published on November 30, 2017. https://doi.org/10.1090/jams/893.Google Scholar
Chestnut, D. and Fishkind, D. E., Counting spanning trees of threshold graphs. 2012. arxiv:1208.4125.Google Scholar
Garsia, A. M. and Haglund, J., A polynomial expression for the character of diagonal harmonics . Ann. Combin. 19(2015), 693–703. https://doi.org/10.1007/s00026-015-0284-7.Google Scholar
Garsia, A. M., Haglund, J., and Xin, G., Constant term methods in the theory of Tesler matrices and Macdonald polynomial operators . Ann. Comb. 18(2014), 83–109. https://doi.org/10.1007/s00026-013-0213-6.Google Scholar
Garsia, A. M. and Haiman, M., A graded representation model for Macdonald’s polynomials . Proc. Nat. Acad. Sci. U.S.A. 90(1993), 3607–3610. https://doi.org/10.1073/pnas.90.8.3607.Google Scholar
Garsia, A. M. and Haiman, M., A remarkable q, t-Catalan sequence and q-Lagrange inversion . J. Algebraic Combin. 5(1996), 191–244. https://doi.org/10.1023/A:1022476211638.Google Scholar
Gessel, I. M., Enumerative applications of a decomposition for graphs and digraphs . Discrete Math. 139(1995), 1–3, 257–271. https://doi.org/10.1016/0012-365X(94)00135-6.Google Scholar
Gorsky, E. and Negut, A., Refined knot invariants and Hilbert schemes . J. Math. Pures Appl. 104(2015), 403–435. https://doi.org/10.1016/j.matpur.2015.03.003.Google Scholar
Haglund, J., Catalan paths and $q,t$ -enumeration. In: Handbook of enumerative combinatorics, CRC Press, Boca Raton, 2015, pp. 679–751.Google Scholar
Haglund, J., The $q,t$ -Catalan numbers and the space of diagonal harmonics. University Lecture Series, 41, American Mathematical Society, Providence, RI, 2008.Google Scholar
Haglund, J., A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants . Adv. Math. 227(2011), 2092–2106. https://doi.org/10.1016/j.aim.2011.04.013.Google Scholar
Haglund, J., Haiman, M., Loehr, N., Remmel, J. B., and Ulyanov, A., A combinatorial formula for the character of the diagonal coinvariants . Duke Math. J. 126(2005), 195–232. https://doi.org/10.1215/S0012-7094-04-12621-1.Google Scholar
Haglund, J. and Loehr, N., A conjectured combinatorial formula for the Hilbert series for diagonal harmonics . Discrete Math. 298(2005), 189–204. https://doi.org/10.1016/j.disc.2004.01.022.Google Scholar
Haiman, M., Conjectures on the quotient ring by diagonal invariants . J. Algebraic Combin. 3(1994), 17–76. https://doi.org/10.1023/A:1022450120589.Google Scholar
Haiman, M., Vanishing theorems and character formulas for the Hilbert scheme of points in the plane . Invent. Math. 149(2002), 371–407. https://doi.org/10.1007/s002220200219.Google Scholar
Kreweras, G., Une famille de polynômes ayant plusieurs propriétés énumeratives . Period. Math. Hungar. 11(1980), 309–320. https://doi.org/10.1007/BF02107572.Google Scholar
Levande, P., Combinatorial structures and generating functions of Fishburn numbers, parking functions. PhD thesis, Univeristy of Pennsylvania, 2012.Google Scholar
Loehr, N., Combinatorics of q, t-parking functions . Adv. in Appl. Math 34(2005), 408–425. https://doi.org/10.1016/j.aam.2004.08.002.Google Scholar
Loehr, N. A. and Remmel, J. B., Conjectured combinatorial models for the Hilbert series of generalized diagonal harmonics modules . Electron. J. Combin. 11(2004), R68.Google Scholar
Mahadev, N. V. R. and Peled, U. N., Threshold graphs and related topics. Annals of Discrete Mathematics, 56, North-Holland Publishing Co., Amsterdam, 1995.Google Scholar
Merino López, C., Chip firing and the Tutte polynomial . Ann. Comb. 1(1997), 253–259. https://doi.org/10.1007/BF02558479.Google Scholar
Mészáros, K., Morales, A. H., and Rhoades, B., The polytope of Tesler matrices . Selecta Math. (N.S.) 23(2017), 425–454. https://doi.org/10.1007/s00029-016-0241-2.Google Scholar
Perkinson, D., Yang, Q., and Yu, K., G-parking functions and tree inversions . Combinatorica 37(2017), 269–282. https://doi.org/10.1007/s00493-015-3191-y.Google Scholar
Postnikov, A. and Shapiro, B., Trees, parking functions, syzygies, and deformations of monomial ideals . Trans. Amer. Math. Soc. 356(2004), 3109–3142. https://doi.org/10.1090/S0002-9947-04-03547-0.Google Scholar
Sloane, N. J. A., The online encyclopedia of integer sequences. http://www.oeis.org.Google Scholar
Stanley, R. P., Enumerative combinatorics. Vol. 1 (second ed.) and Vol. 2 (first ed.), Cambridge University Press, Cambridge, 2012 and 1999.Google Scholar
Wilson, A. T., A weighted sum over generalized Tesler matrices . J. Algebraic Combin. 45(2017), 825–855. https://doi.org/10.1007/s10801-016-0726-2.Google Scholar