Sandpiles, spanning trees, and plane duality

DOI10.1137/140982015MaRDI QIDQ3453580zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(7)

• Geometric bijections for regular matroids, zonotopes, and Ehrhart theory
• scientific article; zbMATH DE number 503444 (Why is no real title available?)
• 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

Describes a project that uses

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)