\documentclass[submission]{FPSAC2019}

\articlenumber{47}
\addbibresource{47.bib}

\title{A bijection for Shi arrangement faces}
\author{Duncan Levear\thanks{\href{mailto:dlevear@brandeis.edu}{dlevear@brandeis.edu}}}
\address{Department of Mathematics, Brandeis University, Waltham, Massachusetts, USA}
\received{\today}
\keywords{Shi arrangement, hyperplane arrangements, faces, bijection}

\abstract{The Shi arrangement of hyperplanes in $\mathbb{R}^n$ is known to have $(n+1)^{n-1}$ regions. This remarkable formula was first derived algebraically in 1986 by Shi, and has since been explained bijectively through either parking functions or Cayley trees. Although the lower-dimensional faces have been counted by a finite field method, no bijective correspondence has been established. In this paper, we extend a bijection for regions defined by Bernardi to obtain a correspondence for all Shi faces graded by their dimension. The image of the bijection is a set of decorated binary trees, which can further be converted to a simple set of functions $f: [n-1] \to [n+1]$ known as Pr\"ufer sequences. In the process, we also obtain a correspondence for the faces of the Catalan arrangement, and the results generalize to both extended arrangements. }
%\usepackage{amsmath, amssymb}
\usepackage{tikz}
\usepackage{mathrsfs} %\mathscr command
\usepackage{xcolor}
\usepackage{enumitem}
\usepackage{subcaption}
%\usepackage[backend=bibtex]{biblatex}
%\usepackage{biblatex}
%\addbibresource{refs.bib}

\setenumerate{label=(\arabic*)}
\DeclareMathOperator{\given}{\; \vert \;}
\DeclareMathOperator{\biggiven}{\; \Big \vert \;}
%\numberwithin{equation}{section}

%\usepackage{hyperref}  
\definecolor{robin}{HTML}{158c89}
\definecolor{pinkrobin}{HTML}{8c1554}
\definecolor{redrobin}{HTML}{8c1518}
\definecolor{greenrobin}{HTML}{158c4e}
\definecolor{bluerobin}{HTML}{15548c}

%\usepackage[sort,nocompress]{cite}

%\newcommand{\eref}[1]{\hyperref[#1]{(\ref{#1})}}
\newcommand{\secref}[1]{{\hyperref[#1]{Section \ref{#1}}}}
\newcommand{\subsecref}[1]{{\hyperref[#1]{Subsection \ref{#1}}}}
\newcommand{\thmref}[1]{{\hyperref[#1]{Theorem \ref{#1}}}}
\newcommand{\lemref}[1]{{\hyperref[#1]{Lemma \ref{#1}}}}
\newcommand{\corref}[1]{{\hyperref[#1]{Corollary \ref{#1}}}}
\newcommand{\figref}[1]{{\hyperref[#1]{Figure \ref{#1}}}}
\newcommand{\defref}[1]{{\hyperref[#1]{Definition \ref{#1}}}}

\newcommand{\nallem}{\ensuremath _n^{(m)}}
\newcommand{\bracketbox}[2]{\left\{ \parbox{#1}{\centering #2}\right\}}
\newcommand{\todonote}[1]{\textcolor{redrobin}{\bf \boxed{NOTE}: #1}\PackageWarning{TODO:}{#1!}}
\newcommand{\todo}[1]{\textcolor{greenrobin}{\bf \boxed{TODO} #1}\PackageWarning{TODO:}{#1!}}


\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{corollary}[definition]{Corollary}
\newtheorem{proposition}[definition]{Proposition}
\theoremstyle{remark}
\newtheorem{remark}[definition]{Remark}

\begin{document}
\maketitle

\section{Introduction} \label{sec-introduction}

Much is known about the enumeration of the regions of hyperplane arrangements. Basic references are \cite{Orlik:hyperplane-arrangements} and \cite{Stanley:hyperplane-arrangements}. Less is known about the lower-dimensional faces, which are the focus of this paper. In particular, we show that the faces of the Catalan and Shi arrangements are in bijection with certain decorated binary trees. We begin with some basic definitions before stating the result.

\subsection{Hyperplane Arrangements}
A \emph{hyperplane arrangement} is a finite collection of affine hyperplanes in $\mathbb{R}^n$ for some $n \ge 1$. The \emph{regions} of an arrangement are the connected components of the complement of its hyperplanes. The \emph{braid arrangement} in $\mathbb{R}^n$ is the collection of hyperplanes \begin{align}x_i - x_j = 0, \; \text{for} \; 1 \le i < j \le n. \end{align} It is not hard to see that  there are $n!$ regions.
The \emph{Shi arrangement} in $\mathbb{R}^n$ is the collection of hyperplanes \begin{align}x_i - x_j = 0,1, \; \text{for} \; 1 \le i < j \le n. \end{align} It is known that there are $(n+1)^{n-1}$ regions, which was first derived algebraically by Shi \cite{Shi:nb-regions} in 1986, and later re-proved bijectively \cite{ Athanasiadis:bijection-Shi, Bernardi:hyperplane-trees, Stanley:hyperplane-interval-orders-overview}. 
The \emph{Catalan arrangement} in $\mathbb{R}^n$ is the collection of hyperplanes
\begin{align}x_i - x_j = -1,0,1, \; \text{for} \; 1 \le i < j \le n. \end{align}
There are $n! \text{Cat}_n$ regions, where $\text{Cat}_n = \frac{(2n)!}{n!(n+1)!}$ is the $n$th Catalan number. This result first appeared in \cite{Stanley:hyperplane-interval-orders-overview}, where it is obtained by defining a bijection from the regions to labelled semiorders. All three arrangements are shown in \figref{fig-arrangements} with $n=3$. 

\begin{figure}[t]
\centering
\begin{tikzpicture}

\begin{scope}[scale=.5]
\node at (0,4.3) {\bf Braid};
\draw[-,ultra thick] (-3.0,0) -- (3.0,0) node[above]{\tiny $x_1-x_3=0$};
%\draw->,black,thick] (-3.0,1) -- (3.0,1) node[above]{};
\draw[-,rotate=60,ultra thick] (-3.3,0) -- (3.3,0) node[below,rotate=60]{\tiny $x_1-x_2=0$};
%\draw->,black,rotate around={(60:(0,0)},thick] (-3.3,1) -- (3.3,1) node[right,rotate=0]{};
\draw[-,rotate=-60, ultra thick] (-3.3,0) -- (3.3,0) node[above,rotate=-60]{\tiny $x_2-x_3=0$};
%\draw[<->,black,rotate around={(-60:(0,0)}, thick] (-3.3,1) -- (3.3,1) node[above,rotate=-60]{};
\end{scope}

\begin{scope}[scale=.5,shift={(10,0)}]
\node at (0,4.3) {\bf Shi};
\draw[-,ultra thick] (-3.0,0) -- (3.0,0) node[above]{};
\draw[-,black,thick] (-3.0,1) -- (3.0,1) node[above]{\tiny $x_1-x_3=1$};
\draw[-,rotate=60,ultra thick] (-3.3,0) -- (3.3,0) node[below,rotate=60]{};
\draw[-,black,rotate around={(60:(0,0)},thick] (-3.3,1) -- (3.3,1) node[below,rotate=60]{\tiny $x_1-x_2=1$};
\draw[-,rotate=-60, ultra thick] (-3.3,0) -- (3.3,0) node[above,rotate=-60]{};
\draw[-,black,rotate around={(-60:(0,0)}, thick] (-3.3,1) -- (3.3,1) node[above,rotate=-60]{\tiny $x_2-x_3=1$};
\end{scope}

\begin{scope}[scale=.5,shift={(20,0)}]
\node at (0,4.3) {\bf Catalan};
\draw[-,ultra thick] (-3.0,0) -- (3.0,0) node[above]{};
\draw[-,black,thick] (-3.0,1) -- (3.0,1) node[above]{};
\draw[-,black,thick] (-3.0,-1) -- (3.0,-1) node[above]{\tiny $x_1-x_3=-1$};
\draw[-,rotate=60,ultra thick] (-3.3,0) -- (3.3,0) node[below,rotate=60]{};
\draw[-,black,rotate around={(60:(0,0)},thick] (-3.3,1) -- (3.3,1) node[right,rotate=0]{};
\draw[-,black,rotate around={(60:(0,0)},thick] (-3.3,-1) -- (3.3,-1) node[below,rotate=60]{\tiny \; \; $x_1-x_2=-1$};
\draw[-,rotate=-60, ultra thick] (-3.3,0) -- (3.3,0) node[above,rotate=-60]{};
\draw[-,black,rotate around={(-60:(0,0)}, thick] (-3.3,1) -- (3.3,1) node[above,rotate=-60]{};
\draw[-,black,rotate around={(-60:(0,0)}, thick] (-3.3,-1) -- (3.3,-1) node[above,rotate=-60]{\tiny $x_2-x_3=-1$};
\end{scope}
\end{tikzpicture}

\caption[Arrangements]{The braid, Shi, and Catalan arrangements\footnotemark{} in $\mathbb{R}^3$.}
\label{fig-arrangements}
\end{figure}
\footnotetext{Technically speaking, \figref{fig-arrangements} displays the induced hyperplane arrangements in the vector space $\{(x_1,x_2,x_3) \in \mathbb{R}^3 \given \sum x_i =0\} \cong \mathbb{R}^2$. Such induced arrangements are referred to as \emph{essentializations}.}

\subsection{Faces}
A \emph{face} of a hyperplane arrangement is the solution set to a (non-void) system of equalities and inequalities, one for each hyperplane.  The \emph{dimension} of a face is the dimension of its affine span. The regions are the highest-dimensional faces. Viewing the regions as polyhedra, the faces of the arrangement are the faces of these polyhedra. We refer to the faces of the braid (resp. Shi, Catalan) arrangement as \emph{braid} (resp. \emph{Shi}, \emph{Catalan}) \emph{faces}. 

An \emph{ordered set partition} of a set $X$ is an ordered tuple of disjoint nonempty subsets whose union equals $X$. Here and throughout we use the notation $[n]$ for the set $\{1,2,\dots,n\}$. The braid faces are in bijection with ordered set partitions of $[n]$, giving the counting formula $k! S(n,k)$ for faces of dimension $k = 1,2,\dots,n$ (see \cite[Exercise 2.10]{Stanley:hyperplane-arrangements}), where $S(n,k)$ are the Stirling numbers of the second kind.

It is not so easy to count the faces of the Shi and Catalan arrangements. In 1996, Athanasiadis devised an innovative extension to the finite field method, and thereby obtained counting formulae for the number of faces. One of his results is the following: 
\begin{theorem}[{\cite[Thm 8.2.1]{Athanasiadis:PhD}}] \label{thm-ath-shi}
The number of $k$-dimensional faces of the Shi arrangement in $\mathbb{R}^n$ is 
\begin{align} \label{eq-athanasiadis-shi-counting}
\binom{n}{k} \sum_{i=0}^{n-k} \binom{n-k}{i} (-1)^i (n-i+1)^{n-1}, \; \; 1 \le k \le n.
\end{align}
\end{theorem}
Athanasiadis remarked that, by inclusion-exclusion, the formula \eqref{eq-athanasiadis-shi-counting} enumerates the set
\begin{align} \label{eq-athanasiadis-shi-faces}
    \left\{(f,S) \given \begin{array}{l} f : [n-1] \to [n+1] \\ S \subset \text{Im}(f) \smallsetminus \{n+1\} \\ |S| = n-k  \end{array} \right \},
\end{align}
where $\text{Im}(f)$ denotes the image of $f$. He asked if a bijective explanation could be given; indeed, one of the main results of this paper is such an explanation.

\subsection{Main Result}
First, we obtain a bijection between the faces of the Catalan arrangement and a set of decorated binary trees. Second, we modify the bijection to give a bijection between the faces of the Shi arrangement and a simple subset of these trees (namely, those that decrease to the right). See \figref{fig-shi-example} for some examples. Our bijection (and overall method) is an extension of an approach for regions due to Bernardi \cite{Bernardi:hyperplane-trees}. Thirdly, we are able to obtain the set of functions \eqref{eq-athanasiadis-shi-faces} by applying some simple bijective manipulations to the trees corresponding to the Shi faces. 

Our results extend to a general family of hyperplane arrangements, indexed by an integer parameter $m>0$. The \emph{$m$-Catalan arrangement} in $\mathbb{R}^n$ is the collection of hyperplanes 
\begin{align}
    x_i - x_j = -m,-m+1,\dots,m-1,m, \; \text{for} \; 1 \le i < j \le n.
\end{align}
The \emph{$m$-Shi arrangement} in $\mathbb{R}^n$ is the collection of hyperplanes 
\begin{align}
    x_i - x_j = -m+1,\dots,m-1,m, \; \text{for} \; 1 \le i < j \le n.
\end{align}
These arrangements are known as the \emph{extended arrangements}, and the classical arrangements correspond to the case $m=1$. For any $m>0$, we obtain an explicit bijection from the faces of these arrangements to certain decorated $(m+1)$-ary trees. In the $m$-Shi case, we also obtain a set of functions analogous to those in \eqref{eq-athanasiadis-shi-faces}. The counting formulae were already found by Athanasiadis, but the bijective correspondences are new.

\begin{figure}[t]
    \centering
    \parbox[c]{.50\textwidth}{\includegraphics[width=.50\textwidth]{shi_trees_4cols}}
    \parbox[c]{.40\textwidth}{\includegraphics[width=.40\textwidth]{shi_chart3}}
    \caption{The correspondence between two-dimensional faces of the Shi arrangement in $\mathbb{R}^3$ and $[3]$-decorated binary trees with exactly one solid right edge such that all right internal edges are descents.}
    \label{fig-shi-example}
\end{figure}
\subsection{Outline}
In \secref{sec-catalan-bijection} we define the bijection between the Catalan faces and a simple set of trees. In \secref{sec-shi-faces} we adjust the bijection to obtain one between the Shi faces and a simple subset of the trees. In \secref{sec-bijection-to-functions} we explain the additional steps to obtain the set of functions \eqref{eq-athanasiadis-shi-faces}. In \secref{sec-extended-arrangements} we state the general results for extended arrangements. Enumerative consequences (generating functions, counting formulae) are stated in \secref{sec-enumerative-consequences} for a general $m$.
\section{From Catalan Faces To Trees} \label{sec-catalan-bijection} 
In this section we define the map between faces of the Catalan arrangement and the appropriate set of trees. 
\subsection{Decorated Trees}
    A \emph{Cayley tree} (or just \emph{tree}) is a finite connected acyclic graph, with vertex set $[n]$ for some $n \ge 1$. A \emph{rooted tree} is a tree with a distinguished vertex called its root. We adopt the usual vocabulary of parents, children, leaves (vertices with no children), and nodes (vertices with some children).  A \emph{rooted plane tree} is a rooted tree with a chosen ordering of the children of each node. A \emph{binary tree} is a rooted plane tree where each vertex has exactly zero or two children. For binary trees, the first child of a node is called its \emph{left child}, and the second is called its \emph{right child}. The edge connecting a parent to its left (resp. right) child is called a \emph{left} (resp. \emph{right}) \emph{edge}. An \emph{internal edge} is one between two nodes. 

The next definition furnishes the domain for our bijection to Catalan faces. 
\begin{definition}
An \emph{$[n]$-decorated binary tree} is a binary tree together with the following decorations: 
\begin{itemize}
    \item Each node is labelled with a non-empty subset of $[n]$. Together, the set of labels forms a partition of $[n]$.
    \item Internal right edges are of two types: solid and dashed.
\end{itemize}
\end{definition}
Note that an $[n]$-decorated binary tree has anywhere up to $n$ nodes. The main result of this section is a bijection from the set of $[n]$-decorated binary trees to the faces of the Catalan arrangement in $\mathbb{R}^n$. 

\subsection{The Bijection}
Now we define the map: 
\newcommand{\catmap}{\ensuremath \Phi_{\text{Cat}_n}}
\begin{align}
\catmap: \{ \text{$[n]$-decorated binary trees} \} \to \{ \text{Catalan faces in $\mathbb{R}^n$} \}.
\end{align}

The hyperplanes of the Catalan arrangement are all of the form $x_i = x_j$ or $x_i = x_j+1$ for some $i,j \in [n]$. Therefore, to specify an element of the image, one needs to specify all of the equalities and inequalities between $x_i,x_j,x_i+1,x_j+1$ for all $i,j \in [n]$. These are obtained by reading through the tree in a certain order. If $v$ is any vertex in a binary tree, let $p(v)$ denote the word in the alphabet $\{L,R\}$ obtained by traversing the unique path from the root to $v$ ($L$ means left edge, $R$ means right edge). Let $p_R(v)$ denote the number of right edges used. 
\begin{definition}
Let $T$ be a binary tree and let $v,w$ be two vertices. We say $v \prec_T w$ if either:
\begin{itemize}
    \item $p_R(v) < p_R(w)$ or
    \item $p_R(v) = p_R(w)$ and $p(v) <_{\text{lex}} p(w)$, where $<_{\text{lex}}$ is the lexicographic ordering on words with $R < L$. 
\end{itemize}
\end{definition}
\begin{figure}[t]
    \centering
    \begin{minipage}[c]{0.55\textwidth}
      \caption{The $\prec_T$ order on the vertices of a binary tree. The label of each vertex is its place in the total order $\prec_T$.}
      \label{fig-torder}
    \end{minipage}
    \begin{minipage}[c]{0.35\textwidth}
      \begin{tikzpicture}[scale=0.5, every node/.style={scale=0.5}]
        \draw (0,0) node(v1)[circle,draw] {$1$};
        \draw (-2,2) node(v2)[circle,draw] {$2$};
        \draw (-3,3) node(v3)[circle,draw] {$3$};
        \draw (-4,4) node(v4)[circle,draw] {$4$};
        \draw (-1,3) node(v7)[circle,draw] {$7$};
        \draw (-2,4) node(v8)[circle,draw] {$8$};
        \draw (-3,5) node(v9)[circle,draw] {$9$};
        \draw (-1,5) node(v12)[circle,draw] {$12$};
        
        \draw (1,1) node(v5)[circle,draw] {$5$};
        \draw (0,2) node(v6)[circle,draw] {$6$};
        \draw (2,2) node(v10)[circle,draw] {$10$};
        \draw (1,3) node(v11)[circle,draw] {$11$};
        \draw (3,3) node(v13)[circle,draw] {$13$};
        \draw (v1) -- (v2);
        \draw (v2) -- (v7);
        \draw (v2) -- (v3);
        \draw (v3) -- (v4);
        \draw (v3) -- (v8);
        \draw (v8) -- (v9);
        \draw (v8) -- (v12);
        \draw (v1) -- (v5);
        \draw (v5) -- (v6);
        \draw (v5) -- (v10);
        \draw (v10) -- (v11);
        \draw (v10) -- (v13);
      \end{tikzpicture}
    \end{minipage} 
\end{figure}

\figref{fig-torder} shows the $\prec_T$ order for an (unlabelled) binary tree.  Let $T$ be a given $[n]$-decorated binary tree, and for $i \in [n]$ let 
\begin{align} 
\label{eq-nt-def} N_T(i) := \text{the node whose label contains $i$}. 
\end{align}
We now define the face $\catmap(T)$. Let $i,j \in [n]$ be given, and follow the decision tree in \figref{fig-decision-tree} to obtain the relevant inequalities or equalities between $x_i,x_j,x_i+1,$ and $x_j+1$. We define $\catmap(T)$ as the face arising from all of these inequalities or equalities. 
\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[xscale=0.7, every node/.style={scale=0.7}]
\draw (0,0) node{\small $N_i \prec_T N_j$?};

\draw[shorten >= 15pt, shorten <= 15pt] (0,0) -- (-3,-1) node{\small $N_i = N_j$?} node[midway,left]{\small \bf no};
\draw[shorten >= 5pt, shorten <= 5pt] (-3,-1) -- (-4,-2) node[below]{\small $\begin{array}{c} \text{swap}(i,j) \\ \text{restart} \end{array}$} node[midway,left]{\small \bf no};
\draw[shorten >= 5pt, shorten <= 5pt] (-3,-1) -- (-2,-2) node[below]{\small $x_i = x_j$} node[midway,right]{\small \bf yes};

\draw[shorten >= 15pt, shorten <= 15pt] (0,0) -- (4,-1) node{\small is $N_j$ the dashed right-child of $N_i$?} node[midway,right]{\small \bf yes};
\draw[shorten >= 2pt, shorten <= 11pt] (4,-1) -- (6.5,-2) node[below]{\small $\begin{array}{c} x_i < x_j \\ x_i+1=x_j \end{array}$} node[midway,right]{\small \bf yes};
\draw[shorten >= 2pt, shorten <= 8pt] (4,-1) -- (2.0,-2) node[below]{\small is $N_j \prec_T$ the right-child of $N_i$?} node[midway,left]{\small \bf no};

\draw[shorten >= 10pt, shorten <= 17pt] (1.5,-2) -- (3.0,-3.3) node{\small $\begin{array}{c} x_i < x_j \\ x_i+1 > x_j \end{array}$} node[midway,right]{\small \bf yes};
\draw[shorten >= 10pt, shorten <= 17pt] (1.5,-2) -- (0.0,-3.3) node{\small $\begin{array}{c} x_i < x_j \\ x_i+1 < x_j \end{array}$} node[midway,left]{\small \bf no};
\end{tikzpicture}

\caption{Definition of $\catmap$. We write $N_i$ for $N_T(i)$  and $N_j$ for $N_T(j)$.}
\label{fig-decision-tree}
\end{center}
\end{figure}
\begin{theorem} \label{thm-cat-bijection}
The map $\catmap$ is a bijection between $[n]$-decorated binary trees and the faces of the Catalan arrangement in $\mathbb{R}^n$. Furthermore, the $k$-dimensional faces correspond to those trees with $k$ solid right edges.
\end{theorem}

We can prove \thmref{thm-cat-bijection} by explicitly constructing an inverse (omitted). The statement about $k$-dimensional faces is a straightforward consequence of the definition. We explore the implications of \thmref{thm-cat-bijection} in the next sections.
\section{From Shi Faces To Trees} \label{sec-shi-faces}
 In this section, we obtain an analogue of \thmref{thm-cat-bijection} for the Shi arrangement. We say an internal edge between nodes with labels $S,T$ is a \emph{descent} if $\max S > \min T$.
 \begin{definition} \label{def-trees-shitype}
 An $[n]$-decorated binary tree is of \emph{Shi type} if all its right internal edges are descents. 
 \end{definition}
 
 Our main result is that $[n]$-decorated trees of Shi type are in bijection with Shi faces in $\mathbb{R}^n$.
 
 \subsection{The Bijection} Now we define the map:
 \newcommand{\shimap}{\ensuremath \Phi_{\text{Shi}_n}}
 \begin{align}
     \shimap : \{ \text{$[n]$-decorated binary trees of Shi type}\} \to \{\text{Shi faces in $\mathbb{R}^n$}\}.
 \end{align}
 The hyperplanes of the Shi arrangement are of the form $x_i = x_j$ or $x_i = x_j+1$ but only for $1 \le i < j \le n$. If $T$ is an $[n]$-decorated binary tree of Shi type, and $1 \le i < j \le n$, we specify the relevant equalities and inequalities as follows: 
 
\begin{itemize}
    \item If $N_T(i) = N_T(j)$ then $x_i = x_j$.
    \item Else if $N_T(i) \prec_T N_T(j)$ then $x_i < x_j$, (and so $x_i < x_j+1$ and we are done)
    \item Else, then $N_T(j) \prec_T N_T(i)$ and $x_j < x_i$, and
    \begin{itemize}
        \item If $N_T(i)$ is a dashed right-child of $N_T(j)$ then $x_i=x_j+1$.
        \item Else if $N_T(i) \prec_T$ the right child of $N_T(j)$, then $x_i < x_j+1$.
        \item Else $x_i > x_j+1$.
    \end{itemize}
\end{itemize}

We define $\shimap (T)$ to be the face arising from all of these inequalities or equalities. Equivalently, $\shimap(T)$ is the unique Shi face to which the face $\catmap(T)$ belongs.

\begin{theorem} \label{thm-shi-bijection}
The map $\shimap$ is a bijection between $[n]$-decorated binary trees of Shi type and the faces of the Shi arrangement in $\mathbb{R}^n$. Furthermore, the $k$-dimensional faces correspond to those trees with $k$ solid right edges. 
\end{theorem}

The proof of \thmref{thm-shi-bijection} relies heavily on properties of $\catmap$. We briefly explain the general ideas. Every face of the Catalan arrangement in $\mathbb{R}^n$ belongs to a unique face of the corresponding Shi arrangement, so we say two Catalan faces $f_1,f_2$ are \emph{Shi-equivalent} if they belong to the same face of the Shi arrangement. The Shi faces are naturally in bijection with these Shi equivalence classes. Then the crucial fact is the following:
\begin{lemma} \label{lem-shitype}
Each Shi equivalence class contains a unique face $f$ such that $\catmap^{-1}(f)$ is an $[n]$-decorated tree of Shi type. Furthermore, all $[n]$-decorated trees of Shi type arise in this way.
\end{lemma}

The idea behind \lemref{lem-shitype} is to first prove that $\catmap$ respects the ``local structure'' of a face, and then use an inductive argument to show that only one face has the ``local structure of Shi type.'' It follows that there is a bijection between faces of the Shi arrangement in $\mathbb{R}^n$ and $[n]$-decorated trees of Shi type. The map $\shimap$ gives the explicit correspondence. 
\section{From Shi Faces To Functions} \label{sec-bijection-to-functions}
The original counting formula of Athanasiadis suggests that Shi faces correspond bijectively to certain functions (see \eqref{eq-athanasiadis-shi-faces}). In this section, we explain how to obtain these functions from our decorated trees. 
\begin{theorem} \label{thm-shi-everything}
The faces of the Shi arrangement in $\mathbb{R}^n$ are in bijection with:
\begin{enumerate}
    \item 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 The set of binary trees with $n$ nodes, labelled by elements of $[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 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 The set of functions $f : [n-1] \to [n+1]$, together with a subset $S \subset \text{Im}(f) \smallsetminus \{n+1\}$. The $k$-dimensional faces correspond to the pairs such that $|S| = n-k$.
\end{enumerate}
\end{theorem}

\newcommand{\markcolor}[0]{red!45}

\begin{figure}
    \centering
    \parbox[c]{.20 \textwidth}{
    %% [n]-DECORATED BINARY TREE
    \begin{tikzpicture}[scale=0.7, every node/.style={scale=0.6}]
      \draw (0,0) node[circle,draw](v4) {$4$};
  \draw (-1,1) node[circle,draw](v6) {$6,8$};
  \draw (-.5,2.2) node[circle,draw](v5) {$5$};
  \draw (1,1) node[circle,draw](v3) {$3$};
  \draw (.5,2.2) node[circle,draw](v9) {$9$};
  \draw (.8,3) node[circle,draw](v7) {$7$};
  \draw (2,2.2) node[circle,draw](v1) {$1,2$};
  
  \draw (v4) -- (v6);
  \draw[dashed,thick,\markcolor] (v6) -- (v5);
  \draw (v4) -- (v3);
  \draw (v3) -- (v9);
  \draw[dashed,thick,\markcolor] (v3) -- (v1);
  
  \filldraw (v6) -- (-1.75,2) circle (2pt);
  \filldraw (v5) -- (-.8,3) circle (2pt);
  \filldraw (v5) -- (-.2,3) circle (2pt);
  \filldraw (v9) -- (.2,3) circle (2pt);
  \draw (v9) -- (v7);
  \filldraw (v7) -- (.6,3.5) circle (2pt);
  \filldraw (v7) -- (1,3.5) circle (2pt);
  
  \filldraw (v1) -- (1.5,3) circle (2pt);
  \filldraw (v1) -- (2.5,3) circle (2pt);
    \end{tikzpicture}
    }
    {\large $\rightarrow$}
    \parbox[c]{.20 \textwidth}{
    %% BINARY TREE
    \begin{tikzpicture}[scale=0.5, every node/.style={scale=0.6}]
      \draw (0,0) node[circle,draw](v4) {$4$};
  \draw (-1,1.75) node[circle,draw,fill=\markcolor](v6) {$6$};
  \draw (-1.75,3.5) node[circle,draw,fill=\markcolor](v8) {$8$};
  \draw (-2.5,5) node[circle,draw](v5) {$5$};
  \draw (1,1.75) node[circle,draw,fill=\markcolor](v3) {$3$};
  \draw (0,3.5) node[circle,draw](v9) {$9$};
  \draw (.5,5) node[circle,draw](v7) {$7$};
  
  \draw (2,3.5) node[circle,draw,fill=\markcolor](v1) {$1$};
  \draw (1.5,5) node[circle,draw](v2) {$2$};
  
  \draw (v4) -- (v6);
  \draw (v6) -- (v8);
  \draw (v8) -- (v5);
  \draw (v4) -- (v3);
  \draw (v3) -- (v9);
  \draw (v3) -- (v1);
  \draw (v1) -- (v2);
  
  \filldraw (v5) -- (-3.0,6) circle (3pt);
  \filldraw (v5) -- (-2.0,6) circle (3pt);
  
  \filldraw (v8) -- (-1.25,4.5) circle (3pt);
  
  \filldraw (v6) -- (-0.5,2.75) circle (3pt);
  
  \draw (v9) -- (v7);
  \filldraw (v9) -- (-0.5,4.5) circle (3pt);
  \filldraw (v7) -- (0.75,6) circle (3pt);
  \filldraw (v7) -- (0.25,6) circle (3pt);
  
  \filldraw (v2) -- (1.25,6) circle (3pt);
  \filldraw (v2) -- (1.75,6) circle (3pt);
  
  \filldraw (v1) -- (2.5,4.5) circle (3pt);
    \end{tikzpicture}
    }
    {\large $\rightarrow$}
    \parbox[c]{.20 \textwidth}{ 
    %% CAYLEY TREE
    \begin{tikzpicture}[scale=0.7, every node/.style={scale=0.6}, rotate=90]
      \draw (0,0) node[circle,draw](v10) {$10$};
  \draw (-1,1) node[circle,draw,fill=\markcolor](v3) {$3$};
  \draw (-1,-1) node[circle,draw,fill=\markcolor](v1) {$1$};
  \draw (-.7,2.2) node[circle,draw](v9) {$9$};
  \draw (-2.1,.5) node[circle,draw](v7) {$7$};
  \draw (-2,-2) node[circle,draw](v2) {$2$};
  \draw (1,0) node[circle,draw](v4) {$4$};
  \draw (2,0) node[circle,draw,fill=\markcolor](v6) {$6$};
  \draw (3,0) node[circle,draw,fill=\markcolor](v8) {$8$};
  \draw (4,0) node[circle,draw](v5) {$5$};
  
  \draw (v10) -- (v3);
  \draw (v3) -- (v7);
  \draw (v3) -- (v9);
  \draw (v10) -- (v1);
  \draw (v1) -- (v2);
  \draw (v10) -- (v4);
  \draw (v4) -- (v6);
  \draw (v6) -- (v8);
  \draw (v8) -- (v5);
    \end{tikzpicture}}
    {\large $\rightarrow$}
    \parbox[c]{.20 \textwidth}{
    %% PRUFER CODE
      \begin{tikzpicture}
    \draw[white] (0,0);
    \begin{scope}[shift={(1.5,0)},scale=.7,every node/.style={scale=0.7},rotate=0]
       \node[draw,fill=\markcolor,minimum size=20pt] at (0,0) {$1$};
       \node[draw, minimum size=20pt] at (0,-20pt) {$10$};
       \node[draw,fill=\markcolor,minimum size=20pt] at (0,-40pt) {$8$};
       \node[draw,fill=\markcolor,minimum size=20pt] at (0,-60pt) {$3$};
       \node[draw,fill=\markcolor, minimum size=20pt] at (0,-80pt) {$6$};
       \node[draw,minimum size=20pt] at (0,-100pt) {$4$};
       \node[draw,fill=white, minimum size=20pt] at (0,-120pt) {$10$};
       \node[draw,fill=\markcolor, minimum size=20pt] at (0,-140pt) {$3$};
       
       \node at (-25pt,0) {$1 \mapsto$};
       \node at (-25pt,-20pt) {$2 \mapsto$};
       \node at (-25pt,-40pt) {$3 \mapsto$};
       \node at (-25pt,-60pt) {$4 \mapsto$};
       \node at (-25pt,-80pt) {$5 \mapsto$};
       \node at (-25pt,-100pt) {$6 \mapsto$};
       \node at (-25pt,-120pt) {$7 \mapsto$};
       \node at (-25pt,-140pt) {$8 \mapsto$};
    \end{scope}
  \end{tikzpicture}
    %$(\boxed{1},9,\boxed{8},\boxed{3},9,\boxed{6},4)$
    }
    \caption{The three bijections in \thmref{thm-shi-everything}. In this example, $n=9$ and $k=5$.}
    \label{fig-shi-everything}
\end{figure}

Item (1) is just \thmref{thm-shi-bijection}. The rest are obtained sequentially. One example of the chain of correspondences is shown in \figref{fig-shi-everything}. We start by describing a bijection from (1) to (2). Let an $[n]$-decorated binary tree be given. There are two steps:
\begin{enumerate}[label=(\roman*)]
\begin{minipage}[c]{.5\textwidth} \item We apply a local operation to every node. Let $v$ be a node, with left child $L_v$, right-child $R_v$, and with label $S = \{s_1,s_2,\dots,s_p\}$ with $s_1 < s_2 < \dots < s_p$. Expand $v$ according to the diagram to the right. If the edge from $v$ to $R_v$ is dashed, then the corresponding edge from $s_p$ to $R_v$ remains dashed.
\end{minipage}
\begin{minipage}[c]{.5\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.50, every node/.style={scale=0.60}]
\draw (-9,1.5) node(v)[circle,draw] {$S$};
\draw (-10,2.5) node(l) {$L_v$};
\draw (-8,2.5) node(r) {$R_v$};
\draw (v) -- (l);
\draw (v) -- (r);

\draw[->,thick] (-6.5,2) -- (-4.5,2);

\draw (0,0) node(s1)[circle,draw,fill=red!25] {$s_1$};
\filldraw (s1) -- (1,1) circle (2pt);
\draw (-1,1) node(s2)[circle,draw,fill=red!25] {$s_2$};
\draw (s1) -- (s2);

\filldraw (s2) -- (0,2) circle (2pt);
\draw (-2,2) node(sd)[] {$\dots$};
\draw (s2) -- (sd);

\draw (-3,3) node(sp)[circle,draw] {$s_p$};
\draw (sd) -- (sp);

\draw (-4,4) node(spl) {$L_v$};
\draw (-2,4) node(spr) {$R_v$};

\draw (sp) -- (spl);
\draw (sp) -- (spr);
\end{tikzpicture}
\end{center}
\end{minipage}


\item Now we apply a local operation to each node with a dashed right edge. Let $v$ be such a node. First convert its dashed right edge to solid edge, and add $v$ to the set of marked nodes. Then, if the left child of $v$ is a leaf, swap the two children of $v$. 
\end{enumerate}
This map has a clear inverse: for any marked node, if the left child is an ascent then we undo step (i), and if it is a descent we undo step (ii). This establishes the bijection (1) to (2).

To go from (2) to (3) we delete all right edges and all leaves from the binary tree, and then add edges connecting each vertex to all of the vertices in the right path starting from its left child. Finally, we add a node labelled $n+1$ and connect it to the vertices of the root's right-path (including the root). The set of marked vertices is unchanged. Since the right-paths are always decreasing, there is no loss of information, and this map is a bijection. 

Finally, we give the map (3) $\leftrightarrow$ (4). Given a Cayley tree $T$ with $n+1$ vertices we define a function $f : [n-1] \to [n+1]$ as follows: define $f(1)$ to be the label of the parent of the leaf vertex of $T$ of minimum label. Then delete this leaf, and use the same rule to define $f(2)$, then $f(3)$, and so on to $f(n-1)$ (deleting leaves at each stage). The resulting function $f$ is known as the \emph{Pr\"ufer sequence} of the tree $T$, and it can be shown that this encoding is well-defined and bijective \cite[Prop. 5.3.2]{Stanley:volume2}. For the subset $S$ we take the set of labels of the marked nodes of $T$. It follows from the definition of $f$ that $\text{Im}(f)$ consists of all non-leaf vertices of $T$, whence $S \subset \text{Im}(f)$. The inverse of this map is given by inverting the Pr\"ufer sequence, and then marking the nodes recorded in $S$. Thus we have a bijection (3) $\leftrightarrow$ (4).

\section{Extended Arrangements} \label{sec-extended-arrangements}
All of the results from the previous sections carry over to the $m$-Catalan and $m$-Shi arrangements. In this section we state the bijective results. An \emph{$m$-ary tree} is a rooted plane tree where all vertices have zero or $m$ children. We treat the children as ordered left to right; in particular, the first child of a node is its \emph{leftmost child} and the last child is its \emph{rightmost child}. The edge connecting a parent to its leftmost child (resp. rightmost child) is called a \emph{leftmost} (resp. \emph{rightmost}) edge.
\begin{definition}
An \emph{$[n]$-decorated $m$-ary tree} is an $m$-ary tree together with the following decorations: 
\begin{itemize}
    \item Each node is labelled with a subset of $[n]$. Together, the set of labels forms a partition of $[n]$.
    \item All internal edges except the leftmost are of two types: solid and dashed. 
    \item If an edge is dashed, then all of the children to its right are leaves.
\end{itemize}
\end{definition}

\begin{theorem} \label{thm-m-catalan-bijection}
The faces of the $m$-Catalan arrangement in $\mathbb{R}^n$ are in bijection with $[n]$-decorated $(m+1)$-ary trees. Furthermore the $k$-dimensional faces correspond to those with $k=\#\text{(nodes)}-\#\text{(dashed-edges)}$.
\end{theorem}

Using the same ``local structure'' reasoning of \secref{sec-shi-faces}, we obtain a set of trees for the $m$-Shi faces. Additionally, the bijections in \secref{sec-bijection-to-functions} can be generalized for any $m$, giving the following result.
\begin{theorem} \label{thm-m-shi-everything}
The faces of the $m$-Shi arrangement in $\mathbb{R}^n$ are in bijection with:
\begin{enumerate}
    \item The set of $[n]$-decorated $(m+1)$-ary trees such that all rightmost internal edges are descents. The $k$-dimensional faces have $k=\#\text{(nodes)}-\#\text{(dashed-edges)}$.
    \item The set of $(m+1)$-ary trees with $n$ nodes, labelled by $[n]$, such that all rightmost internal edges are descents, together with a subset of nodes that each has at least one node among its first $m$ children. The $k$-dimensional faces have a subset of size $n-k$.
    \item The set of Cayley trees with $n+1$ vertices, with edges of $m$ different colors, except all edges incident to $n+1$ are uncolored, together with a subset $S$ of non-leaf vertices excluding $n+1$. The $k$-dimensional faces have a subset of size $n-k$.
    %\item (same as Rooted forests with $n$ vertices, and $m$ types (colors) of edges, and a subset $S$ of nodes)
    \item The set of functions $f : [n-1] \to [mn+1]$ with a subset $S \subset [n]$ such that $\text{Im}(f) \cap [(i-1)m+1, im] \neq \varnothing$ for all $i \in S$. The $k$-dimensional faces have $|S| = n-k$.
\end{enumerate}
\end{theorem}

The proofs of \thmref{thm-m-catalan-bijection} and \thmref{thm-m-shi-everything} are fairly straightforward generalizations of the $m=1$ case.
\section{Enumerative Consequences} \label{sec-enumerative-consequences}
In this section, we state functional equations for the exponential generating functions of the face polynomials of the $m$-Catalan and $m$-Shi arrangements. We also give explicit counting formulae for the faces of any given dimension. These results are basic corollaries of the bijective correspondences obtained in the previous sections.

\subsection{Catalan Generating Function}
We define the exponential generating function 
\begin{align}
  C_m(x,y) := 1 + \sum_{n \ge 1} \frac{x^n}{n!} \sum_{k = 1}^{n} c_{n,k}^{(m)}  y^{k},
  \end{align}
 where $c_{n,k}^{(m)}$ is the number of $k$-dimensional faces of the $m$-Catalan arrangement in $\mathbb{R}^n$.
  \begin{corollary} \label{cor-cat-gf}
 Let $C$ stand for $C_m(x,y)$. We have the functional equation
 \begin{align}\label{eq-mcatalan-functional-simpler}
     C = 1 + \left(e^{x}-1 \right) \left( (1+y) C^{m+1} - C \right).
 \end{align}
 Furthermore, the number of $k$-dimensional faces of the $m$-Catalan arrangement in $\mathbb{R}^n$ is
 \begin{align} \label{eq-mcatalan-counting-formula}
   c_{n,k}^{(m)} = \sum_{i=k}^{n} S(n,i) (i-1)! \binom{i}{k} \sum_{j=0}^{i-k} (-1)^j \binom{i-k}{j} \binom{i(m+1)-jm}{i-1}.
 \end{align}

 \end{corollary}
Equation \eqref{eq-mcatalan-functional-simpler} is obtained by decomposing the trees in \thmref{thm-m-catalan-bijection} at the root. Formula \eqref{eq-mcatalan-counting-formula} is obtained by counting separately the labels and the trees, by way of Lagrange inversion and inclusion-exclusion. We omit the calculation here.
\begin{remark}
In the case $m=1$ in \eqref{eq-mcatalan-counting-formula}, one can show by inclusion-exclusion that the inner sum on $j$ collapses to $\binom{i+k}{k-1}$. Thus the number of $k$-dimensional faces of the classical Catalan arrangement in $\mathbb{R}^n$ is simply
\begin{align} \label{eq-athanasiadis-catalan}
    c_{n,k}^{(1)} = \sum_{i=k}^{n} S(n,i) (i-1)!  \binom{i}{k} \binom{i+k}{k-1}.
\end{align}
This formula was first obtained by Athanasiadis via a finite field method \cite[Cor. 8.3.2]{Athanasiadis:PhD}. Our argument gives a combinatorial explanation for each term, though we omit the details here.
\end{remark}

\subsection{Shi Generating Function}
We define the exponential generating function 
\begin{align} \label{eq-S-def}
S_m(x,y) := 1 + \sum_{n \ge 1} \frac{x^n}{n!} \sum_{k  = 1}^{n} s_{n,k}^{(m)}  y^{k} ,
\end{align}
where $s_{n,k}^{(m)}$ is the number of $k$-dimensional faces of the $m$-Shi arrangement in $\mathbb{R}^n$. 
\begin{corollary} \label{cor-shi-gf}
Let $S$ stand for $S_m(x,y)$. We have the functional equation
\begin{align} \label{eq-S-thm}
    S = \exp \left( x(1+y)S^m - x \right). 
\end{align}
Furthermore, the number of $k$-dimensional faces of the $m$-Shi arrangement in $\mathbb{R}^n$ is
\begin{align} \label{eq-mshi-counting}
    s_{n,k}^{(m)} = \binom{n}{k} \sum_{i=0}^{n-k} (-1)^i \binom{n-k}{i} (m(n-i)+1)^{n-1}.
\end{align}
\end{corollary}
Equation \eqref{eq-S-thm} is obtained by decomposing the trees in set (3) of \thmref{thm-m-shi-everything}, and the formula \eqref{eq-mshi-counting} is obtained by applying inclusion-exclusion directly to the functions in set (4) of \thmref{thm-m-shi-everything}. The counting formula \eqref{eq-mshi-counting} was first found via the finite field method in \cite[Thm. 8.2.1]{Athanasiadis:PhD}. 

For small $k$, the functions in set (4) of \thmref{thm-m-shi-everything} yield easy positive formulae. For example, the number of one-dimensional faces of the $m$-Shi arrangement is simply
\begin{align} \label{eq-shi-onedim}
  %s_{n,1} = n!.
  s_{n,1}^{(m)} = n!m^{n-1},
\end{align}
and the number of two-dimensional faces is
\begin{align} \label{eq-shi-twodim}
  %s_{n,2} = \frac{n!(n-1)(n+4)}{4}.
  s_{n,2}^{(m)} = \frac{ n! (n-1) (m(n+2)+2)m^{n-2}}{4}.
\end{align}
It is not too hard to derive the formula \eqref{eq-shi-onedim} directly from the definition of Shi faces, but we do not know a direct proof of the formula \eqref{eq-shi-twodim}.

%We observe that these counting formulae are all polynomials in $m$ of degree $n-1$. It was shown in \cite{Athanasiadis:reciprocity} that the number of regions is always a quasi-polynomial in $m$ for arrangements such as these, and these formulae suggest the same may be true for faces.
\section*{Acknowledgements}
The author is grateful to Olivier Bernardi for sharing many helpful suggestions and discussions.
\printbibliography
\end{document}
