Abstract
We consider the following (solitary) game: each node of a directed graph contains a pile of chips. A move consists of selecting a node with at least as many chips as its outdegree, and sending one chip along each outgoing edge to its neighbors. We extend to directed graphs several results on the undirected version obtained earlier by the authors, P. Shor, and G. Tardos, and we discuss some new topics such as periodicity, reachability, and probabilistic aspects.
Among the new results specifically concerning digraphs, we relate the length of the shortest period of an infinite game to the length of the longest terminating game, and also to the access time of random walks on the same graph. These questions involve a study of the Laplace operator for directed graphs. We show that for many graphs, in particular for undirected graphs, the problem whether a given position of the chips can be reached from the initial position is polynomial time solvable.
Finally, we show how the basic properties of the “probabilistic abacus” can be derived from our results.
Article PDF
Similar content being viewed by others
References
R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovász, and C.W. Rackoff, “Random walks, universal travelling sequences, and the complexity of maze problem,” Proc. 20th Ann. Symp. on Foundations of Computer Science, 1979, 218–223.
N. Alon, “Eigenvalues and expanders,” Combinatorica 6 (1986), 83–96.
R.J. Anderson, L. Lovász, P.W. Shor, J. Spencer, É. Tardos, and S. Winograd, “Disks, balls, and walls: Analysis of a combinatorial game,” Amer. Math. Monthly 96 (1989), 481–493.
A. Björner, L. Lovász, and P.W. Shor, “Chip-firing games on graphs,” European J. Combin. 12 (1991), 283–291.
A. Björner and G.M. Ziegler, “Introduction to greedoids,” in Matroid Applications, N. White, (ed.), Cambridge Univ. Press, Cambridge, 1992, 284–357.
P. Diaconis and W. Fulton, “A growth model, a game, an algebra, Lagrange inversion, and characteristic classes,” preprint, 1991.
A. Engel, “The probabilistic abacus,” Educ. Stud. in Math. 6 (1975), 1–22.
A. Engel, “Why does the probabilistic abacus work?” Educ. Stud. in Math. 7 (1976), 59–69.
K. Eriksson, “Chip firing games on mutating graphs,” preprint, 1992.
K. Eriksson, “No polynomial bound for the chip-firing game on directed graphs,” Proc. Amer. Math. Soc. 112 (1991), 1203–1205.
R.M. Karp and R.E. Miller, “Parallel program schemata,” J. Computer and System Sci. 3 (1969), 147–195.
J.G. Kemeny and J.L. Snell, Finite Markov Chains, Van Nostrand, Princeton, NJ, 1960.
J.H.B. Kemperman, The Passage Problem for a Stationary Markov Chain, Univ. of Chicago Press, Chicago, 1961.
S.R. Kosaraju, “Decidability of reachability in vector addition systems,” Proc. 14th Ann. ACM Symp. on Theory of Computing, 1982, 267–281.
E.W. Mayr, “An algorithm for the general Petri net reachability problem,” SIAM J. Comput. 13 (1984), 441–460.
H. Minc, Nonnegative Matrices, J. Wiley and Sons, New York, 1988.
W. Reisig, Petri Nets: An Introduction, Springer-Verlag, New York, 1985.
C. Reutenauer, Aspects Mathématiques des Réseaux de Petri, Masson, Paris, 1988.
R. Rimányi, unpublished manuscript, 1988.
J. Spencer, “Balancing vectors in the max norm,” Combinatorica 6 (1986), 55–66.
G. Tardos, “Polynomial bound for a chip-firing game on graphs,” SIAM J. Discrete Math. 1 (1988), 397–398.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Björner, A., Lovász, L. Chip-Firing Games on Directed Graphs. Journal of Algebraic Combinatorics 1, 305–328 (1992). https://doi.org/10.1023/A:1022467132614
Issue Date:
DOI: https://doi.org/10.1023/A:1022467132614