×

Parallel rank of two sandpile models of signed integer partitions. (English) Zbl 1268.06001

Summary: We introduce the concept of a fundamental sequence for a finite graded poset \(X\) which is also a discrete dynamical model. The fundamental sequence concept is a refinement of the concept of parallel convergence time for these models. We compute the parallel convergence time and the fundamental sequence when \(X\) is the finite lattice \(P(n, r)\) of all the signed integer partitions \(a_r, \dots, a_1\), \(b_1, \dots, b_{n-r}\) such that \(r \geq a_r \geq \cdots \geq a_1 \geq 0 \geq b_1 \geq \cdots \geq b_{n-r} \geq -(n - r)\), where \(n \geq r \geq 0\), and when \(X\) is the sublattice \(P(n, d, r)\) of all the signed integer partitions of \(P(n, r)\) having exactly \(d\) nonzero parts.

MSC:

06A07 Combinatorics of partially ordered sets
05D99 Extremal combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] É. Goles, M. Latapy, C. Magnien, M. Morvan, and H. D. Phan, “Sandpile models and lattices: a comprehensive survey,” Theoretical Computer Science, vol. 322, no. 2, pp. 383-407, 2004. · Zbl 1054.05007
[2] T. Brylawski, “The lattice of integer partitions,” Discrete Mathematics, vol. 6, pp. 201-219, 1973. · Zbl 0283.06003
[3] E. Goles, “Sand pile automata,” Annales de l’Institut Henri Poincaré A, vol. 56, no. 1, pp. 75-90, 1992. · Zbl 0791.68118
[4] E. Goles and M. A. Kiwi, “Games on line graphs and sand piles,” Theoretical Computer Science, vol. 115, no. 2, pp. 321-349, 1993. · Zbl 0785.90120
[5] P. Bak, C. Tang, and K. Wiesenfeld, “Self-organized criticality,” Physical Review A, vol. 38, no. 1, pp. 364-374, 1988. · Zbl 1230.37103
[6] D. Dhar, “The abelian sandpiles and related models,” Physica A, vol. 263, no. 1-4, pp. 4-25, 1999.
[7] E. Goles and M. Margenstern, “Universality of the chip-firing game,” Theoretical Computer Science, vol. 172, no. 1-2, pp. 121-134, 1997. · Zbl 0903.68138
[8] E. Goles, M. Morvan, and H. D. Phan, “Lattice structure and convergence of a game of cards,” Annals of Combinatorics, vol. 6, no. 3-4, pp. 327-335, 2002. · Zbl 1093.06001
[9] G. Cattaneo, M. Comito, and D. Bianucci, “Sand piles: from physics to cellular automata models,” Theoretical Computer Science, vol. 436, pp. 35-53, 2012. · Zbl 1251.37017
[10] A. Dennunzio, P. Guillon, and B. Masson, “Sand automata as cellular automata,” Theoretical Computer Science, vol. 410, no. 38-40, pp. 3962-3974, 2009. · Zbl 1171.68023
[11] E. Goles and M. A. Kiwi, “One-dimensional sand piles, cellular automata and related models,” in Nonlinear Phenomena in Fluids, Solids and Other Complex Systems (Santiago, 1990), North-Holland Delta Series, pp. 169-185, North-Holland, Amsterdam, The Netherlands, 1991.
[12] J. Cervelle and E. Formenti, “On sand automata,” in Mathematical Foundations of Computer Science 2003, vol. 2607 of Lecture Notes in Computer Science, pp. 642-653, Springer, Berlin, Germany, 2003. · Zbl 1035.68065
[13] J. Cervelle, E. Formenti, and B. Masson, “Basic properties for sand automata,” in Mathematical Foundations of Computer Science 2005, vol. 3618 of Lecture Notes in Computer Science, pp. 192-211, Springer, Berlin, Germany, 2005. · Zbl 1156.68486
[14] J. Cervelle, E. Formenti, and B. Masson, “From sandpiles to sand automata,” Theoretical Computer Science, vol. 381, no. 1-3, pp. 1-28, 2007. · Zbl 1155.68051
[15] E. Formenti and B. Masson, “On computing the fixed points for generalized sandpiles,” International Journal of Unconventional Computing, vol. 2, no. 1, pp. 13-25, 2005.
[16] E. Formenti and B. Masson, “A note on fixed points of generalized ice piles models,” International Journal of Unconventional Computing, vol. 2, no. 2, pp. 183-191, 2006.
[17] E. Formenti, B. Masson, and T. Pisokas, “On symmetric sandpiles,” in Cellular Automata, vol. 4173 of Lecture Notes in Computer Science, pp. 676-685, Springer, Berlin, Germany, 2006. · Zbl 1155.82320
[18] E. Formenti, B. Masson, and T. Pisokas, “Advances in symmetric sandpiles,” Fundamenta Informaticae, vol. 76, no. 1-2, pp. 91-112, 2007. · Zbl 1112.37010
[19] E. Goles, M. Morvan, and H. D. Phan, “Sandpiles and order structure of integer partitions,” Discrete Applied Mathematics, vol. 117, no. 1-3, pp. 51-64, 2002. · Zbl 0998.05005
[20] M. H. Le and T. H. D. Phan, “Strict partitions and discrete dynamical systems,” Theoretical Computer Science, vol. 389, no. 1-2, pp. 82-90, 2007. · Zbl 1143.68049
[21] M. Latapy, “Partitions of an integer into powers,” in Discrete Models: Combinatorics, Computation, and Geometry (Paris, 2001), Discrete Mathematics and Theoretical Computer Science, pp. 215-228, 2001. · Zbl 1002.11074
[22] M. Latapy, “Integer partitions, tilings of 2D-gons and lattices,” RAIRO-Theoretical Informatics and Applications, vol. 36, no. 4, pp. 389-399, 2002. · Zbl 1028.05010
[23] M. Latapy, R. Mantaci, M. Morvan, and H. D. Phan, “Structure of some sand piles model,” Theoretical Computer Science, vol. 262, no. 1-2, pp. 525-556, 2001. · Zbl 0983.68085
[24] M. Latapy and H. D. Phan, “The lattice structure of chip firing games and related models,” Physica D, vol. 155, no. 1-2, pp. 69-82, 2001. · Zbl 0978.68109
[25] M. Latapy and T. H. D. Phan, “The lattice of integer partitions and its infinite extension,” Discrete Mathematics, vol. 309, no. 6, pp. 1357-1367, 2009. · Zbl 1168.05007
[26] K. Perrot and E. Rémila, “Transduction on Kadanoff sand pile model avalanches, application to wave pattern emergence,” in Mathematical Foundations of Computer Science 2011, vol. 6907 of Lecture Notes in Comput. Sci., pp. 508-519, Springer, Heidelberg, Germany, 2011. · Zbl 1343.37011
[27] K. Perrot, T. H. D. Phan, and T. van Pham, “On the set of fixed points of the parallel symmetric sand pile model,” in Automata 2011-17th International Workshop on Cellular Automata and Discrete Complex Systems, Discrete Mathematics and Theoretical Computer Science, pp. 17-28, Discrete Mathematics and Theoretical Computer Science Proceedings, 2011. · Zbl 1323.37014
[28] T. H. D. Phan, “Two sided sand piles model and unimodal sequences,” RAIRO-Theoretical Informatics and Applications, vol. 42, no. 3, pp. 631-646, 2008. · Zbl 1149.68408
[29] P. T. H. Duong and T. T. T. Huong, “On the stability of sand piles model,” Theoretical Computer Science, vol. 411, no. 3, pp. 594-601, 2010. · Zbl 1184.68352
[30] G. E. Andrews, “Euler’s ‘de Partitio numerorum’,” Bulletin of the American Mathematical Society, vol. 44, no. 4, pp. 561-573, 2007. · Zbl 1172.11031
[31] W. J. Keith, “A bijective toolkit for signed partitions,” Annals of Combinatorics, vol. 15, no. 1, pp. 95-117, 2011. · Zbl 1233.05031
[32] G. Chiaselotti, “On a problem concerning the weight functions,” European Journal of Combinatorics, vol. 23, no. 1, pp. 15-22, 2002. · Zbl 0998.05064
[33] G. Chiaselotti, G. Infante, and G. Marino, “New results related to a conjecture of Manickam and Singhi,” European Journal of Combinatorics, vol. 29, no. 2, pp. 361-368, 2008. · Zbl 1131.05093
[34] G. Chiaselotti, G. Marino, and C. Nardi, “A minimum problem for finite sets of real numbers with nonnegative sum,” Journal of Applied Mathematics, vol. 2012, Article ID 847958, 15 pages, 2012. · Zbl 1273.11045
[35] G. Marino and G. Chiaselotti, “A method to count the positive 3-subsets in a set of real numbers with non-negative sum,” European Journal of Combinatorics, vol. 23, no. 5, pp. 619-629, 2002. · Zbl 1021.05003
[36] C. Bisi, G. Chiaselotti, and P. A. Oliverio, “Sand piles models of signed partitions with d piles,” ISRN Combinatorics, vol. 2013, Article ID 615703, 7 pages, 2013. · Zbl 1264.05007
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.