2011/05/11 by Scott T. Chapman, Rebecca Garcia, Chapman, Scott +9
Computer Science · Physics and Astronomy · #05C20 #05C25 #05C38 #05C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Theoretical and Computational Physics #Topological and Geometric Data Analysis #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1105.2357
openalex publication_date 2011/05/11 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
The sandpile group of a graph is a well-studied object that combines ideas\nfrom algebraic graph theory, group theory, dynamical systems, and statistical\nphysics. A graph's sandpile group is part of a larger algebraic structure on\nthe graph, known as its sandpile monoid. Most of the work on sandpiles so far\nhas focused on the sandpile group rather than the sandpile monoid of a graph,\nand has also assumed the underlying graph to be undirected. A notable exception\nis the recent work of Babai and Toumpakari, which builds up the theory of\nsandpile monoids on directed graphs from scratch and provides many connections\nbetween the combinatorics of a graph and the algebraic aspects of its sandpile\nmonoid.\n In this paper we primarily consider sandpile monoids on directed graphs, and\nwe extend the existing theory in four main ways. First, we give a combinatorial\nclassification of the maximal subgroups of a sandpile monoid on a directed\ngraph in terms of the sandpile groups of certain easily-identifiable subgraphs.\nSecond, we point out certain sandpile results for undirected graphs that are\nreally results for sandpile monoids on directed graphs that contain exactly two\nidempotents. Third, we give a new algebraic constraint that sandpile monoids\nmust satisfy and exhibit two infinite families of monoids that cannot be\nrealized as sandpile monoids on any graph. Finally, we give an explicit\ncombinatorial description of the sandpile group identity for every graph in a\nfamily of directed graphs which generalizes the family of (undirected)\ndistance-regular graphs. This family includes many other graphs of interest,\nincluding iterated wheels, regular trees, and regular tournaments.\n