Parking functions, Shi arrangements, and mixed graphs

Abstract

The \emph{Shi arrangement} is the set of all hyperplanes in ${\mathbb{R}}^n$ of the form $x_j-x_k=0$ or $1$ for $1\le j<k\le n$. Shi observed in 1986 that the number of regions (i.e., connected components of the complement) of this arrangement is $(n+1{)}^{n-1}$. An unrelated combinatorial concept is that of a \emph{parking function}, i.e., a sequence $(x_1,x_2,...,x_n)$ of positive integers that, when rearranged from smallest to largest, satisfies $x_k\le k$. (There is an illustrative reason for the term \emph{parking function}.) It turns out that the number of parking functions of length $n$ also equals $(n+1{)}^{n-1}$, a result due to Konheim and Weiss from 1966. A natural problem consists of finding a bijection between the $n$-dimensional Shi arragnement and the parking functions of length $n$. Stanley and Pak (1996) and Athanasiadis and Linusson 1999) gave such (quite different) bijections. We will shed new light on the former bijection by taking a scenic route through certain mixed graphs.

12 pages

Cited by in corpus (1)

• A combinatorial model for computing volumes of flow polytopes