×

zbMATH — the first resource for mathematics

Root system chip-firing. I: interval-firing. (English) Zbl 1440.17006
Summary: Jim Propp recently introduced a variant of chip-firing on a line where the chips are given distinct integer labels. Hopkins, McConville, and Propp showed that this process is confluent from some (but not all) initial configurations of chips. We recast their set-up in terms of root systems: labeled chip-firing can be seen as a root-firing process which allows the moves \(\lambda\rightarrow \lambda+\alpha\) for \(\alpha \in \Phi^{+}\) whenever \(\langle \lambda, \alpha^\vee \rangle = 0\), where \(\Phi^{+}\) is the set of positive roots of a root system of Type A and \(\lambda\) is a weight of this root system. We are thus motivated to study the exact same root-firing process for an arbitrary root system. Actually, this central root-firing process is the subject of a sequel to this paper.
In the present paper, we instead study the interval root-firing processes determined by \(\lambda\rightarrow \lambda+\alpha\) for \(\alpha \in \Phi^{+}\) whenever \(\langle \lambda ,\alpha^\vee \rangle \in [-k-1,k-1]\) or \(\langle \lambda,\alpha^\vee \rangle \in [-k,k-1]\), for any \(k \ge 0\). We prove that these interval-firing processes are always confluent, from any initial weight. We also show that there is a natural way to consistently label the stable points of these interval-firing processes across all values of \(k\) so that the number of weights with given stabilization is a polynomial in \(k\). We conjecture that these Ehrhart-like polynomials have nonnegative integer coefficients.

