Signed Chip Firing Games and symmetric Sandpile Models on the cycles
Cori, Robert ; Duong Phan, Thi Ha ; Huong Tran, Thi Thu
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013), p. 133-146 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We investigate the Sandpile Model and Chip Firing Game and an extension of these models on cycle graphs. The extended model consists of allowing a negative number of chips at each vertex. We give the characterization of reachable configurations and of fixed points of each model. At the end, we give explicit formula for the number of their fixed points.

Publié le : 2013-01-01
DOI : https://doi.org/10.1051/ita/2012023
Classification:  05C57,  91A43,  68R15,  68Rxx 
@article{ITA_2013__47_2_133_0,
     author = {Cori, Robert and Duong Phan, Thi Ha and Huong Tran, Thi Thu},
     title = {Signed Chip Firing Games and symmetric Sandpile Models on the cycles},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {47},
     year = {2013},
     pages = {133-146},
     doi = {10.1051/ita/2012023},
     mrnumber = {3072314},
     zbl = {1266.05098},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2013__47_2_133_0}
}

Cori, Robert; Duong Phan, Thi Ha; Huong Tran, Thi Thu. Signed Chip Firing Games and symmetric Sandpile Models on the cycles. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 47 (2013) pp. 133-146. doi : 10.1051/ita/2012023. http://gdmltest.u-ga.fr/item/ITA_2013__47_2_133_0/

[1] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality : An explanation of 1/f noise. Phys. Rev. Lett. 59 (1987) 381-284. | MR 949160 | Zbl 1230.37103

[2] A. Björner, L. Lovász and P.W. Shor, Chip-firing games on graphs. Eur. J. Combin. 12 (1991) 283-291. | MR 1120415 | Zbl 0729.05048

[3] R. Cori and D. Rossin, On the sandpile group of dual graphs. Eur. J. Combin. 21 (2000) 447-459. | MR 1756151 | Zbl 0969.05034

[4] J. Desel, E. Kindler, T. Vesper and R. Walter, A simplified proof for the self-stabilizing protocol : A game of cards. Inf. Process. Lett. 54 (1995) 327-328. | Zbl 1004.68506

[5] D. Dhar, P. Ruelle, S. Sen and D.-N. Verma, Algebraic aspects of abelian sandpile models. J. Phys. A 28 (1995) 805-831. | MR 1326322 | Zbl 0848.68062

[6] E. Formenti, B. Masson and T. Pisokas, Advances in symmetric sandpiles. Fundam. Inf. 76 (2007) 91-112. | MR 2293052 | Zbl 1112.37010

[7] E. Goles and M.A. Kiwi, Games on line graphes and sand piles. Theoret. Comput. Sci. 115 (1993) 321-349. | MR 1224440 | Zbl 0785.90120

[8] E. Goles, M. Morvan and H.D. Phan, Lattice structure and convergence of a game of cards. Ann. Combin. 6 (2002) 327-335. | MR 1980343 | Zbl 1093.06001

[9] E. Goles, M. Morvan and H.D. Phan. Sandpiles and order structure of integer partitions. Discrete Appl. Math. 117 (2002) 51-64. | MR 1881267 | Zbl 0998.05005

[10] E. Goles, M. Morvan and H.D. Phan, The structure of linear chip firing game and related models. Theoret. Comput. Sci. 270 (2002) 827-841. | MR 1871097 | Zbl 0992.68226

[11] É. Goles and M. Latapy, Clémence Magnien, Michel Morvan and Ha Duong Phan. Sandpile models and lattices : a comprehensive survey. Theoret. Comput. Sci. 322 (2004) 383-407. | MR 2080235 | Zbl 1054.05007

[12] S.-T. Huang. Leader election in uniform rings. ACM Trans. Program. Lang. Syst. 15 (1993) 563-573.

[13] R. Karmakar and S.S. Manna, Particle hole symmetry in a sandpile model, J. Stat. Mech. 2005 (2005) L01002.

[14] M. Latapy and H.D. Phan, The lattice structure of chip firing games. Physica D 115 (2001) 69-82. | MR 1837204 | Zbl 0978.68109

[15] H.D. Phan, Two sided sand piles model and unimodal sequences. RAIRO - Theor. Inf. Appl. 42 (2008) 631-646. | Numdam | MR 2434039 | Zbl 1149.68408