Enumeration and Quasipolynomiality of Chip-Firing Configurations

2011/04/02 by Schneider, Jon
#Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics

paper · doi:10.48550/arxiv.1104.0279

Abstract

In this paper we explore enumeration problems related to the number of reachable configurations in a chip-firing game on a finite connected graph G. We define an auxiliary notion of debt-reachability and prove that the number of debt-reachable configurations from an initial configuration with c chips on one vertex is a quasipolynomial in c. For the cycle graph C_n, we apply these results to compute a near explicit formula for the number of debt-reachable configurations. We then derive polynomial asymptotic bounds for the number of debt-reachable and reachable configurations, and finally provide evidence for a quasipolynomiality conjecture regarding the number of reachable configurations.

Related

• Self-Reachable Chip Configurations on Trees
• On Chip-Firing on Undirected Binary Trees
• On the Period Lengths of the Parallel Chip-Firing Game
• On lengths of burn-off chip-firing games
• A maximizing characteristic for critical configurations of chip-firing games on digraphs