×

Directed nonabelian sandpile models on trees. (English) Zbl 1456.82607

Summary: We define two general classes of nonabelian sandpile models on directed trees (or arborescences), as models of nonequilibrium statistical physics. Unlike usual applications of the well-known abelian sandpile model, these models have the property that sand grains can enter only through specified reservoirs.
In the Trickle-down sandpile model, sand grains are allowed to move one at a time. For this model, we show that the stationary distribution is of product form. In the Landslide sandpile model, all the grains at a vertex topple at once, and here we prove formulas for all eigenvalues, their multiplicities, and the rate of convergence to stationarity. The proofs use wreath products and the representation theory of monoids.

MSC:

82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
05C05 Trees
82C22 Interacting particle systems in time-dependent statistical mechanics
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ayyer A., Klee S., Schilling A.: Combinatorial Markov chains on linear extensions. J. Algebr. Combin. 39(4), 853-881 (2014) · Zbl 1292.05156 · doi:10.1007/s10801-013-0470-9
[2] Almeida, J.: Finite semigroups and universal algebra, Series in Algebra, vol. 3. World Scientific Publishing Co. Inc., River Edge (1994) (Translated from the 1992 Portuguese original and revised by the author) · Zbl 0844.20039
[3] Ayyer, A., Strehl, V.: The spectrum of an asymmetric annihilation process. In: 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), Discrete Math. Theor. Comput. Sci. Proc., AN, pp. 461-472. Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2010) · Zbl 1374.05013
[4] Ayyer, A., Strehl, V.: Stationary distribution and eigenvalues for a de Bruijn process. In: Kotsireas, I.S., Zima, E.V. (eds.) Advances in Combinatorics, pp. 101-120. Springer, Berlin (2013) · Zbl 1271.05038
[5] Ayyer, A., Schilling, A., Steinberg, B., Thiéry, N.M.: \[{{\fancyscript{R}}}\] R-trivial monoids and Markov chains. Int. J. Algebra Comput. (2014, to appear). arXiv:1401.4250 · Zbl 1310.60105
[6] Ayyer A.: Algebraic properties of a disordered asymmetric Glauber model. J. Stat. Mech. Theory Exp. 2011(02), P02034 (2011) · Zbl 1456.82840 · doi:10.1088/1742-5468/2011/02/P02034
[7] Brown K.S., Diaconis P.: Random walks and hyperplane arrangements. Ann. Probab. 26(4), 1813-1854 (1998) · Zbl 0938.60064 · doi:10.1214/aop/1022855884
[8] Brzozowski J.A., Fich F.E.: Languages of \[{{\mathcal{R}}}\] R -trivial monoids. J. Comput. Syst. Sci. 20(1), 32-49 (1980) · Zbl 0446.68066 · doi:10.1016/0022-0000(80)90003-3
[9] Bidigare P., Hanlon P., Rockmore D.: A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99(1), 135-174 (1999) · Zbl 0955.60043 · doi:10.1215/S0012-7094-99-09906-4
[10] Biggs N.L.: Chip-firing and the critical group of a graph. J. Algebr. Combin. 9(1), 25-45 (1999) · Zbl 0919.05027 · doi:10.1023/A:1018611014097
[11] Björner, A.: Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries. In: Building Bridges, Bolyai Soc. Math. Stud., vol. 19, pp. 165-203. Springer, Berlin (2008) · Zbl 1158.60344
[12] Björner A.: Note: Random-to-front shuffles on trees. Electron. Commun. Probab. 14, 36-41 (2009) · Zbl 1190.60059 · doi:10.1214/ECP.v14-1445
[13] Björner A., Lovász L., Shor P.W.: Chip-firing games on graphs. Eur. J. Combin 12(4), 283-291 (1991) · Zbl 0729.05048 · doi:10.1016/S0195-6698(13)80111-4
[14] Brown K.S.: Semigroups, rings, and Markov chains. J. Theor. Probab. 13(3), 871-938 (2000) · Zbl 0980.60014 · doi:10.1023/A:1007822931408
[15] Bak P., Tang C., Wiesenfeld K.: Self-organized criticality: an explanation of the 1/f noise. Phys. Rev. Lett. 59(4), 381-384 (1987) · doi:10.1103/PhysRevLett.59.381
[16] Chung F., Graham R.: Edge flipping in graphs. Adv. Appl. Math. 48(1), 37-63 (2012) · Zbl 1234.05210 · doi:10.1016/j.aam.2011.06.002
[17] Cori R., Le Borgne Y.: The sand-pile model and Tutte polynomials. Adv. Appl. Math. 30(1), 44-52 (2003) · Zbl 1030.05058 · doi:10.1016/S0196-8858(02)00524-9
[18] Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups, vol. I. Mathematical Surveys, No. 7. American Mathematical Society, Providence (1961) · Zbl 0111.03403
[19] Derrida B., Evans M.R., Hakim V., Pasquier V.: Exact solution of a 1D asymmetric exclusion model using a matrix formulation. J. Phys. A 26(7), 1493-1517 (1993) · Zbl 0772.60096 · doi:10.1088/0305-4470/26/7/011
[20] Deo, N,: Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall Series in Automatic Computation. Prentice-Hall Inc., Englewood Cliffs (1974) · Zbl 0992.68226
[21] Dhar D.: Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64(14), 1613-1616 (1990) · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613
[22] Dhar D.: The abelian sandpile and related models. Phys. A Stat. Mech. Appl. 263(1), 4-25 (1999) · doi:10.1016/S0378-4371(98)00493-2
[23] Dhar, D.: Some results and a conjecture for Manna’s stochastic sandpile model. Phys. A Stat. Mech. Appl. 270(1), 69-81 (1999) · Zbl 0772.60096
[24] Dhar, D.: Theoretical studies of self-organized criticality. Phys. A Stat. Mech. Appl. 369(1), 29-70 (2006). Fundamental Problems in Statistical Physics Proceedings of the 11th International Summerschool on ‘Fundamental problems in statistical physics’, Leuven, Belgium 11th International Summerschool on ‘Fundamental problems in statistical physics’ · Zbl 0919.05027
[25] Denton, T., Hivert, F., Schilling, A., Thiéry, N.M.: On the representation theory of finite \[{{\mathcal{J}}}\] J-trivial monoids. Sém. Lothar. Combin. 64, Art. B64d, 44 (2010/2011) · Zbl 1296.05201
[26] Diaconis, P.: Group representations in probability and statistics. Institute of Mathematical Statistics Lecture Notes—Monograph Series, vol. 11. Institute of Mathematical Statistics, Hayward (1988) · Zbl 0695.60012
[27] Diaconis, P.: From shuffling cards to walking around the building: an introduction to modern Markov chain theory. In: Proceedings of the International Congress of Mathematicians, vol. I (Berlin, 1998), pp. 187-204 (1998) · Zbl 0902.60052
[28] Devroye L., Lugosi G.: Combinatorial methods in density estimation, Springer Series in Statistics Series. Springer, Berlin (2001) · Zbl 0964.62025
[29] Eilenberg, S.: Automata, languages, and machines, vol. B. Academic Press, Harcourt Brace Jovanovich Publishers, New York (1976) [with two chapters (“Depth decomposition theorem” and “Complexity of semigroups and morphisms”) by Bret Tilson, Pure and Applied Mathematics, vol. 59 (1976)] · Zbl 0359.94067
[30] Goles E., Morvan M., Phan H.D.: The structure of a linear chip firing game and related models. Theor. Comput. Sci. 270(1-2), 827-841 (2002) · Zbl 0992.68226 · doi:10.1016/S0304-3975(01)00119-0
[31] Grigorchuk R.I., Nekrashevich V.V., Sushchanskiĭ V.I.: Automata, dynamical systems, and groups. Tr. Mat. Inst. Steklova 231(Din. Sist. Avtom. i Beskon. Gruppy), 134-214 (2000) · Zbl 1155.37311
[32] Grigorchuk R.I., Zuk A.: The lamplighter group as a group generated by a 2-state automaton, and its spectrum. Geom. Dedicata 87(1-3), 209-244 (2001) · Zbl 0990.60049 · doi:10.1023/A:1012061801279
[33] Higgins, P.M.: Techniques of semigroup theory. Oxford Science Publications. The Clarendon Press Oxford University Press, New York (1992) (with a foreword by G. B. Preston) · Zbl 0744.20046
[34] Holroyd, A.E., Levine, L., Mészáros, K., Peres, Y., Propp, J., Wilson, D.B.: Chip-firing and rotor-routing on directed graphs. In and Out of Equilibrium 2, pp. 331-364 (2008) · Zbl 1173.82339
[35] Howie, J.M.: Fundamentals of semigroup theory, London Mathematical Society Monographs. New Series, vol. 12. Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, (1995) · Zbl 0835.20077
[36] Ivashkevich E.V., Priezzhev V.B.: Introduction to the sandpile model. Phys. A Stat. Mech. Appl. 254(1-2), 97-116 (1998) · doi:10.1016/S0378-4371(98)00012-0
[37] Krohn, K., Rhodes, J., Tilson, B.: Algebraic theory of machines, languages, and semigroups, Chapters 1, 5-9. In: Arbib, M.A. (ed.) With a major contribution by Kenneth Krohn and John L. Rhodes. Academic Press, New York (1968) · Zbl 0446.68066
[38] Kambites M., Silva P.V., Steinberg B.: The spectra of lamplighter groups and Cayley machines. Geom. Dedicata 120, 193-227 (2006) · Zbl 1168.20012 · doi:10.1007/s10711-006-9086-8
[39] Levin, D.A., Peres, Y., Wilmer, E.L.: Markov chains and mixing times. American Mathematical Society, Providence (2009) (with a chapter by James G. Propp and David B. Wilson) · Zbl 1160.60001
[40] Manna S.S.: Two-state model of self-organized criticality. J. Phys. A Math. Gen. 24(7), L363 (1991) · doi:10.1088/0305-4470/24/7/009
[41] Meldrum J.D.P.: Wreath products of groups and semigroups, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 74. Longman, Harlow (1995) · Zbl 0833.20001
[42] Meldrum J.D.P.: Wreath products of groups and semigroups, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 74. Longman, Harlow (1995) · Zbl 0833.20001
[43] MacDonald C.T., Gibbs J.H.: Concerning the kinetics of polypeptide synthesis on polyribosomes. Biopolymers 7(5), 707-725 (1969) · doi:10.1002/bip.1969.360070508
[44] MacDonald C.T., Gibbs J.H., Pipkin A.C.: Kinetics of biopolymerization on nucleic acid templates. Biopolymers 6(1), 1-25 (1968) · doi:10.1002/bip.1968.360060102
[45] Margolis S., Steinberg B.: Quivers of monoids with basic algebras. Compos. Math. 148(5), 1516-1560 (2012) · Zbl 1292.20069 · doi:10.1112/S0010437X1200022X
[46] Nekrashevych, V.: Self-similar groups, Mathematical Surveys and Monographs, vol. 117. American Mathematical Society, Providence (2005) · Zbl 1087.20032
[47] Pin, J.-E.: Varieties of formal languages. Foundations of Computer Science. Plenum Publishing Corp., New York (1986) (with a preface by M.-P. Schützenberger, Translated from the French by A. Howie) · Zbl 0919.05027
[48] Postnikov A., Shapiro B.: Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Am. Math. Soc. 356(8), 3109-3142 (2004). (electronic) · Zbl 1043.05038 · doi:10.1090/S0002-9947-04-03547-0
[49] Rhodes J., Steinberg B.: The q-theory of finite semigroups, Springer Monographs in Mathematics. Springer, New York (2009) · Zbl 1186.20043 · doi:10.1007/b104443
[50] Stein W.A., et al. Sage Mathematics Software (Version 5.9). The Sage Development Team (2013). http://www.sagemath.org
[51] The Sage-Combinat community. Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2008). http://combinat.sagemath.org
[52] Sadhu T., Dhar D.: Steady state of stochastic sandpile models. J. Stat. Phys. 134(3), 427-441 (2009) · Zbl 1162.82013 · doi:10.1007/s10955-009-9683-7
[53] Schütz G.M., Ramaswamy R., Barma M.: Pairwise balance and invariant measures for generalized exclusion processes. J. Phys. A Math. Gen. 29(4), 837 (1996) · Zbl 0943.82548 · doi:10.1088/0305-4470/29/4/011
[54] Stanley, R.P.: Enumerative combinatorics, vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62. Cambridge University Press, Cambridge (1999) (with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin) · Zbl 0928.05001
[55] Steinberg B.: Möbius functions and semigroup representation theory. J. Combin. Theory Ser. A 113(5), 866-881 (2006) · Zbl 1148.20049 · doi:10.1016/j.jcta.2005.08.004
[56] Steinberg B.: Möbius functions and semigroup representation theory. II. Character formulas and multiplicities. Adv. Math. 217(4), 1521-1557 (2008) · Zbl 1155.20057 · doi:10.1016/j.aim.2007.12.001
[57] Sasamoto T., Wadati M.: Exact results for one-dimensional totally asymmetric diffusion models. J. Phys. A Math. Gen. 31(28), 6057 (1998) · Zbl 1085.83501 · doi:10.1088/0305-4470/31/28/019
[58] Tripathy G., Barma M.: Steady state and dynamics of driven diffusive systems with quenched disorder. Phys. Rev. Lett. 78, 3039-3042 (1997) · doi:10.1103/PhysRevLett.78.3039
[59] Toumpakari, E.C.: On the Abelian Sandpile Model. Ph.D. thesis, University of Chicago, Department of Mathematics (2005) · Zbl 1120.05042
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.