# Mathematical Sciences Research Institute

Home > Education > For Undergraduates > MSRI-UP > 2016 > MSRI-UP 2016 Projects

# MSRI-UP 2016: Sandpile Groups

 Home Research Topic People Colloquia Research Projects Pictures

On the Accessibility Numbers in the Sandpile Monoid of a Graph

Students: Ernest Castorena, Dominika Palinko, Cecily Santiago

Advisors:  Prof. Luis David Garcia Puente, Prof. Ashley K. Wheeler

Abstract: Combinatorists study sandpile groups within the Abelian Sandpile Model, conceived in 1987 by the physicists Bak, Tang, and Wiesenfeld to describe the phenomenon of self-organized criticality.  According to the model, we fix a graph with one distinguished vertex called the sink.  We assign to each non-sink vertex an amount of “sand” a non-negative integer.  If a vertex has an amount of sand greater than or equal to its outdegree then it topples, meaning it sends a grain of sand to each of its adjacent vertices.  A sequence of toppling may result, but the presence of the sink, which we do not allow to topple, ensures the process terminates.  The result is a stable sandpile.  Under the operation stable addition, the combining of sandpiles and allowing toppling until stable, the set of stable sandpiles on a graph forms a monoid.

Within the sandpile monoid are the well-studied recurrent sandpiles, which themselves form a group.  A sandpile is recurrent means it can be accessed via sand addition and toppling by any other stable sandpile.  However, little is known about the remaining stable sandpiles, called transients, or their structure within the monoid.  The accessibility number of a sandpile gives the number of stable sandpiles that can access it.  For example, the accessibility number of a recurrent is the order of the monoid, the accessibility number of a super accessible transient (SAT) is the difference between the order of the monoid and the order of the group, etc.  Accessibility numbers dictate a hierarchy in the monoid which we describe by “nexi”.  In particular, we study the class of c3po sandpiles, (an affectionate working name with a backstory) whose accessibility numbers equal the number of non-SAT transients.  We explicitly exhibit, and then prove, uniqueness of a c3po sandpile for certain classes of trees including paths, stars, and potted plants.

The Sandpile Group of a Thick Cycle Graph

Students: Diane Christine Alar, Jonathan Celaya, Micah Henson

Advisors:  Prof. Luis David Garcia Puente, Prof. Ashley K. Wheeler

Abstract: The set of stable sandpiles on a graph, equipped with stable addition, combining sand from two configurations and then allowing the system to topple until stable, forms an abelian monoid.  The subset of stable sandpiles which can be accessed by any other sandpile in the monoid via stable addition forms a group called the sandpile group.

In this project we examine the thick n-cycle graph, the cycle of n vertices with multiedges allowed.  We prove that the ith invariant factor of the sandpile group is the greatest common divisor (gcd) of the products of the edge multiplicities taken i at a time, divided by the gcd of those taken i-1 at a time; with the first invariant factor equaling the gcd of the edge multiplicities and the last equaling the quotient of the number of spanning trees by the gcd of the (n-2)-products of the edge multiplicities.  A number of corollaries follow – for example, it is immediate that the sandpile group does not depend on the permutation of the edge multiplicities.  Cori and Rossin have shown that a planar graph and its dual graph have isomorphic sandpile groups and so we also get the sandpile groups of the duals to thick cycles, such as the book graphs.  Our main theorem is one of the first general results describing the sandpile group of a family of non-regular multigraphs.

On the Sandpile Group of Circulant Graphs

Students: Anna Comito, Jennifer Garcia, Justin Rivera

Advisors:  Prof. Luis David Garcia Puente, Natalie Hobson

Abstract: Circulant graphs are of interest in many areas of mathematics, particularly geometric group theory, because of the beautiful cyclic symmetries they display. These graphs have adjacency matrices that are circulant and can be defined from a set of integer generators A={a_1, …, a_m}, on a fixed number of n vertices, denoted C_n(A). Given any graph, one can construct a matrix, called the Laplacian matrix, from the data of the degree and adjacencies of each vertex. The cokernel of this matrix determines the sandpile group of the graph. The order of the sandpile group is always equal to the number of spanning trees of the graph. In this sense, the sandpile group is a more subtle invariant. It has been shown that the number of spanning trees of circulant graphs with a given set of generators follows a recursive formula. One can then ask if this structure is reflected in the corresponding sandpile groups as well. Previous results on the sandpile group for C_n(1,2) seem to infer this may be the case.

In this project, we create a database of isomorphism classes and sandpile groups for a large collection of circulant graphs. From our database, we are able to conclude that such nice structure is not always preserved in the sandpile group and hence the sandpile group is a more elusive graph invariant. We further focus our attention to the case C_n(1,3) in order to determine the explicit structure of the sandpile group for this family of graphs.

Combinatorial and Algebraic Properties of Generalized Crown Graphs

Students: Carlos Angrinsoni-Santiago, Angel Burr, Ruben Hurtado

Advisors:  Prof. Luis David Garcia Puente, Natalie Hobson

Abstract: In this project we study the combinatorial and algebraic properties of the generalized crown graphs. Such a graph is a regular bipartite graph defined by two parameters, n the number of vertices in each disjoint set and r the degree of each vertex. We have observed that this family of graphs includes many previously well-studied graphs such as complete bipartite graphs, prism graphs, and Möbius ladder graphs.

In our work, we construct an explicit isomorphism to show that a generalized crown graph is a circulant graph when r is even or the parity of r and n are equal.  Circulant graphs are well studied and our isomorphism provides a portal to understanding such cases. We show, however, that generalized crown graphs in the other cases are indeed not circulant yet they seem to display many nice combinatorial properties similar to circulant graphs. Particularly, the number of spanning trees of a circulant graph follows explicitly defined recursive formulas. Our investigations show this appears to be the case for all generalized crown graphs as well. We study in depth the first unexplored generalized crown graph of this type, for r=5 and n even, in order to make conclusions about combinatorial and algebraic properties.

The Avalanche Polynomial of the Complete Bipartite Graph

Students: Karlie Elliott, Drisana Mosaphir, Maleek Richardson