Abstract
We continue our studies of burn-off chip-firing games from [Discrete Math. Theor. Comput. Sci. 15 (2013), no. 1, 121-132; MR3040546] and [Australas. J. Combin. 68 (2017), no. 3, 330-345; MR3656659]. The latter article introduced randomness by choosing successive seeds uniformly from the vertex set of a graph G. The length of a game is the number of vertices that fire (by sending a chip to each neighbor and annihilating one chip) as an excited chip configuration passes to a relaxed state. This article determines the probability distribution of the game length in a long sequence of burn-off games. Our main results give exact counts for the number of pairs (C, v), with C a relaxed legal configuration and v a seed, corresponding to each possible length. In support, we give our own proof of the well-known equicar-dinality of the set R of relaxed legal configurations on G and the set of spanning trees in the cone G∗ of G. We present an algorithmic, bijective proof of this correspondence.
| Original language | English |
|---|---|
| Pages (from-to) | 53-77 |
| Number of pages | 25 |
| Journal | Journal of Combinatorial Mathematics and Combinatorial Computing |
| Volume | 116 |
| State | Published - Feb 2021 |
Funding
This work was partially supported by a grant from the Simons Foundation (#279367 to Mark Kayll). Most of the manuscript for this article was finalized while the first author was on sabbatical at the University of Otago in Dunedin, New Zealand. The author gratefully acknowledges the support of Otago's Department of Mathematics and Statistics. Both authors thank the referees for the constructive suggestions (and promptness!).
| Funders | Funder number |
|---|---|
| Simons Foundation | 279367 |
Keywords
- Burn-off game
- Chip-firing
- Game-length probability
- Markov chain
- Relaxed legal configuration
- Sandpile group
- Spanning tree