Some results concerning tableaux and sandpile models on the complete bipartite graph

Abstract

This thesis presents several new bijections between combinatorial objects that are motivated by two different sandpile models on the complete bipartite graph. These bijections build on recent papers which have shown that these combinatorial objects are in one-toone correspondence with recurrent configurations of the Abelian sandpile model (ASM). Chapter 1 introduces the concepts and background material we use in this thesis. First, we recall some standard definitions and concepts in graph theory. Then we define two models, the first is the Abelian sandpile model (ASM) on the complete bipartite graph and some concepts related to it. Then we introduce the second model which is the stochastic sandpile model (SSM) on a general graph. Chapter 2 gives an overview of the combinatorial objects (EW-tableaux and parallelogram polyominoes) which we study in this thesis. We present and prove a bijection between rectangular EW-tableaux and the set of labelled ribbon parallelogram polyominoes. Chapter 3 introduces the notion of marked EW-tableaux. This allows us to lift the bijection presented in Chapter 2 to a more general level. Furthermore, we introduce and prove a direct bijection between the set of marked EW-tableaux and the set of all labelled parallelogram polyominoes. Chapter 4 gives a characterisation of stochastically recurrent states of the SSM in terms of graph orientations. We use and exploit this characterization to present and prove a connection between rectangular 0/1 tableaux and the stochastically recurrent configurations of the SSM on the complete bipartite graph. Furthermore, we introduce marked rectangular tableaux and explain the connection between the stochastically recurrent configurations and marked rectangular tableaux. Chapter 5 defines the lacking polynomial Lm,n(x) of the SSM on the complete bipartite graph Km,n. We derive exact formulae for the polynomials L_2,n(x) and L_m,2(x) for the graphs K_(2,n) and K_(m,2), respectively. We also investigate whether the sequence of coefficients of the lacking polynomial is log concave. Finally, we prove some upper and lower bounds on the stochastically recurrent states of the SSM on K_(m,n).