The sandpile model on the complete split graph, combinatorial necklaces, and tiered parking functions

Mark Dukes

Published 2020-06-14Version 1

In this paper we perform a classification of the recurrent states of the Abelian sandpile model (ASM) on the complete split graph. There are two distinct cases to be considered that depend upon the location of the sink vertex in the complete split graph. We define and use a new toppling order, called the $mascoi$ toppling order, to perform this classification. This mascoi toppling order allows us to give a bijection between the decreasing recurrent states of the ASM on the complete split graph and two classes of tri-coloured combinatorial necklaces. This characterisation of decreasing recurrent states is then used to provide a characterisation of the general recurrent states. We also give a characterisation of the recurrent states in terms of a new type of parking function that we call a $tiered$ $parking$ $function$. These parking functions are characterised by assigning a tier (or colour) to each of the cars, and specifying how many cars of a lower-tier one wishes to have parked before them. We also enumerate the different sets of recurrent configurations studied in this paper, and in doing so derive a formula for the number of spanning trees of the complete split graph. This paper lays the foundations for a study into statistics on these recurrent configurations, as was done in the case of the complete bipartite graph in the author's papers Dukes & Le Borgne (2013) and Aval et al. (2014).