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.
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.79
Keywords: root system, chip-firing, Ehrhart polynomial, permutohedron, zonotope, root polytope
Hopkins, Sam 1; Postnikov, Alexander 1
CC-BY 4.0
@article{ALCO_2019__2_6_1159_0,
author = {Hopkins, Sam and Postnikov, Alexander},
title = {A positive formula for the {Ehrhart-like} polynomials from root system chip-firing},
journal = {Algebraic Combinatorics},
pages = {1159--1196},
publisher = {MathOA foundation},
volume = {2},
number = {6},
year = {2019},
doi = {10.5802/alco.79},
zbl = {07140429},
mrnumber = {4049842},
language = {en},
url = {https://alco.centre-mersenne.org/articles/10.5802/alco.79/}
}
TY - JOUR AU - Hopkins, Sam AU - Postnikov, Alexander TI - A positive formula for the Ehrhart-like polynomials from root system chip-firing JO - Algebraic Combinatorics PY - 2019 SP - 1159 EP - 1196 VL - 2 IS - 6 PB - MathOA foundation UR - https://alco.centre-mersenne.org/articles/10.5802/alco.79/ DO - 10.5802/alco.79 LA - en ID - ALCO_2019__2_6_1159_0 ER -
%0 Journal Article %A Hopkins, Sam %A Postnikov, Alexander %T A positive formula for the Ehrhart-like polynomials from root system chip-firing %J Algebraic Combinatorics %D 2019 %P 1159-1196 %V 2 %N 6 %I MathOA foundation %U https://alco.centre-mersenne.org/articles/10.5802/alco.79/ %R 10.5802/alco.79 %G en %F ALCO_2019__2_6_1159_0
Hopkins, Sam; Postnikov, Alexander. A positive formula for the Ehrhart-like polynomials from root system chip-firing. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1159-1196. doi : 10.5802/alco.79. https://alco.centre-mersenne.org/articles/10.5802/alco.79/
[1] The freeness of Shi–Catalan arrangements, European J. Combin., Volume 32 (2011) no. 8, pp. 1191-1198 | DOI | MR | Zbl
[2] 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] Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2015, xx+285 pages | DOI | MR | Zbl
[4] Combinatorics of Coxeter groups, Graduate Texts in Mathematics, 231, Springer, New York, 2005, xiv+363 pages | MR | Zbl
[5] 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] Root polytopes and Borel subalgebras, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 4392-4420 | DOI | MR | Zbl
[7] Parabolic subgroup orbits on finite root systems, J. Pure Appl. Algebra, Volume 222 (2018) no. 12, pp. 3849-3857 | DOI | MR | Zbl
[8] Free arrangements and rhombic tilings, Discrete Comput. Geom., Volume 15 (1996) no. 3, pp. 307-340 | DOI | MR | Zbl
[9] 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] Root system chip-firing I: Interval-firing (Forthcoming, Mathematische Zeitschrift) | DOI | Zbl
[11] Root system chip-firing II: Central-firing (2017) (Forthcoming, International Mathematics Research Notices, https://arxiv.org/abs/1708.04849)
[12] , the most exceptional group, Bull. Amer. Math. Soc. (N.S.), Volume 53 (2016) no. 4, pp. 643-671 | DOI | MR | Zbl
[13] Sorting via chip-firing, Electron. J. Combin., Volume 24 (2017) no. 3, Paper no. P3.13, 20 pages | MR | Zbl
[14] Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, 9, Springer-Verlag, New York-Berlin, 1972, xii+169 pages | MR | Zbl
[15] 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] On Positivity of Ehrhart Polynomials, Recent Trends in Algebraic Combinatorics, Springer International Publishing, Cham, 2019, pp. 189-237 | DOI | MR | Zbl
[17] Polynomials associated with finite cell-complexes, J. London Math. Soc. (2), Volume 4 (1971), pp. 181-192 | DOI | MR | Zbl
[18] 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] Lattice invariant valuations on rational polytopes, Arch. Math., Volume 31 (1978/79) no. 1, pp. 509-516 | DOI | MR | Zbl
[20] Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc., Volume 363 (2011) no. 8, pp. 4359-4382 | DOI | MR | Zbl
[21] Root polytopes, triangulations, and the subdivision algebra, II, Trans. Amer. Math. Soc., Volume 363 (2011) no. 11, pp. 6111-6141 | DOI | MR | Zbl
[22] A classification of subsystems of a root system (2006) (https://arxiv.org/abs/math/0611904)
[23] Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | DOI | MR | Zbl
[24] 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: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2018 (http://combinat.sagemath.org)
[26] SageMath, the Sage Mathematics Software System (Version 8.2) (2018) (http://www.sagemath.org)
[27] Combinatorial properties of associated zonotopes, Canad. J. Math., Volume 26 (1974) no. 2, pp. 302-321 | DOI | MR | Zbl
[28] 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] 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] Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR | Zbl
[31] The partial order of dominant weights, Adv. Math., Volume 136 (1998) no. 2, pp. 340-364 | DOI | MR | Zbl
[32] Multiderivations of Coxeter arrangements, Invent. Math., Volume 148 (2002) no. 3, pp. 659-674 | DOI | MR | Zbl
[33] 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] Worpitzky partitions for root systems and characteristic quasi-polynomials, Tohoku Math. J. (2), Volume 70 (2018) no. 1, pp. 39-63 | DOI | MR | Zbl
Cited by Sources: