Bijections between k-Shi arrangement, k-parking functions and k-parking graphs

Abstract: This thesis is about three combinatorial concepts and their relations: One concept is the k-Shi arrangement (also called extended Shi-arrangement), which is the set of all hyperplanes in R^n of the form x_i-x_j=-k+1,-k+2,...,k for 0<i<j<n+1. The second concept is a k-parking function, that is a sequence (x_1,x_2,...,x_n) of positive integers that, when rearranged from smallest to largest, satisfies x_i< 2+k(i-1). In 1996, Pak and Stanley gave a bijection from the regions of the n-dimensional k-Shi arrangement to the k-parking functions of length n, but they could not describe the inverse. Athanasiadis and Linusson found a different bijection in 1999, where they were able to specify explicitly both directions. A new approach was given by Beck et al. (2015) who gave a bijection from the 1-parking functions, respectively the regions of the 1-Shi-Arrangement to a subset of the class of mixed graphs (i.e. graphs that could have directed as well as undirected edges) which they called parking graphs.   In this thesis we define k-parking graphs and use them to extend Beck's bijections to k-Shi arrangements and k-parking functions. This gives an explicit description of the inverse of the Pak-Stanley bijection.