A constant bound for the periods of parallel chip-firing games with many chips |
| |
| Authors: | Paul Myer Kominers Scott Duke Kominers |
| |
| Institution: | 1. Department of Economics, Massachusetts Institute of Technology, c/o 8520 Burning Tree Road, Bethesda, MD, 20817, USA
2. Department of Economics, Harvard University, and Harvard Business School, Wyss Hall, Soldiers Field, Boston, MA, 02163, USA
|
| |
| Abstract: | We prove that any parallel chip-firing game on a graph G with at least 4|E(G)| − |V(G)| chips stabilizes, i.e., such a game has eventual period of length 1. Furthermore, we obtain a polynomial bound on the number
of rounds before stabilization. This result is a counterpoint to previous results which showed that the eventual periods of
parallel chip-firing games with few chips need not be polynomially bounded. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
