Algebraic and combinatorial aspects of sandpile monoids on directed graphs
Preprint
Abstract
The sandpile group of a graph is a well-studied object that combines ideas from algebraic graph theory, group theory, dynamical systems, and statistical physics. A graph's sandpile group is part of a larger algebraic structure on the graph, known as its sandpile monoid. Most of the work on sandpiles so far has focused on the sandpile group rather than the sandpile monoid of a graph, and has also assumed the underlying graph to be undirected. A notable exception is the recent work of Babai and Toumpakari, which builds up the theory of sandpile monoids on directed graphs from scratch and provides many connections between the combinatorics of a graph and the algebraic aspects of its sandpile monoid. In this paper we primarily consider sandpile monoids on directed graphs, and we extend the existing theory in four main ways. First, we give a combinatorial classification of the maximal subgroups of a sandpile monoid on a directed graph in terms of the sandpile groups of certain easily-identifiable subgraphs. Second, we point out certain sandpile results for undirected graphs that are really results for sandpile monoids on directed graphs that contain exactly two idempotents. Third, we give a new algebraic constraint that sandpile monoids must satisfy and exhibit two infinite families of monoids that cannot be realized as sandpile monoids on any graph. Finally, we give an explicit combinatorial description of the sandpile group identity for every graph in a family of directed graphs which generalizes the family of (undirected) distance-regular graphs. This family includes many other graphs of interest, including iterated wheels, regular trees, and regular tournaments.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Sandpile groups and spanning trees of directed line graphsJournal of Combinatorial Theory, Series A, 2011
- The sandpile group of a treeEuropean Journal of Combinatorics, 2009
- Chip-Firing and Rotor-Routing on Directed Graphs2008
- On the sandpile group of regular treesEuropean Journal of Combinatorics, 2007
- Topics in Algebraic Graph Theory, by Lowell W. Beineke and Robin J. Wilson (Academic Consultant: Peter J. Cameron), Encyclopedia of Mathematics and its Applications 102, CUP 2005, 257pp., £ 50.00/$95.00Combinatorics, Probability and Computing, 2006
- Theoretical studies of self-organized criticalityPhysica A: Statistical Mechanics and its Applications, 2006
- Algebraic Graph Theory2001
- On the Sandpile Group of Dual GraphsEuropean Journal of Combinatorics, 2000
- Chip-Firing and the Critical Group of a GraphJournal of Algebraic Combinatorics, 1999
- Chip-firing Games on GraphsEuropean Journal of Combinatorics, 1991