Séminaire Lotharingien de Combinatoire, 78B.30 (2017), 12 pp.
Sam Hopkins, Thomas McConville and Jim Propp
Sorting via Chip-Firing
Abstract.
We investigate a variant of the chip-firing process on the infinite
path graph Z: rather than treating the chips as
indistinguishable, we label them with positive integers. To fire an
unstable vertex, i.e., a vertex with more than one chip, we choose any
two chips at that vertex and move the lesser-labeled chip to the left
and the greater-labeled chip to the right. This labeled version of
the chip-firing process exhibits a remarkable confluence property,
similar to but subtler than the confluence that prevails for unlabeled
chip-firing: when all chips start at the origin and the number of
chips is even, the chips always end up in sorted order. Our proof of
sorting relies upon an independently interesting lemma concerning
unlabeled chip-firing which says that stabilization preserves a
natural partial order on configurations. We also discuss extensions to
other variants of the infinite path, an intriguing empirical
observation on random firing of labeled chips, and a possible
generalization to other types.
Received: November 14, 2016.
Accepted: February 17, 2017.
Final version: April 1, 2017.
The following versions are available: