Maths DTP 2020 University of Strathclyde | Threlfall, Daniel: Bevan, David (Principal Investigator) Steingrimsson, Einar (Co-investigator) Threlfall, Daniel (Research Co-investigator); 01-Jan-2020 - 01-Jan-2024
Connecting physics models via permutations: Steingrimsson, Einar (Principal Investigator); 01-Jan-2018 - 30-Jan-2020
The Möbius function of the poset of permutations: Steingrimsson, Einar (Principal Investigator); "Permutations are lists of objects that can be compared pairwise with respect to a given total order, and they can thus always be represented by integers, where the order is the usual order of size. A pattern P in a permutation is a subsequence in the permutation whose elements appear in the same order of size as those in P. For example, the letters 452 in 641523 form an occurrence of the pattern 231.

In recent decades research on various properties of permutations with respect to pattern containment has seen enormous growth, and established a myriad connections to other branches of discrete mathematics and even to physics, biology and theoretical computer science, the last of which has been strongly connected to the field in its modern incarnation.

The focus in this field was for a long time mainly on enumerative results, but studies of structural properties of the poset (partially ordered set) of all finite permutations, ordered by pattern containment, have been growing strong in the last decade or so. These have so far mostly concerned order ideals in this poset, that is, downward closed classes of elements, analogous to minor closed classes of graphs. This poset is the fundamental object in all studies of permutation patterns, since it encompasses all information about containment and avoidance of patterns in permutations.

An inevitable question about any combinatorially defined poset regards the Möbius function of its intervals, that is, sets of permutations containing a given permutation A and contained in another given permutation B. The Möbius function is probably the single most important invariant of a combinatorially defined poset. In addition to the intrinsic interest of determining the Möbius function for this poset, and the likely effect it will have on studies of its topology, there are already results showing that the Möbius function is in some cases closely connected to the number of occurrences of one permutation as a pattern in anothone of the central problems in the area of permutation patterns. Moreover, such a connection is at the core of this proposal, so we expect success here to have an impact on the enumerative studies of permutation patterns.

The study of the Möbius function of the permutation poset has only been going on for a few years, but it is already clear that this poset has a very rich and complicated structure, which reflects the situation with the enumerative problems in the area. Because of this complexity it seems unlikely there will ever be an effective and completely general formula for the Möbius function, but that is of course often the case with interesting mathematical structures. In light of the progress nevertheless made already, this should not be seen as discouraging, but as a challenging invitation.

In all cases where the Möbius function has been determined for a class of intervals there is a common thread to the solutions. These are the so called normal embeddings, special occurrences of a permutation in another, which are very similar, but still different between the cases, and whose number in each of these cases is essentially equal to the Möbius function of the corresponding intervals.

Intriguingly, empirical tests show that yet another variation on the definition of these normal embeddings gives analogous results, that is, that the number of these embeddings equals the Möbius function, in an ``unreasonably'' large proportion of cases, far beyond the realm of where we now understand this phenomenon. This is what we want to understand, since it will almost definitely lead to substantial progress in the research on the Möbius function of this poset, to more systematic results on its general structure, and to tools for further progress."; 29-Jan-2015 - 28-Jan-2018
New combinatorial perspectives on the abelian sandpile model: Steingrimsson, Einar (Principal Investigator) Dukes, Mark (Co-investigator); "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."; 01-Jan-2015 - 31-Jan-2018