Abelian sandpile model and Biggs-Merino polynomial for directed graphs
arXiv:1412.4837 · doi:10.1016/j.jcta.2017.08.013
Abstract
We prove several results concerning a polynomial that arises from the sandpile model on directed graphs; these results are previously only known for undirected graphs. Implicit in the sandpile model is the choice of a sink vertex, and it is conjectured by Perrot and Pham that the polynomial , where is the number of recurrent classes of the sandpile model with level , is independent of the choice of the sink. We prove their conjecture by expressing the polynomial as an invariant of the sinkless sandpile model. We then present a bijection between arborescences of directed graphs and reverse -parking functions that preserves external activity by generalizing Cori-Le Borgne bijection for undirected graphs. As an application of this bijection, we extend Merino's Theorem by showing that for Eulerian directed graphs the polynomial is equal to the greedoid polynomial of the graph.
arXiv commentv3 incorporates referee comments, improves proofs and notations
References in corpus (8)
- Eulerian Walkers as a model of Self-Organised Criticality
- Chip-Firing and Rotor-Routing on Directed Graphs
- Chip-firing games, potential theory on graphs, and spanning trees
- Canonical representatives for divisor classes on tropical curves and the Matrix-Tree Theorem
- Multiple and inverse topplings in the Abelian Sandpile Model
- Diophantine Geometry and Analytic Spaces
- A family of bijections between G-parking functions and spanning trees
- A Bijection Between the Recurrent Configurations of a Hereditary Chip-Firing Model and Spanning Trees
Cited by in corpus (4)
- Root polytopes and Jaeger-type dissections for directed graphs
- Abelian networks IV. Dynamics of nonhalting networks
- A geometric proof for the root-independence of the greedoid polynomial of Eulerian branching greedoids
- #P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method