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
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.