×

Sandpile models and lattices: a comprehensive survey. (English) Zbl 1054.05007

Summary: Starting from some studies of (linear) integer partitions, we noticed that the lattice structure is strongly related to a large variety of discrete dynamical models, in particular sandpile models and chip firing games. After giving an historical survey of the main results which appeared about this, we propose a unified framework to explain the strong relationship between these models and lattices. In particular, we show that the apparent complexity of these models can be reduced, by showing the possibility of simplifying them, and we show how the known lattice properties can be deduced from this.

MSC:

05A17 Combinatorial aspects of partitions of integers
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andrews, G. E., The theory of partitions, Encyclopedia of Mathematics and its Applications, Vol. 2 (1976), Addison-Wesley Publishing Company: Addison-Wesley Publishing Company Reading, MA · Zbl 0371.10001
[2] Bak, P., How Nature Works—The Science of SOC (1997), Oxford University Press: Oxford University Press Oxford
[3] Bak, P.; Tang, C.; Wiesenfeld, K., Self-organized criticalityan explanation of the \(1/f\) noise, Phys. Rev. Lett., 59, 4, 381-384 (1987)
[4] Berge, C., Principles of combinatorics, Mathematics in Science and Engineering, Vol. 72 (1971), Academic Press: Academic Press New York · Zbl 0227.05002
[5] K. Bertet, Sur quelques aspects algorithmiques et structurels des treillis, Ph.D. Thesis, Université Paris VII, 1998.; K. Bertet, Sur quelques aspects algorithmiques et structurels des treillis, Ph.D. Thesis, Université Paris VII, 1998.
[6] Biggs, N., Algebraic potential theory on graphs, Bull. London Math. Soc., 29, 641-682 (1997)
[7] Biggs, N., Chip firing and the critical group of a graph, J. Algebraic Combin., 9, 25-45 (1999) · Zbl 0919.05027
[8] Björner, A.; Lovász, L., Chip-firing games on directed graphs, J. Algebraic Combin., 1, 304-328 (1992) · Zbl 0805.90142
[9] Björner, A.; Lovász, L.; Shor, W., Chip-firing games on graphs, European J. Combin., 12, 283-291 (1991) · Zbl 0729.05048
[10] O. Bodini, M. Latapy, Generalized tilings with height functions, (2001), submitted for publication.; O. Bodini, M. Latapy, Generalized tilings with height functions, (2001), submitted for publication.
[11] Brylawski, T., The lattice of integer partitions, Discrete Math., 6, 210-219 (1973) · Zbl 0283.06003
[12] Cori, R.; Rossin, D., On the sandpile group of a graph, European J. Combin., 21, 4, 447-459 (2000) · Zbl 0969.05034
[13] Davey, B. A.; Priestley, H. A., Introduction to Lattices and Orders (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0701.06001
[14] Desel, J.; Kindler, E.; Vesper, T.; Walter, R., A simplified proof of the self-stabilizing protocola game of cards, Inform. Process. Lett., 54, 327-328 (1995) · Zbl 1004.68506
[15] D. Dhar, The abelian sandpile model and related models, 1998, preprint available on Arxiv, at; D. Dhar, The abelian sandpile model and related models, 1998, preprint available on Arxiv, at
[16] Dhar, D.; Majumbar, S. N., Abelian sandpile model on the Bethe lattice, J. Phys. A, 23, 4333-4350 (1990)
[17] Dhar, D.; Ruelle, P.; Sen, S.; Verma, D., Algebraic aspects of sandpile models, J. Phys. A, 28, 805-831 (1995) · Zbl 0848.68062
[18] Eriksson, K., No polynomial bound for the chip firing game on directed graphs, Proc. Amer. Math. Soc., 112, 1203-1205 (1989) · Zbl 0758.05060
[19] K. Eriksson, Strongly convergent games and coxeter groups, Ph.D. Thesis, Kungl Tekniska Hogskolan, Sweden, 1993.; K. Eriksson, Strongly convergent games and coxeter groups, Ph.D. Thesis, Kungl Tekniska Hogskolan, Sweden, 1993.
[20] Goles, E.; Kiwi, M. A., Games on line graphs and sand piles, Theoret. Comput. Sci., 115, 321-349 (1993) · Zbl 0785.90120
[21] Goles, E.; Morvan, M.; Phan, H. D., Lattice structure and convergence of a game of cards, Ann. Combin., 6, 327-335 (2002) · Zbl 1093.06001
[22] E. Goles, M. Morvan, H.D. Phan, Sand piles and order structure of integer partitions, Discrete Appl. Math. (1998), to appear. Preprint available at; E. Goles, M. Morvan, H.D. Phan, Sand piles and order structure of integer partitions, Discrete Appl. Math. (1998), to appear. Preprint available at · Zbl 0998.05005
[23] E. Goles, M. Morvan, H.D. Phan, The structure of linear chip firing games and related models, Theoret. Comput. Sci. (1998), to appear. Preprint available at; E. Goles, M. Morvan, H.D. Phan, The structure of linear chip firing games and related models, Theoret. Comput. Sci. (1998), to appear. Preprint available at · Zbl 0992.68226
[24] J. van den Heuvel, Algorithmic aspects of a chip firing game, London School of Economics, CDAM Research Reports, 1999. Preprint available at; J. van den Heuvel, Algorithmic aspects of a chip firing game, London School of Economics, CDAM Research Reports, 1999. Preprint available at
[25] Ivashkevich, E. V.; Priezzhev, V. V., Introduction to the sandpile model, Physica A, 254, 97-116 (1998)
[26] Jensen, H. J., Self-Organised Criticality (1998), Cambridge University Press: Cambridge University Press Cambridge
[27] M. Latapy, Generalized integer partitions, tilings of zonotopes and lattices, in: A.A. Mikhalev, D. Krob, E.V. Mikhalev (Eds.), Proc. 12th Internat. Conf. Formal Power Series and Algebraic Combinatorics (FPSAC’00), Springer, Berlin, June 2000, pp. 256-267. Preprint available at; M. Latapy, Generalized integer partitions, tilings of zonotopes and lattices, in: A.A. Mikhalev, D. Krob, E.V. Mikhalev (Eds.), Proc. 12th Internat. Conf. Formal Power Series and Algebraic Combinatorics (FPSAC’00), Springer, Berlin, June 2000, pp. 256-267. Preprint available at · Zbl 0960.05005
[28] M. Latapy, Partitions of an integer into powers, in: Discrete Mathematics and Theoretical Computer Science, Proc. 1st Internat. Conf. Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG’01), MIMD, July 2001, pp. 215-228. Preprint available at; M. Latapy, Partitions of an integer into powers, in: Discrete Mathematics and Theoretical Computer Science, Proc. 1st Internat. Conf. Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG’01), MIMD, July 2001, pp. 215-228. Preprint available at · Zbl 1002.11074
[29] M. Latapy, R. Mantaci, M. Morvan, H.D. Phan, Structure of some sand piles model, Theoret. Comput. Sci. 262 (2001) 525-556. Preprint available at; M. Latapy, R. Mantaci, M. Morvan, H.D. Phan, Structure of some sand piles model, Theoret. Comput. Sci. 262 (2001) 525-556. Preprint available at · Zbl 0983.68085
[30] M. Latapy, H.D. Phan, The lattice of integer partitions and its infinite extension, Proc. of ORDAL’99, DMTCS, special issue (1999), to appear. Preprint available at; M. Latapy, H.D. Phan, The lattice of integer partitions and its infinite extension, Proc. of ORDAL’99, DMTCS, special issue (1999), to appear. Preprint available at · Zbl 1168.05007
[31] M. Latapy, H.D. Phan, The lattice structure of chip firing games, Phys. D 115 (2001) 69-82. Preprint available at; M. Latapy, H.D. Phan, The lattice structure of chip firing games, Phys. D 115 (2001) 69-82. Preprint available at · Zbl 0978.68109
[32] MacMahon, P. A., Combinatory Analysis (1916), Cambridge University Press: Cambridge University Press Cambridge · JFM 46.0118.07
[33] C. Magnien, Lattices induced by chip firing games and related models (2001), submitted. Preprint available at; C. Magnien, Lattices induced by chip firing games and related models (2001), submitted. Preprint available at · Zbl 1007.91503
[34] C. Magnien, H.D. Phan, L. Vuillon, Characterization of lattices induced by (extended) chip firing games, in: Discrete Mathematics and Theoretical Computer Science, Proc. 1st Internat. Conf. Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG’01), MIMD, July 2001, pp. 229-244. Preprint available at; C. Magnien, H.D. Phan, L. Vuillon, Characterization of lattices induced by (extended) chip firing games, in: Discrete Mathematics and Theoretical Computer Science, Proc. 1st Internat. Conf. Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG’01), MIMD, July 2001, pp. 229-244. Preprint available at · Zbl 1007.91503
[35] Malhotra, V. M.; Kumar, M. P.; Maheshwari, S. N., An \(o(|v|^2)\) algorithm for finding maximal flows in networks, Inform. Process. Lett., 7, 277-278 (1978) · Zbl 0391.90041
[36] Monjardet, B., The consequences of dilworth’s work on lattices with unique irreductible decompositions, (Bogart, K. P.; Freese, R.; Kung, J., The Dilworth Theorems Selected Papers of Robert P. Dilworth (1990), Birkhauser: Birkhauser Boston), 192-201
[37] Pretzel, O., On reorienting graphs by pushing down maximal vertices, Order, 3, 135-153 (1986) · Zbl 0611.05028
[38] Pretzel, O., Orientations and reorientations of graphs, Contemp. Math., 57, 103-125 (1986) · Zbl 0595.06005
[39] J. Propp, Lattice structure of orientations of graphs (1993), preprint, available at; J. Propp, Lattice structure of orientations of graphs (1993), preprint, available at
[40] Propp, J., Generating random elements of finite distributive lattices, Electron. J. Combin., 4 (1998)
[41] E. Remila, On the lattice structure of the set of tilings of a simply connected figure with dominoes, Theoret. Comput. Sci., to appear.; E. Remila, On the lattice structure of the set of tilings of a simply connected figure with dominoes, Theoret. Comput. Sci., to appear.
[42] R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49, Cambridge University Press, Cambridge, 1997.; R.P. Stanley, Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol. 49, Cambridge University Press, Cambridge, 1997.
[43] C. Tang, Self-organised criticality, OCPA Newsletter, 1993.; C. Tang, Self-organised criticality, OCPA Newsletter, 1993.
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.