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

Advisors: Prof. Luis David Garcia Puente, Jacob Russell-Madonia

Abstract: As an established example of a dynamical system exhibiting self-organized criticality, the dynamics of sandpiles on a graph have garnered much interest. For a given recurrent sandpile on a graph, the simplest dynamics which can be achieved arise from adding one grain of sand to a vertex and stabilizing. The resulting sequence of vertex topplings is called a principal avalanche and understanding the distribution of these principal avalanches is critical for understanding the dynamics of the whole sandpile model. To study this distribution, we can calculate the multivariate avalanche polynomial, which encodes the size, frequency and large scale structure of all principle avalanches on the graph. General formulas for avalanche polynomials have been computed for several families of graphs including complete graphs, wheel graphs, cycles, and trees. We build off of these examples as well as the work of Duke and Le Borgne to calculate a general form of the multivariate avalanche polynomial for the case of complete bipartite graphs.

Bijections Between the Recurrent Sandpiles of an Eulerian Digraph and Its Reverse

Students: Tafari James, Casandra Monroe, Ricardo Rojas-Echenique

Advisors: Prof. Luis David Garcia Puente, Jacob Russell-Madonia

Abstract: An Eulerian digraph is a directed graph where the indegree of each vertex is equal to the outdegree. After designating a single vertex of an Eulerian digraph as a sink, the set of recurrent sandpiles on the graph forms a finite abelian group whose isomorphism class can be calculated based on the Laplacian matrix of the graph. Given a directed graph, we can also construct its reverse graph by reversing the direction of each edge. In general, there is no relationship between the group of recurrent sandpiles of a directed graph and its reverse. However, in the case of Eulerian digraphs we have the salient property that the Laplacian of the reverse graph is equal to the transpose of the Laplacian of the original graph. This allows us to conclude the two groups of recurrent sandpiles are isomorphic. While this isomorphism shows that the number of recurrent sandpiles on an Eulerian digraph and its reverse are equal, the two sets of sandpiles can look quite different. Further, the isomorphism does not provide an explicit bijection between these two sets. We discuss a few possible natural bijections between the recurrent sandpiles on an Eulerian digraph and its reverse, including a map which has the combinatorial property of preserving the number of grains of sand on each sandpile.

MSRI-UP 2016: Research Projects

MSRI-UP 2016: Sandpile Groups