A positive formula for the Ehrhart-like polynomials from root system chip-firing

Hopkins, Sam; Postnikov, Alexander

Algebraic Combinatorics, Tome 2 (2019) no. 6, pp. 1159-1196.

In earlier work in collaboration with Pavel Galashin and Thomas McConville we introduced a version of chip-firing for root systems. Our investigation of root system chip-firing led us to define certain polynomials analogous to Ehrhart polynomials of lattice polytopes, which we termed the symmetric and truncated Ehrhart-like polynomials. We conjectured that these polynomials have nonnegative integer coefficients. Here we affirm “half” of this positivity conjecture by providing a positive, combinatorial formula for the coefficients of the symmetric Ehrhart-like polynomials. This formula depends on a subtle integrality property of slices of permutohedra, and in turn a lemma concerning dilations of projections of root polytopes, which both may be of independent interest. We also discuss how our formula very naturally suggests a conjecture for the coefficients of the truncated Ehrhart-like polynomials that turns out to be false in general, but which may hold in some cases.

Classification : 17B22, 52B20
Mots clés : root system, chip-firing, Ehrhart polynomial, permutohedron, zonotope, root polytope

[1] Abe, Takuro; Terao, Hiroaki The freeness of Shi–Catalan arrangements, European J. Combin., Volume 32 (2011) no. 8, pp. 1191-1198 | DOI | MR | Zbl

[2] Athanasiadis, Christos A. Deformations of Coxeter hyperplane arrangements and their characteristic polynomials, Arrangements – Tokyo 1998 (Adv. Stud. Pure Math.), Volume 27, Kinokuniya, Tokyo, 2000, pp. 1-26 | MR | Zbl

[3] Beck, Matthias; Robins, Sinai Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2015, xx+285 pages | DOI | MR | Zbl

[4] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | MR | Zbl

[5] Bourbaki, Nicolas Lie groups and Lie algebras. Chapters 4–6, Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 2002, xii+300 pages (Translated from the 1968 French original by Andrew Pressley) | DOI | MR | Zbl

[6] Cellini, Paola; Marietti, Mario Root polytopes and Borel subalgebras, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 4392-4420 | DOI | MR | Zbl

[7] Dyer, M. J.; Lehrer, G. I. Parabolic subgroup orbits on finite root systems, J. Pure Appl. Algebra, Volume 222 (2018) no. 12, pp. 3849-3857 | DOI | MR | Zbl

[8] Edelman, Paul H.; Reiner, Victor Free arrangements and rhombic tilings, Discrete Comput. Geom., Volume 15 (1996) no. 3, pp. 307-340 | DOI | MR | Zbl

[9] Ehrhart, E. Polynômes arithmétiques et méthode des polyèdres en combinatoire, International Series of Numerical Mathematics, 35, Birkhäuser Verlag, Basel-Stuttgart, 1977, 165 pages | MR | Zbl

[10] Galashin, Pavel; Hopkins, Sam; McConville, Thomas; Postnikov, Alexander Root system chip-firing I: Interval-firing (Forthcoming, Mathematische Zeitschrift) | DOI | Zbl

[11] Galashin, Pavel; Hopkins, Sam; McConville, Thomas; Postnikov, Alexander Root system chip-firing II: Central-firing (2017) (Forthcoming, International Mathematics Research Notices, https://arxiv.org/abs/1708.04849)

[12] Garibaldi, Skip $E_8$, the most exceptional group, Bull. Amer. Math. Soc. (N.S.), Volume 53 (2016) no. 4, pp. 643-671 | DOI | MR | Zbl

[13] Hopkins, Sam; McConville, Thomas; Propp, James Sorting via chip-firing, Electron. J. Combin., Volume 24 (2017) no. 3, P3.13, 20 pages | MR | Zbl

[14] Humphreys, James E. Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, 9, Springer-Verlag, New York-Berlin, 1972, xii+169 pages | MR | Zbl

[15] Lam, Thomas; Postnikov, Alexander Alcoved Polytopes II, Lie Groups, Geometry, and Representation Theory: A Tribute to the Life and Work of Bertram Kostant, Springer International Publishing, Cham, 2018, pp. 253-272 | DOI | Zbl

[16] Liu, Fu On Positivity of Ehrhart Polynomials, Recent Trends in Algebraic Combinatorics, Springer International Publishing, Cham, 2019, pp. 189-237 | DOI | MR | Zbl

[17] Macdonald, I. G. Polynomials associated with finite cell-complexes, J. London Math. Soc. (2), Volume 4 (1971), pp. 181-192 | DOI | MR | Zbl

[18] McMullen, Peter Valuations and Euler-type relations on certain classes of convex polytopes, Proc. London Math. Soc. (3), Volume 35 (1977) no. 1, pp. 113-135 | DOI | MR | Zbl

[19] McMullen, Peter Lattice invariant valuations on rational polytopes, Arch. Math., Volume 31 (1978/79) no. 1, pp. 509-516 | DOI | MR | Zbl

[20] Mészáros, Karola Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc., Volume 363 (2011) no. 8, pp. 4359-4382 | DOI | MR | Zbl

[21] Mészáros, Karola Root polytopes, triangulations, and the subdivision algebra, II, Trans. Amer. Math. Soc., Volume 363 (2011) no. 11, pp. 6111-6141 | DOI | MR | Zbl

[22] Oshima, Toshio A classification of subsystems of a root system (2006) (https://arxiv.org/abs/math/0611904)

[23] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | DOI | MR | Zbl

[24] Postnikov, Alexander; Stanley, Richard P. Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A, Volume 91 (2000) no. 1-2, pp. 544-597 (In memory of Gian-Carlo Rota) | DOI | MR | Zbl

[25] Sage-Combinat community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2018 (http://combinat.sagemath.org)

[26] Sage Developers SageMath, the Sage Mathematics Software System (Version 8.2) (2018) (http://www.sagemath.org)

[27] Shephard, Geoffrey C. Combinatorial properties of associated zonotopes, Canad. J. Math., Volume 26 (1974) no. 2, pp. 302-321 | DOI | MR | Zbl

[28] Stanley, Richard P. Decompositions of rational convex polytopes, Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978) (Ann. Discrete Math.), Volume 6, North Holland, 1980, pp. 333-342 | MR | Zbl

[29] Stanley, Richard P. A zonotope associated with graphical degree sequences, Applied geometry and discrete mathematics (DIMACS Ser. Discrete Math. Theoret. Comput. Sci.), Volume 4, Amer. Math. Soc., Providence, RI, 1991, pp. 555-570 | MR | Zbl

[30] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR | Zbl

[31] Stembridge, John R. The partial order of dominant weights, Adv. Math., Volume 136 (1998) no. 2, pp. 340-364 | DOI | MR | Zbl

[32] Terao, Hiroaki Multiderivations of Coxeter arrangements, Invent. Math., Volume 148 (2002) no. 3, pp. 659-674 | DOI | MR | Zbl

[33] Yoshinaga, Masahiko Characterization of a free arrangement and conjecture of Edelman and Reiner, Invent. Math., Volume 157 (2004) no. 2, pp. 449-454 | DOI | MR | Zbl

[34] Yoshinaga, Masahiko Worpitzky partitions for root systems and characteristic quasi-polynomials, Tohoku Math. J. (2), Volume 70 (2018) no. 1, pp. 39-63 | DOI | MR | Zbl