PARKING FUNCTIONS, SHI ARRANGEMENTS, AND MIXED GRAPHS

Abstract. The Shi arrangement is the set of all hyperplanes in Rn of the form xj − xk = 0 or 1 for 1 ≤ j < k ≤ 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 parking function, i.e., a sequence (x1, x2,..., xn) of positive integers that, when rearranged from smallest to largest, satisfies xk ≤ k. (There is an illustrative reason for the term 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. 1