Chip firing may be much faster than you think

Speaker
Felix Goldberg
Date
07/12/2014 - 13:00 - 12:15Add to Calendar 2014-12-07 12:15:00 2014-12-07 13:00:00 Chip firing may be much faster than you think The chip ring game Bjorner, Lovasz and Shor (BLS) introduced the following game in 1991: N chips are placed on the vertices on a n-vertex graph and at every turn, the solitaire player chooses a vertex i of degree di which has at least di chips on it and "fires" i by shifting a chip from i to each of i's neighbours. The game duration problem BLS have proved the remarkable result that whenever this game terminates, it always does so in the same number of moves, irrespective of gameplay! (I will explain the background for this). They also gave an elegant upper bound on the number of moves. However, computer simulation reveals that the game actually ends in far fewer moves than the BLS bound in all examined cases. The new results I will show a new approach to obtaining upper bounds on the game duration, based on a re nement of the classic BLS analysis together with a simple but potent new observation. The new bounds are always at least as good as the BLS bound and in some cases the improvement is dramatic. For example, for the strongly regular graphs BLS reduces to O(nN) while the new bound reduces to O(n+N). For dense regular graphs BLS reduces to O(N) while the new bound reduces to O(n) (for such it holds that n = O(N)). The proof technique involves a careful analysis of the pseudo-inverse of the graph's discrete Laplacian. The wider context Time permitting, I will also discuss the appearance of chip ring (and its very close relative, the sandpile model) in diverse mathematical and scientific contexts. אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Abstract

The chip ring game Bjorner, Lovasz and Shor (BLS) introduced the following game in 1991: N chips are placed on the vertices on a n-vertex graph and at every turn, the solitaire player chooses a vertex i of degree di which has at least di chips on it and "fires" i by shifting a chip from i to each of i's neighbours.
The game duration problem BLS have proved the remarkable result that whenever this game terminates, it always does so in the same number of moves, irrespective of gameplay! (I will explain the background for this). They also gave an elegant upper bound on the number of moves. However, computer simulation reveals that the game actually ends in far fewer moves than the BLS bound in all examined cases.
The new results I will show a new approach to obtaining upper bounds on the game duration, based on a re nement of the classic BLS analysis together with a simple but potent new observation.
The new bounds are always at least as good as the BLS bound and in some cases the improvement is dramatic. For example, for the strongly regular graphs BLS reduces to O(nN) while the new bound reduces to O(n+N). For dense regular graphs BLS reduces to O(N) while the new bound reduces to O(n) (for such it holds that n = O(N)).
The proof technique involves a careful analysis of the pseudo-inverse of the graph's discrete Laplacian.
The wider context Time permitting, I will also discuss the appearance of chip ring (and its very close relative, the sandpile model) in diverse mathematical and scientific contexts.

Last Updated Date : 03/12/2014