On lengths of burn-off chip-firing games
From MaRDI portal
Publication:4995310
zbMath1466.05135arXiv2007.09732MaRDI QIDQ4995310
Publication date: 23 June 2021
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 equicardinality of the set $mathcal{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.
Full work available at URL: https://arxiv.org/abs/2007.09732
Markov chainspanning treesandpile groupchip-firingburn-off gamegame-length probabilityrelaxed legal configuration
Trees (05C05) Games involving graphs (91A43) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57)
This page was built for publication: On lengths of burn-off chip-firing games
