Bijections for faces of the Shi and Catalan arrangements (Q2665971)

Summary: \textit{J.-Y. Shi} [The Kazhdan-Lusztig cells in certain affine Weyl groups. Springer, Cham (1986; Zbl 0582.20030)] derived the famous formula \((n+1)^{n-1}\) for the number of regions of the Shi arrangement, a hyperplane arrangement in \({R}^n\). There are at least two different bijective explanations of this formula, one by Pak and Stanley, another by \textit{C. A. Athanasiadis} and \textit{S. Linusson} [Discrete Math. 204, No. 1--3, 27--39 (1999; Zbl 0959.52019)]. \textit{C. A. Athanasiadis} [Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials. Cambridge, Massachusetts: Massachusetts Institute of Technology (PhD Thesis) (1996)] used the finite field method to derive a formula for the number of \(k\)-dimensional faces of the Shi arrangement for any \(k\). Until now, the formula of Athanasiadis did not have a bijective explanation. In this paper, we extend a bijection for regions defined by \textit{O. Bernardi} [Adv. Math. 335, 466--518 (2018; Zbl 1394.05056)] to obtain a bijection between the \(k\)-dimensional faces of the Shi arrangement for any \(k\) and a set of decorated binary trees. Furthermore, we show how these trees can be converted to a simple set of functions of the form \(f: [n-1] \to [n+1]\) together with a marked subset of \(\text{Im}(f)\). This correspondence gives the first bijective proof of the formula of Athanasiadis. In the process, we also obtain a bijection and counting formula for the faces of the Catalan arrangement. All of our results generalize to both extended arrangements.