Signed Chip Firing Games and symmetric Sandpile Models on the cycles

Robert Cori; Thi Ha Duong Phan; Thi Thu Huong Tran

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2013)

  • Volume: 47, Issue: 2, page 133-146
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Cori, Robert, Duong Phan, Thi Ha, and 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 47.2 (2013): 133-146. <http://eudml.org/doc/273088>.

@article{Cori2013,
abstract = {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.},
author = {Cori, Robert, Duong Phan, Thi Ha, Huong Tran, Thi Thu},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {sandpile model; chip firing game; circular distribution; symmetric sandpile model; signed chip firing game; lattice structure; chip \{f\}\{\}\{iring\} game},
language = {eng},
number = {2},
pages = {133-146},
publisher = {EDP-Sciences},
title = {Signed Chip Firing Games and symmetric Sandpile Models on the cycles},
url = {http://eudml.org/doc/273088},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Cori, Robert
AU - Duong Phan, Thi Ha
AU - Huong Tran, Thi Thu
TI - Signed Chip Firing Games and symmetric Sandpile Models on the cycles
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 2
SP - 133
EP - 146
AB - 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.
LA - eng
KW - sandpile model; chip firing game; circular distribution; symmetric sandpile model; signed chip firing game; lattice structure; chip {f}{}{iring} game
UR - http://eudml.org/doc/273088
ER -

References

top
  1. [1] P. Bak, C. Tang and K. Wiesenfeld, Self-organized criticality : An explanation of 1/f noise. Phys. Rev. Lett.59 (1987) 381–284. Zbl1230.37103MR949160
  2. [2] A. Björner, L. Lovász and P.W. Shor, Chip-firing games on graphs. Eur. J. Combin.12 (1991) 283–291. Zbl0729.05048MR1120415
  3. [3] R. Cori and D. Rossin, On the sandpile group of dual graphs. Eur. J. Combin.21 (2000) 447–459. Zbl0969.05034MR1756151
  4. [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. Zbl1004.68506
  5. [5] D. Dhar, P. Ruelle, S. Sen and D.-N. Verma, Algebraic aspects of abelian sandpile models. J. Phys. A28 (1995) 805–831. Zbl0848.68062MR1326322
  6. [6] E. Formenti, B. Masson and T. Pisokas, Advances in symmetric sandpiles. Fundam. Inf.76 (2007) 91–112. Zbl1112.37010MR2293052
  7. [7] E. Goles and M.A. Kiwi, Games on line graphes and sand piles. Theoret. Comput. Sci.115 (1993) 321–349. Zbl0785.90120MR1224440
  8. [8] E. Goles, M. Morvan and H.D. Phan, Lattice structure and convergence of a game of cards. Ann. Combin.6 (2002) 327–335. Zbl1093.06001MR1980343
  9. [9] E. Goles, M. Morvan and H.D. Phan. Sandpiles and order structure of integer partitions. Discrete Appl. Math.117 (2002) 51–64. Zbl0998.05005MR1881267
  10. [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. Zbl0992.68226MR1871097
  11. [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. Zbl1054.05007MR2080235
  12. [12] S.-T. Huang. Leader election in uniform rings. ACM Trans. Program. Lang. Syst.15 (1993) 563–573. 
  13. [13] R. Karmakar and S.S. Manna, Particle hole symmetry in a sandpile model, J. Stat. Mech. 2005 (2005) L01002. 
  14. [14] M. Latapy and H.D. Phan, The lattice structure of chip firing games. Physica D115 (2001) 69–82. Zbl0978.68109MR1837204
  15. [15] H.D. Phan, Two sided sand piles model and unimodal sequences. RAIRO – Theor. Inf. Appl.42 (2008) 631–646. Zbl1149.68408MR2434039

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.