Sandpiles, spanning trees, and plane duality

DOI10.1137/140982015zbMATH Open1327.05342arXiv1406.5147OpenAlexW1973306025MaRDI QIDQ3453580FDOQ3453580

Authors: Melody Chan, Darren B. Glass, M. Macauley, David Perkinson, Caryn Werner, Qiaoyu Yang 

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1406.5147

Recommendations

• Rotor-routing and spanning trees on planar graphs
• On the sandpile group of dual graphs
• On the sandpile group of regular trees
• Sandpile groups and spanning trees of directed line graphs

zbMATH Keywords

planarityribbon graphschip-firingrotor-router modelsandpiles

Mathematics Subject Classification ID

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

Cites Work

• On the sandpile group of dual graphs
• Riemann-Roch and Abel-Jacobi theory on a finite graph
• The lattice of integral flows and the lattice of integral cuts on a finite graph
• Chip-Firing and Rotor-Routing on Directed Graphs
• Tutte polynomial, subgraphs, orientations and sandpile model: new connections via embeddings
• Rotor-routing and spanning trees on planar graphs
• The Bernardi Process and Torsor Structures on Spanning Trees

Cited In (7)

• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• Title not available (Why is that?)
• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• On Torsor Structures on Spanning Trees
• Geometric bijections between spanning trees and break divisors
• Rotor-routing and spanning trees on planar graphs
• Recognizing hyperelliptic graphs in polynomial time

Uses Software

• MathOverflow

This page was built for publication: Sandpiles, spanning trees, and plane duality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453580)