Abelian sandpile model and Biggs-Merino polynomial for directed graphs

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 $c_0+c_{1}y+\dots c_n{y}^n$, where $c_i$ is the number of recurrent classes of the sandpile model with level $i$, 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 $G$-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 $c_0+c_{1}y+\dots c_n{y}^n$ is equal to the greedoid polynomial of the graph.

v3 incorporates referee comments, improves proofs and notations

References in corpus (2)

• 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