×

Sandpiles, spanning trees, and plane duality. (English) Zbl 1327.05342

Summary: Let \(G\) be a connected, loopless multigraph. The sandpile group of \(G\) is a finite abelian group associated to \(G\) whose order is equal to the number of spanning trees in \(G\). Holroyd et al. used a dynamical process on graphs called rotor-routing to define a simply transitive action of the sandpile group of \(G\) on its set of spanning trees. Their definition depends on two pieces of auxiliary data: a choice of a ribbon graph structure on \(G\), and a choice of a root vertex. Chan, Church, and Grochow showed that if \(G\) is a planar ribbon graph, it has a canonical rotor-routing action associated to it; i.e., the rotor-routing action is actually independent of the choice of root vertex. It is well known that the spanning trees of a planar graph \(G\) are in canonical bijection with those of its planar dual \(G^*\), and furthermore that the sandpile groups of \(G\) and \(G^*\) are isomorphic. Thus, one can ask: are the two rotor-routing actions, of the sandpile group of \(G\) on its spanning trees, and of the sandpile group of \(G^*\) on its spanning trees, compatible under plane duality? In this paper, we give an affirmative answer to this question, which had been conjectured by Baker.

MathOverflow Questions:

What is the sandpile torsor?

MSC:

05E18 Group actions on combinatorial structures
05C05 Trees
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Software:

MathOverflow
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Bacher, P. de la Harpe, and T. Nagnibeda, {\it The lattice of integral flows and the lattice of integral cuts on a finite graph}, Bull. Soc. Math. France, 125 (1997), pp. 167-198. · Zbl 0891.05062
[2] M. Baker and S. Norine, {\it Riemann-Roch and Abel-Jacobi theory on a finite graph}, Adv. Math., 215 (2007), pp. 766-788. · Zbl 1124.05049
[3] M. Baker and Y. Wang, {\it The Bernardi Process and Torsor Structures on Spanning Trees}, preprint, 2014. · Zbl 1404.05027
[4] O. Bernardi, {\it Tutte polynomial, subgraphs, orientations and sandpile model: New connections via embeddings}, Electron. J. Combin., 15 (2008), R109. · Zbl 1179.05048
[5] M. Chan, T. Church, and J. Grochow, {\it Rotor-routing and spanning trees on planar graphs}, Int. Math. Res. Not., to appear. · Zbl 1314.05045
[6] R. Cori and D. Rossin, {\it On the sandpile group of dual graphs}, European J. Combin., 21 (2000), pp. 447-459. · Zbl 0969.05034
[7] J. Ellenberg, What is the sandpile torsor? Math Overflow, 2011, http://mathoverflow.net/questions/83552.
[8] A. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp, and D. Wilson, {\it Chip-firing and rotor-routing on directed graphs}, in In and Out of Equilibrium 2, V. Sidoravicius and M. E. Vares, eds., Progress in Probability 60, Birkhäuser, Boston, Cambridge, MA, 2008, pp. 331-364. · Zbl 1173.82339
[9] V. B. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy, {\it Eulerian walkers as a model of self-organized criticality}, Phys. Rev. Lett., 77 (1996), pp. 5079-5082.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.