×

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.

MSC:

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

References:

[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.; 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, (Lovász, L.; Recski, A., Matroid Theory and its Applications, Coll. Math. Soc. J. Bolyai, Vol. 40 (1985), North-Holland: North-Holland Amsterdam), 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, (White, N., Matroid Applications (1991), Cambridge University Press), 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; 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, (Kay, D. C.; Breehm, M., Convexity and Related Combinatorial Geometry, Lecture Notes in Pure and Applied Mathematics 76 (1982), Dekker: Dekker New York), 113-150 · Zbl 0482.52001
[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, (Bollobás, B., Graph Theory and Combinatorics, Proceedings of the Cambridge Combinatorial Conference in Honour of P. Erdös (1984), Academic Press: Academic Press New York/London), 219-232 · Zbl 0553.05030
[12] Reisig, W., Petri Nets: An Introduction (1985), Springer-Verlag: 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.