Chip-firing games on graphs. (English) Zbl 0729.05048

Summary: We analyse the following (solitaire) game: each node of a graph contains a pile of chips, and a move consists of selecting a node with at least as many chips on it as its degree, and letting it send one chip to each of its neighbors. The game terminates if there is no such node. We show that the finiteness of the game and the terminating configuration are independent of the moves made. If the number of chips is less than the number of edges, the game is always finite. If the number of chips is at least the number of edges, the game can be infinite for an appropriately chosen initial configuration. If the number of chips is more than twice the number of edges minus the number of nodes, then the game is always infinite.
The independence of the finiteness and the terminating position follows from simple but powerful ‘exchange properties’ of the sequences of legal moves, and from some general results on ‘antimatroids with repetition’, i.e. languages having these exchange properties. We relate the number of steps in a finite game to the least positive eigenvalue of the Laplace operator of the graph.


05C99 Graph theory
90C10 Integer programming
Full Text: DOI


[1] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[2] R. J. Anderson, L. Lovász, P. W. Shor, J. Spencer, E. Tardos and S. Winograd, Disks, balls, and walls: analysis of a combinatorial game, to appear in Am. Math. Monthly. · Zbl 0693.90110
[3] Björner, A., On matroids, groups and exchange languages, (), 25-60
[4] Björner, A.; Korte, B.; Lovász, L., Homotopy properties of greedoids, Adv. appl. math., 6, 447-494, (1985) · Zbl 0642.05014
[5] Björner, A.; Ziegler, G.M., Introduction to greedoids, (), 284-357 · Zbl 0772.05026
[6] Crapo, H., Selectors: a theory of formal languages, semimodular lattices, branchings, and shelling processes, Adv. math, 54, 233-277, (1984) · Zbl 0583.68037
[7] Edelman, P., Meet-distributive lattices and the anti-exchange closure, Alg. univ., 10, 290-299, (1980) · Zbl 0442.06004
[8] U. Faigle, O. Goecke and R. Schrader, Church-Rosser decomposition in combinatorial structures, preprint, Institute for Operations Research, University of Bonn, 1986. To appear in Math. Op. Res.
[9] Jamison, R.E., A perspective on abstract convexity: classifying alignments by varieties, (), 113-150
[10] Korte, B.; Lovász, L., Structural properties of greedoids, Combinatorica, 3, 359-374, (1983) · Zbl 0526.05018
[11] Korte, B.; Lovász, L., Shelling structures, convexity, and a happy end, (), 219-232 · Zbl 0553.05030
[12] Reisig, W., Petri nets: an introduction, (1985), Springer-Verlag New York · Zbl 0555.68033
[13] Spencer, J., Balancing vectors in the MAX norm, Combinatorica, 6, 55-66, (1986) · Zbl 0593.90110
[14] Tardos, G., Polynomial bound for a chip firing game on graphs, SIAM J. discr. math., 1, 397-398, (1988) · Zbl 0652.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.