Chip-Firing Games on Directed Graphs
Anders Björner
and László Lovász
DOI: 10.1023/A:1022467132614
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.
Pages: 305–328
Keywords: chip-firing game; vector addition system; reachability; random walk; probabilistic abacus; Laplace operator; Petri net
Full Text: PDF
References
1. R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, 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.
2. N. Alon, "Eigenvalues and expanders," Combinatorica 6 (1986), 83-96.
3. R.J. Anderson, L. Lovasz, P.W. Shor, J. Spencer, E. Tardos, and S. Winograd, "Disks, balls, and walls: Analysis of a combinatorial game," Amer. Math. Monthly 96 (1989), 481-493.
4. A. Bjorner, L. Lovasz, and P.W. Shor, "Chip-firing games on graphs," European J. Combin. 12 (1991), 283-291.
5. A. Bjorner and G.M. Ziegler, "Introduction to greedoids," in Matroid Applications, N. White, (ed.), Cambridge Univ. Press, Cambridge, 1992, 284-357.
6. P. Diaconis and W. Fulton, "A growth model, a game, an algebra, Lagrange inversion, and characteristic classes," preprint, 1991.
7. A. Engel, "The probabilistic abacus," Educ. Stud, in Math. 6 (1975), 1-22.
8. A. Engel, "Why does the probabilistic abacus work?" Educ. Stud, in Math. 7 (1976), 59-69.
9. K. Eriksson, "Chip firing games on mutating graphs," preprint, 1992.
10. K. Eriksson, "No polynomial bound for the chip-firing game on directed graphs," Proc. Amer. Math. Soc. 112 (1991), 1203-1205.
11. R.M. Karp and R.E. Miller, "Parallel program schemata," J. Computer and System Sci. 3 (1969), 147-195.
12. J.G. Kemeny and J.L. Snell, Finite Markov Chains, Van Nostrand, Princeton, NJ, 1960.
13. J.H.B. Kemperman, The Passage Problem for a Stationary Markov Chain, Univ. of Chicago Press, Chicago, 1961.
14. S.R. Kosaraju, "Decidability of reachability in vector addition systems," Proc. 14th Ann. ACM Symp. on Theory of Computing, 1982, 267-281.
15. E.W. Mayr, "An algorithm for the general Petri net reachability problem," SIAM J. Comput. 13 (1984), 441-460.
16. H. Minc, Nonnegative Matrices, J. Wiley and Sons, New York, 1988.
17. W. Reisig, Petri Nets: An Introduction, Springer-Verlag, New York, 1985.
18. C. Reutenauer, Aspects Mathematiques des Reseaux de Petri, Masson, Paris, 1988.
19. R. Rimanyi, unpublished manuscript, 1988.
20. J. Spencer, "Balancing vectors in the max norm," Combinatorica 6 (1986), 55-66.
21. G. Tardos, "Polynomial bound for a chip-firing game on graphs," SIAM J. Discrete Math. 1 (1988), 397-398.
2. N. Alon, "Eigenvalues and expanders," Combinatorica 6 (1986), 83-96.
3. R.J. Anderson, L. Lovasz, P.W. Shor, J. Spencer, E. Tardos, and S. Winograd, "Disks, balls, and walls: Analysis of a combinatorial game," Amer. Math. Monthly 96 (1989), 481-493.
4. A. Bjorner, L. Lovasz, and P.W. Shor, "Chip-firing games on graphs," European J. Combin. 12 (1991), 283-291.
5. A. Bjorner and G.M. Ziegler, "Introduction to greedoids," in Matroid Applications, N. White, (ed.), Cambridge Univ. Press, Cambridge, 1992, 284-357.
6. P. Diaconis and W. Fulton, "A growth model, a game, an algebra, Lagrange inversion, and characteristic classes," preprint, 1991.
7. A. Engel, "The probabilistic abacus," Educ. Stud, in Math. 6 (1975), 1-22.
8. A. Engel, "Why does the probabilistic abacus work?" Educ. Stud, in Math. 7 (1976), 59-69.
9. K. Eriksson, "Chip firing games on mutating graphs," preprint, 1992.
10. K. Eriksson, "No polynomial bound for the chip-firing game on directed graphs," Proc. Amer. Math. Soc. 112 (1991), 1203-1205.
11. R.M. Karp and R.E. Miller, "Parallel program schemata," J. Computer and System Sci. 3 (1969), 147-195.
12. J.G. Kemeny and J.L. Snell, Finite Markov Chains, Van Nostrand, Princeton, NJ, 1960.
13. J.H.B. Kemperman, The Passage Problem for a Stationary Markov Chain, Univ. of Chicago Press, Chicago, 1961.
14. S.R. Kosaraju, "Decidability of reachability in vector addition systems," Proc. 14th Ann. ACM Symp. on Theory of Computing, 1982, 267-281.
15. E.W. Mayr, "An algorithm for the general Petri net reachability problem," SIAM J. Comput. 13 (1984), 441-460.
16. H. Minc, Nonnegative Matrices, J. Wiley and Sons, New York, 1988.
17. W. Reisig, Petri Nets: An Introduction, Springer-Verlag, New York, 1985.
18. C. Reutenauer, Aspects Mathematiques des Reseaux de Petri, Masson, Paris, 1988.
19. R. Rimanyi, unpublished manuscript, 1988.
20. J. Spencer, "Balancing vectors in the max norm," Combinatorica 6 (1986), 55-66.
21. G. Tardos, "Polynomial bound for a chip-firing game on graphs," SIAM J. Discrete Math. 1 (1988), 397-398.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition