New combinatorial perspectives on the abelian sandpile model
Lead Research Organisation:
University of Strathclyde
Department Name: Computer and Information Sciences
Abstract
The abelian sandpile model is a dynamical system that appeared in the late eighties as the vehicle to showcase the concept of self-organised criticality. Roughly speaking, this concept of self-organised criticality means that a system evolves towards critical states that, when nudged, topple and cause avalanches of all distances and time scales to happen throughout.
The prototypical sandpile model is on the planar grid but the preferred mathematical setting is on a graph. At the heart of this model are its toppling dynamics: if a sandpile grows too high then the pile topples and does so by donating grains of sand to its neighbouring piles. These neighbouring piles may themselves topple, and the process continues until the system reaches some stable state.
Although it has been shown to be a poor model for modelling general sandpiles, it has been shown to be a good model for many other and more important things. Examples are plentiful and include forest fires, social media, and even dose response analysis in toxicology. The model also explains the cascading effects that have been observed in these systems. Many rich results emerged when mathematicians began to study the sandpile model on abstract graphs and these studies have also provided links to many other parts of mathematics.
Very recently, the author conducted an in-depth study of the sandpile model on the complete bipartite graph, unearthing new and surprising results. One such result is that recurrent states (similar to critical states) can be uniquely represented as staircase polyominoes, geometric objects that are like dominoes with many cells but which are enclosed between two staircase shapes. This observation led to a new link between polynomials defined on these polyominoes and the subject of diagonal harmonic polynomials in algebraic combinatorics, one of the more fertile hunting grounds for algebraic combinatorialists in the last decade.
Our proposal is to follow the success of this by applying the analysis to more general classes of graphs that are regular or recursive in some way. The purpose is to perform a classification of recurrent states of the sandpile model on these graphs and determine what other combinatorial objects they are linked to. Further to this we will turn the initial work on its head to build a new tool in bijective combinatorics that will relate tilings of general lattices to recurrent states of the sandpile model. This will provide new insights into the theory of lattice tilings, and also unsolved problems in this broad area.
The prototypical sandpile model is on the planar grid but the preferred mathematical setting is on a graph. At the heart of this model are its toppling dynamics: if a sandpile grows too high then the pile topples and does so by donating grains of sand to its neighbouring piles. These neighbouring piles may themselves topple, and the process continues until the system reaches some stable state.
Although it has been shown to be a poor model for modelling general sandpiles, it has been shown to be a good model for many other and more important things. Examples are plentiful and include forest fires, social media, and even dose response analysis in toxicology. The model also explains the cascading effects that have been observed in these systems. Many rich results emerged when mathematicians began to study the sandpile model on abstract graphs and these studies have also provided links to many other parts of mathematics.
Very recently, the author conducted an in-depth study of the sandpile model on the complete bipartite graph, unearthing new and surprising results. One such result is that recurrent states (similar to critical states) can be uniquely represented as staircase polyominoes, geometric objects that are like dominoes with many cells but which are enclosed between two staircase shapes. This observation led to a new link between polynomials defined on these polyominoes and the subject of diagonal harmonic polynomials in algebraic combinatorics, one of the more fertile hunting grounds for algebraic combinatorialists in the last decade.
Our proposal is to follow the success of this by applying the analysis to more general classes of graphs that are regular or recursive in some way. The purpose is to perform a classification of recurrent states of the sandpile model on these graphs and determine what other combinatorial objects they are linked to. Further to this we will turn the initial work on its head to build a new tool in bijective combinatorics that will relate tilings of general lattices to recurrent states of the sandpile model. This will provide new insights into the theory of lattice tilings, and also unsolved problems in this broad area.
Planned Impact
This is fundamental research in graph theory and enumerative combinatorics and
its immediate impact will therefore be on both these communities.
The topic at the heart of this proposal has been shown to be a good model of various real-world systems and our research will therefore have an impact on these applications. The way in which it will have an impact is a body of results that classify the behaviour of sandpile systems whose underlying graph structure possesses some type of recursive or regular pattern.
The sandpile model has been advocated by scientists to be be a good way to model certain types of brain behaviour (Scientific American, April 2014), and this idea has been receiving a lot of attention lately. Three dimensional molecular grids whose vertices are connected to nearest-neighbours in a regular way are an example of what we would consider a recursive structure, and so there is a clear and definite impact that our work has on theoretical models of brain activity.
As we have made clear in the Pathways to Impact statement, we plan to provide societal and economic impact by popularising the easier-to-access part of our work using social media and blogs, particularly those related to national mathematics competitions and recreational mathematics.
Final year projects of computer science students in the university will be used to showcase instances of our work. These projects are presented to industrial visitors on project demonstration day and this will provide both educational impact and industrial impact.
its immediate impact will therefore be on both these communities.
The topic at the heart of this proposal has been shown to be a good model of various real-world systems and our research will therefore have an impact on these applications. The way in which it will have an impact is a body of results that classify the behaviour of sandpile systems whose underlying graph structure possesses some type of recursive or regular pattern.
The sandpile model has been advocated by scientists to be be a good way to model certain types of brain behaviour (Scientific American, April 2014), and this idea has been receiving a lot of attention lately. Three dimensional molecular grids whose vertices are connected to nearest-neighbours in a regular way are an example of what we would consider a recursive structure, and so there is a clear and definite impact that our work has on theoretical models of brain activity.
As we have made clear in the Pathways to Impact statement, we plan to provide societal and economic impact by popularising the easier-to-access part of our work using social media and blogs, particularly those related to national mathematics competitions and recreational mathematics.
Final year projects of computer science students in the university will be used to showcase instances of our work. These projects are presented to industrial visitors on project demonstration day and this will provide both educational impact and industrial impact.
Organisations
Publications
Dukes M
(2016)
Decomposing recurrent states of the abelian sandpile model
in Electronic Notes in Discrete Mathematics
Dukes M
(2019)
Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
in Journal of Combinatorial Theory, Series A
Dukes M
(2019)
Permutation Graphs and the Abelian Sandpile Model, Tiered Trees and Non-Ambiguous Binary Trees
in The Electronic Journal of Combinatorics
Dukes M
(2019)
The Abelian sandpile model on Ferrers graphs - A classification of recurrent configurations
in European Journal of Combinatorics
Dukes M
(2018)
Decomposing Recurrent States of the Abelian Sandpile Model
in Séminaire Lotharingien de Combinatoire
Dukes M.
(2019)
Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
in FPSAC 2019 - 31st International Conference on Formal Power Series and Algebraic Combinatorics
Dukes M.
(2019)
Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
in Seminaire Lotharingien de Combinatoire
Dukes Mark
(2018)
Refining the bijections among ascent sequences, (2+2)-free posets, integer matrices and pattern-avoiding permutations
in arXiv e-prints
Dukes Mark
(2018)
The Abelian sandpile model on Ferrers graphs -- A classification of recurrent configurations
in arXiv e-prints
Dukes Mark
(2018)
Permutation graphs and the Abelian sandpile model, tiered trees and non-ambiguous binary trees
in arXiv e-prints
| Description | Connections of the abelian sandpile model to certain objects, called permutation tableaux, which in turn are intimately linked to another physics model, namely the (Partially) Asymmetric Exclusion Process. This has also led to a series of results on the permutation tableaux in question and their relation to other, well known and much studied objects. March 2019: We have obtained results on the Abelian Sandpile Model (ASM) for two further classes of graphs, each generalizing previous results, although in each case we introduce new methods and connect the ASM to new combinatorial structures, such as tiered trees and complete non-ambiguous trees. |
| Exploitation Route | Our discovery of a very strong connection between different kinds of permutation tableaux is likely to lead to other researchers using these connections to investigate the tableaux we are doing pioneering work on, as there has been much activity in the last decade in research on such tableaux. As this is basic research, this further work is almost certainly going to be done by other academics. March 2019: We have connected the ASM on various classes of graphs to several different, much studied, combinatorial structures. These connections are likely to inspire other researchers with expertise in these areas to apply our findings to produce further results on the structures in question. |
| Sectors | Other |
| Description | A bijection between EW-tableaux and Le-tableaux |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Schools |
| Results and Impact | Conference talk |
| Year(s) Of Engagement Activity | 2017 |
| URL | http://www.mat.univie.ac.at/~slc/ |
| Description | A bijection between EW-tableaux and Le-tableaux |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Schools |
| Results and Impact | Conference talk |
| Year(s) Of Engagement Activity | 2017 |
| URL | http://gt-alea.math.cnrs.fr/alea2017/ |
| Description | Permutations and recurrent states of the Abelian sandpile model on Ferrers graphs |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Schools |
| Results and Impact | Conference talk |
| Year(s) Of Engagement Activity | 2017 |