A simple bijection for the regions of the Shi arrangement of hyperplanes (Q1300964)

Suppose \(\Phi\) is a finite crystallographic root system, and \({\mathcal A}_\Phi\) is the Coxeter arrangement of real linear hyperplanes orthogonal to the roots. This paper concerns the combinatorial geometry of certain deformations of \({\mathcal A}_\Phi\), affine arrangements all of whose hyperplanes are parallel to hyperplanes in \({\mathcal A}_\Phi\). In particular, the Shi arrangement \({\mathcal S}_\Phi\) associated to \(\Phi\) is obtained by adjoining to \({\mathcal A}_\Phi\) the hyperplanes given by \(\alpha(x)=1\), where \(\alpha\) ranges over some system of positive roots of \(\Phi\). In case \(\Phi\) has type \(A_{n-1}\), the Shi arrangement \({\mathcal S}_n\) consists of the hyperplanes \(x_i-x_j=0\) and \(x_i-x_j=1\) for \(1\leq i<j\leq n\). Shi showed that the number of connected components of the complement (regions) of \({\mathcal S}_n\) is equal to \((n+1)^{n-1}\). The main purpose of the paper under review is to give a simple bijective proof of this result. The method generalizes to subarrangements of \({\mathcal S}_n\) containing the underlying Coxeter arrangement \({\mathcal A}_n\). The regions of \({\mathcal S}_n\) are counted in two steps. First the authors establish a bijection between regions and marked permutations of \([n]\), as follows. Identify the region \(R\) with the permutation \((a_1,\ldots,a_n)\) such that \(x_{a_1}>\ldots>x_{a_n}\) holds on \(R\). Then attach an arc to this permutation connecting \(a_i\) to \(a_j\) if \(a_i<a_j\) and \(x_{a_i}>x_{a_j}+1\) holds on \(R\). Redundant arcs are omitted. The second step is to associate to such a marked permutation a parking function. A parking function is a function \(f: [n] \to [n]\) for which \(f^{-1}([j])\) has at least \(j\) elements, for each \(j\). Given a marked permutation \((a_1,\ldots,a_n)\), the corresponding parking function sends \(j\) to the position of the leftmost entry of the (possibly trivial) string of arcs in \((a_1,\ldots,a_n)\) containing \(j\). Each coset of \(\langle (1,\ldots, 1)\rangle\) in \({\mathbb Z}_{n+1}^n\) contains precisely one parking function, so there are \((n+1)^{n-1}\) such functions. A bijection between regions of \({\mathcal S}_n\) and parking functions was established by a more complicated argument by \textit{R. P. Pak} and \textit{R. P. Stanley} [Proc. Natl. Acad. Sci. USA 93, No. 6, 2620-2625 (1996; Zbl 0848.05005)]. The present argument is simpler, and also generalizes to give an enumeration of the regions of a type of graphic arrangement \({\mathcal S}_{n,G}\) consisting of the hyperplanes \(x_i-x_j=0\), for \(1\leq i<j\leq n\) and \(x_i-x_j=1\) for \(i<j\) an edge of the graph \(G\). A dual formulation yields a bijective count of the bounded regions of \({\mathcal S}_n\).