The University of Michigan Combinatorics Seminar
Fall 2010
October 1, 4:10-5:00, 3866 East Hall

Chip-firing and a devil's staircase

Lionel Levine

Massachusetts Institute of Technology


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 kind of exotic creature a combinatorialist might never expect to encounter in "real life." I'll show how a devil's staircase arises from the innocent-looking combinatorial problem of parallel chip-firing on the complete graph. This staircase helps explain the surprising tendency of parallel chip-firing to find periodic states of small period. If time permits, I'll also discuss a new generalization of a beautiful formula of Knuth, and its relationship to chip-firing on directed graphs. This talk is based on the papers arXiv:0811.2800 and arXiv:0906.2809.