MSC:
17B22 Root systems
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)
05C57 Games on graphs (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abe, T.; Barakat, M.; Cuntz, M.; Hoge, T.; Terao, H., The freeness of ideal subarrangements of Weyl arrangements, J. Eur. Math. Soc. (JEMS), 18, 1339-1348, (2016) · Zbl 1350.32028
[2] Abe, T.; Terao, H., The freeness of Shi-Catalan arrangements, Eur. J. Combin., 32, 1191-1198, (2011) · Zbl 1235.52035
[3] Abe, T.; Terao, H., Free filtrations of affine Weyl arrangements and the ideal-Shi arrangements, J. Algebraic Combin., 43, 33-44, (2016) · Zbl 1337.32041
[4] Anderson, R.; Lovász, L.; Shor, P.; Spencer, J.; Tardos, É.; Winograd, S., Disks, balls, and walls: analysis of a combinatorial game, Am. Math. Mon., 96, 481-493, (1989) · Zbl 0693.90110
[5] Athanasiadis, C.A.: Deformations of Coxeter hyperplane arrangements and their characteristic polynomials. In: Arrangements—Tokyo 1998, Adv. Stud. Pure Math., vol. 27, pp. 1-26. Kinokuniya, Tokyo (2000) · Zbl 0976.32016
[6] Björner, A., Brenti, F.: Combinatorics of Coxeter groups. In: Graduate Texts in Mathematics, vol. 231. Springer, New York (2005)
[7] Biggs, NL, Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 25-45, (1999) · Zbl 0919.05027
[8] Benkart, G.; Klivans, C.; Reiner, V., Chip firing on Dynkin diagrams and McKay quivers, Math. Z., 290, 615-648, (2018) · Zbl 1448.17015
[9] Björner, A.; Lovász, L., Chip-firing games on directed graphs, J. Algebraic Combin., 1, 305-328, (1992) · Zbl 0805.90142
[10] Björner, A.; Lovász, L.; Shor, PW, Chip-firing games on graphs, Eur. J. Combin., 12, 283-291, (1991) · Zbl 0729.05048
[11] Baker, M.; Norine, S., Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 766-788, (2007) · Zbl 1124.05049
[12] Bourbaki, N.: Lie groups and Lie algebras. Chapters 4-6. In: Elements of Mathematics. Springer, Berlin (2002) (Translated from the 1968 French original by Andrew Pressley)
[13] Beck, M., Robins, S.: Computing the continuous discretely. In: Undergraduate Texts in Mathematics, 2nd edn. Springer, New York. (2015) (Integer-point enumeration in polyhedra, With illustrations by David Austin) · Zbl 1339.52002
[14] Bak, P.; Tang, C.; Wiesenfeld, K., Self-organized criticality: an explanation of the 1/ f noise, Phys. Rev. Lett., 59, 381-384, (1987)
[15] Corry, S., Perkinson, D.: Divisors and Sandpiles: An Introduction to Chip-Firing. American Mathematical Society, Providence (2018) · Zbl 1411.05003
[16] Dhar, D., Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 1613-1616, (1990) · Zbl 0943.82553
[17] Dhar, D., The abelian sandpile and related models, Phys. A Stat. Mech. Appl., 263, 4-25, (1999)
[18] Ehrhart, E..: Polynômes arithmétiques et méthode des polyèdres en combinatoire. Birkhäuser, Basel-Stuttgart (1977) (International Series of Numerical Mathematics, Vol. 35)
[19] Engel, A., The probabilistic abacus, Educ. Stud. Math., 6, 1-22, (1975) · Zbl 0303.60056
[20] Engel, A., Why does the probabilistic abacus work?, Educ. Stud. Math., 7, 59-69, (1976) · Zbl 0338.60041
[21] Edelman, PH; Reiner, V., Free arrangements and rhombic tilings, Discrete Comput. Geom., 15, 307-340, (1996) · Zbl 0853.52013
[22] Etingof, P.; Strickland, E., Lectures on quasi-invariants of Coxeter groups and the Cherednik algebra, Enseign. Math. (2), 49, 35-65, (2003) · Zbl 1051.20018
[23] Farrell, M.; Levine, L., CoEulerian graphs, Proc. Am. Math. Soc., 144, 2847-2860, (2016) · Zbl 1334.05025
[24] Gabrielov, A.: Asymmetric abelian avalanches and sandpile. Preprint, Mathematical Sciences Institute, Cornell University. https://www.math.purdue.edu/ agabriel/asym.pdf (1993)
[25] Galashin, P., Hopkins, S., McConville, T., Postnikov, A.: Root system chip-firing II: central-firing. Eprint published online at arXiv:1708.04849. Forthcoming, International Mathematics Research Notices (2018) · Zbl 1411.05183
[26] Gathmann, A.; Kerber, M., A Riemann-Roch theorem in tropical geometry, Math. Z., 259, 217-230, (2008) · Zbl 1187.14066
[27] Guzmán, J.; Klivans, C., Chip-firing and energy minimization on M-matrices, J. Combin. Theory Ser. A, 132, 14-31, (2015) · Zbl 1307.05032
[28] Hopkins, S.; McConville, T.; Propp, J., Sorting via chip-firing, Electron. J. Comb., 24, p3.13, (2017) · Zbl 1369.05148
[29] Hopkins, S., Postnikov, A.: A positive formula for the Ehrhart-like polynomials from root system chip-firing. Eprint published online at arXiv:1803.08472 (2018)
[30] Huet, G., Confluent reductions: abstract properties and applications to term rewriting systems, J. ACM, 27, 797-821, (1980) · Zbl 0458.68007
[31] Humphreys, J.E.: Introduction to Lie algebras and representation theory. In: Graduate Texts in Mathematics, vol. 9. Springer, New York (1972) · Zbl 0254.17004
[32] Kiss, V.; Tóthmérész, L., Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph, Discrete Appl. Math., 193, 48-56, (2015) · Zbl 1317.05122
[33] Levine, L.; Propp, J., What is \(\dots \) a sandpile?, Not. Am. Math. Soc., 57, 976-979, (2010) · Zbl 1203.82061
[34] Lam, T., Postnikov, A.: Alcoved polytopes II. Eprint published online at arXiv:1202.4015. Forthcoming, Kostant Memorial Volume, Birkhauser (2018)
[35] Levine, L.; Pegden, W.; Smart, CK, Apollonian structure in the Abelian sandpile, Geom. Funct. Anal., 26, 306-336, (2016) · Zbl 1341.60129
[36] Mikhalkin, G., Zharkov, I.: Tropical curves, their Jacobians and theta functions. In: Curves and Abelian Varieties, Contemp. Math., vol. 465, pp. 203-230. American Mathematical Society, Providence (2008) · Zbl 1152.14028
[37] Newman, MHA, On theories with a combinatorial definition of “equivalence”, Ann. Math. (2), 43, 223-243, (1942) · Zbl 0060.12501
[38] Postnikov, A.; Stanley, RP, Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A, 91, 544-597, (2000) · Zbl 0962.05004
[39] Postnikov, A.; Shapiro, B., Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Am. Math. Soc., 356, 3109-3142, (2004) · Zbl 1043.05038
[40] Pegden, W.; Smart, CK, Convergence of the Abelian sandpile, Duke Math. J., 162, 627-642, (2013) · Zbl 1283.60124
[41] Shephard, GC, Combinatorial properties of associated zonotopes, Can. J. Math., 26, 302-321, (1974) · Zbl 0287.52005
[42] Spencer, J., Balancing vectors in the max norm, Combinatorica, 6, 55-65, (1986) · Zbl 0593.90110
[43] Stanley, R.P.: Decompositions of rational convex polytopes. Ann. Discrete Math., 6:333-342, Combinatorial mathematics, optimal designs and their applications. In: Proc, p. 1978. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo, Sympos (1980)
[44] Stembridge, JR, The partial order of dominant weights, Adv. Math., 136, 340-364, (1998) · Zbl 0916.06001
[45] Terao, H., Arrangements of hyperplanes and their freeness. I and II., J. Fac. Sci. Univ. Tokyo Sect. IA Math., 27, 293-312, (1980) · Zbl 0509.14006
[46] Terao, H., Multiderivations of Coxeter arrangements, Invent. Math., 148, 659-674, (2002) · Zbl 1032.52013
[47] Verma, D.N.: The rôle of affine Weyl groups in the representation theory of algebraic Chevalley groups and their Lie algebras. In: Lie groups and their representations (Proc. Summer School, Bolyai János Math. Soc., Budapest, 1971), pp. 653-705. Halsted, New York (1975)
[48] Yoshinaga, M., Characterization of a free arrangement and conjecture of Edelman and Reiner, Invent. Math., 157, 449-454, (2004) · Zbl 1113.52039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.