Chip-Firing And A Devil's Staircase

Abstract

The devil's staircase ― a continuous function on the unit interval $[0,1]$ which is not constant, yet is locally constant on an open dense set ― is the sort of exotic creature a combinatorialist might never expect to encounter in "real life.'' We show how a devil's staircase arises from the combinatorial problem of parallel chip-firing on the complete graph. This staircase helps explain a previously observed "mode locking'' phenomenon, as well as the surprising tendency of parallel chip-firing to find periodic states of small period.

Keywords

• circle map
• fixed-energy sandpile
• mode locking
• non-ergodicity
• parallel chip-firing
• rotation number
• short period attractors
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]