A bijection for Shi arrangement faces (Q2306510)

A hyperplane arrangement \(\mathcal{A}\) is a finite collection of affine hyperplanes in \(\mathbb{R}^{n}\) for some \(n\geq 1\). The regions (or chambers) of an arrangement \(\mathcal{A}\) are the connected components of the complement of hyperplanes in \(\mathcal{A}\). We define the Shi arrangement in \(\mathbb{R}^{n}\) as the collection of hyperplanes \[x_{i} - x_{j} = 0,1 \quad \text{ for } \quad 1 \leq i < j \leq n.\] It is well-known that the Shi arrangement in \(\mathbb{R}^{n}\) has exactly \((n+1)^{n-1}\) regions. The main aim of the paper is to establish an explicit bijection between all Shi faces graded by their dimension. The image of this bijection is a set of certian decorated binary tree. Let us recall that a Cayley tree is a finite connected acyclic graph with vertex set \([n]\) for some \(n\geq 1\). A rooted tree is a tree with a distinguished vertex called its root. A rooted plane tree is a rooted tree with a chosen ordering of the children of each node. Now a binary tree is a rooted plane tree where each vertex has exactly zero of two children. An \([n]\)-decorated binary tree is a binary tree together with the following decorations: \begin{itemize} \item[1)] Each node is labelled with a non-empty subset of \([n]\). Together, the set of labels forms a partition of \([n]\). \item[2)] Internal right edges are of two types: solid and dashed. \end{itemize} Theorem. The faces of the Shi arrangement in \(\mathbb{R}^{n}\) are in bijection with: \begin{itemize} \item[1)] The set of \([n]\)-decorated binary trees such that all right internal edges are descents. The \(k\)-dimensional faces correspond to the trees that have \(k\)-solid right edges. \item[2)] The set of binary trees with \(n\) nodes, labelled by elements \([n]\), such that all right internal edges are descents, together with a subset of marked nodes that have non-leaf left children. The \(k\)-dimensional faces correspond to trees that have \(n-k\) marked nodes. \item[3)] The set of (unrooted) Cayley trees with \(n+1\) vertices, together with a subset of non-leaf vertices, excluding \(n+1\). The \(k\)-dimensional faces correspond to trees that have \(n-k\) marked nodes. \item[4)] The set of functions \(f: [n-1] \rightarrow [n+1]\) together with a subset \(S \subset Im(f) \setminus \{n+1\}\). The \(k\)-dimensional faces correspond to the pairs such that \(|S| = n-k\). \end{itemize} A similar result can be obtained for the \(m\)-Shi arrangement in \(\mathbb{R}^{n}\) given as the collection of hyperplanes \[x_{i}-x_{j} = -m+1, \dots, m-1, m \quad \text{for} \quad 1 \leq i < j \leq n.\] The last section of the paper is devoted to Shi generating functions which allow to obtain the precise values on the number of \(k\)-dimensional faces of the \(m\)-Shi arrangement in \(\mathbb{R}^{n}\).