Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T00:55:52.141Z Has data issue: false hasContentIssue false
  • English
  • Français

Parallel chip-firing on the complete graph: Devil’s staircase and Poincaré rotation number

Published online by Cambridge University Press:  06 May 2010

LIONEL LEVINE
LIONEL LEVINE*
Affiliation:
Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Ave., Cambridge, MA 02139, USA (email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We study how parallel chip-firing on the complete graph Kn changes behavior as we vary the total number of chips. Surprisingly, the activity of the system, defined as the average number of firings per time step, does not increase smoothly in the number of chips; instead it remains constant over long intervals, punctuated by sudden jumps. In the large n limit we find a ‘devil’s staircase’ dependence of activity on the number of chips. The proof proceeds by reducing the chip-firing dynamics to iteration of a self-map of the circle S1, in such a way that the activity of the chip-firing state equals the Poincaré rotation number of the circle map. The stairs of the devil’s staircase correspond to periodic chip-firing states of small period.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 31 , Issue 3 , June 2011 , pp. 891 - 910
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bagnoli, F., Cecconi, F., Flammini, A. and Vespignani, A.. Short-period attractors and non-ergodic behavior in the deterministic fixed-energy sandpile model. Europhys. Lett. 63 (2003), 512–518.CrossRefGoogle Scholar
[2]Bak, P., Tang, C. and Wiesenfeld, K.. Self-organized criticality: an explanation of the 1/f noise. Phys. Rev. Lett. 59(4) (1987), 381–384.CrossRefGoogle Scholar
[3]Bitar, J.. Juegos combinatoriales en redes de autómatas. Tesis Ingeniero Matemático, Dept. Ingeniería Matemática, U. de Chile, 1989.Google Scholar
[4]Bitar, J. and Goles, E.. Parallel chip firing games on graphs. Theoret. Comput. Sci. 92(2) (1992), 291–300.CrossRefGoogle Scholar
[5]Björner, A., Lovász, L. and Shor, P.. Chip-firing games on graphs. European J. Combin. 12(4) (1991), 283–291.CrossRefGoogle Scholar
[6]Casartelli, M., Dall’Asta, L., Vezzani, A. and Vivo, P.. Dynamical invariants in the deterministic fixed-energy sandpile. European Phys. J. B 52(1) (2006), 91–105.CrossRefGoogle Scholar
[7]Dall’Asta, L.. Exact solution of the one-dimensional deterministic fixed-energy sandpile. Phys. Rev. Lett. 96(5) (2006), 058003.CrossRefGoogle ScholarPubMed
[8]Dhar, D.. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett. 64 (1990), 1613–1616.CrossRefGoogle ScholarPubMed
[9]Hasselblatt, B. and Katok, A.. A First Course in Dynamics, with a Panorama of Recent Developments. Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
[10]Janowsky, S. A. and Laberge, C. A.. Exact solutions for a mean-field abelian sandpile. J. Phys. A 26 (1993), L973–L980.CrossRefGoogle Scholar
[11]Kiwi, M. A., Ndoundam, R., Tchuente, M. and Goles, E.. No polynomial bound for the period of the parallel chip firing game on graphs. Theoret. Comput. Sci. 136(2) (1994), 527–532.CrossRefGoogle Scholar
[12]Lagarias, J. C.. Number theory and dynamical systems. Proc. Sympos. Appl. Math. 46 (1992), 35–72.CrossRefGoogle Scholar
[13]de Melo, W. and van Strien, S.. One-Dimensional Dynamics. Springer, Berlin, 1991.Google Scholar
[14]Prisner, E.. Parallel chip-firing on digraphs. Complex Systems 8 (1994), 367–383.Google Scholar
[15]Vespignani, A., Dickman, R., Muñoz, M. A. and Zapperi, S.. Absorbing-state phase transitions in fixed-energy sandpiles. Phys. Rev. E 62 (2000), 4564–4582.CrossRefGoogle ScholarPubMed