\documentclass[finalversion]{FPSAC2025}
\articlenumber{29}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\appto\bibfont{\setlength{\emergencystretch}{.5em}}
%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{lipsum}

\usepackage{amssymb,amsmath}
\usepackage{stmaryrd,paralist}
\usepackage{bbm,url}
\usepackage{graphics,graphicx,tikz-cd}

%\usepackage[latin1]{inputenc}
\usepackage{subfigure}
%\usepackage[margin=1.4 in]{geometry}
\usepackage{hyperref,color}
%\usepackage[dvipsnames]{xcolor}
%\graphicspath{{Figures/}} 
\graphicspath{{./}{./Figures/}{../Figures/}}


\newcommand{\OB}[1]{\textcolor{blue}{OB; #1}}
\newcommand{\ob}[1]{\textcolor{blue}{#1}}




\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}


%
%\newtheorem{theo}{Theorem}
%\numberwithin{theo}{section}
%\newtheorem{thm}[thm]{Theorem}
%\newtheorem{lem}[thm]{Lemma}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{claim}[thm]{Claim}
%\newtheorem{fact}[thm]{Fact}
\newtheorem{Def}[thm]{Definition}
\newtheorem{definition}[thm]{Definition}
\newtheorem{notation}[thm]{Notation}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{example}[thm]{Example}
\newtheorem{rk}[thm]{Remark}
%
%
%\documentclass[letter]{amsart}
%\input{defs.tex}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newcommand{\ds}{\displaystyle}
\def\ni{\noindent}


\newcommand{\bitem}{\begin{compactitem}}
\newcommand{\eitem}{\end{compactitem}}



\def\ZZ{\mathbb{Z}}
\def\NN{\mathbb{N}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}

\def\bz{\mathbb{Z}}
\def\bn{\mathbb{N}}
\def\br{\mathbb{R}}
\def\rp{\mathbb{R}^+}


\def\cA{\mathcal{A}}
\def\cB{\mathcal{B}}
\def\cM{\mathcal{M}}
\def\cF{\mathcal{F}}
\def\cG{\mathcal{G}}
\def\cO{\mathcal{O}}
\def\cR{\mathcal{R}}
\def\cS{\mathcal{S}}
\def\cT{\mathcal{T}}
 
 
\def\mA{\mathcal{A}}
\def\mB{\mathcal{B}}
\def\mC{\mathcal{C}}
\def\mD{\mathcal{D}}
\def\mE{\mathcal{E}}
\def\mF{\mathcal{F}}
\def\mG{\mathcal{G}}
\def\mL{\mathcal{L}}
\def\mM{\mathcal{M}}
\def\mO{\mathcal{O}}
\def\mP{\mathcal{P}}
\def\mR{\mathcal{R}}
\def\mS{\mathcal{S}}
\def\mT{\mathcal{T}}
 
\def\cW{\mathcal{W}}
\def\cL{\mathcal{L}}

\def\cX{\mathcal{X}}


\def\bA{\mathbf{A}}
\def\bE{\mathbf{E}}
\def\bL{\mathbf{L}}
\def\bM{\mathbf{M}}
\def\bO{\mathbf{O}}
\def\bW{\mathbf{W}}
\def\bX{\mathbf{X}}
\def\bAL{\mathbf{AL}}
\def\bT{\mathbf{T}}


\def\mShi{\mathcal{S}hi}

%\def\hH{\widehat{H}}
\newcommand{\Id}{\textrm{Id}}



\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\om}{\omega}
\newcommand{\si}{\sigma}
\newcommand{\eps}{\epsilon}
\renewcommand{\th}{\theta}


\newcommand{\Om}{\Omega}
\newcommand{\Ga}{\Gamma}
\newcommand{\De}{\Delta}
\newcommand{\Th}{\Theta}
\newcommand{\Ups}{\Upsilon}





\newcommand{\ov}[1]{\overline{#1}}
\newcommand{\wt}[1]{\widetilde{#1}}

\newcommand{\bal}{\ov{\al}}
\newcommand{\bbe}{\ov{\be}}
\newcommand{\bga}{\ov{\ga}}
\newcommand{\bde}{\ov{\de}}
\newcommand{\bth}{\ov{\th}}
\newcommand{\bPhi}{\ov{\Phi}}
\newcommand{\bPsi}{\ov{\Psi}}


\newcommand{\fig}[3]{\begin{figure}[!ht]\begin{center}\includegraphics[#1]{#2.pdf}\end{center}\caption{#3}\label{fig:#2}\end{figure}}

\newcommand{\dd}{\textbf{d}}
\newcommand{\ee}{\textbf{e}}
\newcommand{\ff}{\textbf{f}}
\newcommand{\mm}{\textbf{m}}
\newcommand{\vv}{\textbf{v}}
\newcommand{\xx}{\textbf{x}}
\newcommand{\yy}{\textbf{y}}

\newcommand{\fS}{\mathfrak{S}} % Symmetric group


\DeclareMathOperator{\cadet}{\!\textrm{-cadet}}
\DeclareMathOperator{\child}{\!\textrm{-child}}
\renewcommand{\path}{\textrm{path}}
\DeclareMathOperator{\drift}{\textrm{drift}}
\newcommand{\pathT}{\path_T}
\DeclareMathOperator{\driftT}{\drift_T}
\DeclareMathOperator{\blocks}{\textrm{blocks}}
\DeclareMathOperator{\shadow}{\textrm{shadow}}
\DeclareMathOperator{\start}{\textrm{start}}
\DeclareMathOperator{\eend}{\textrm{end}}
\DeclareMathOperator{\comp}{\textrm{comp}}


\DeclareMathOperator{\tr}{\textrm{Triple}}
\DeclareMathOperator{\trmn}{\tr_m^n}

\newcommand{\wT}{{\wt{T}}}
\newcommand{\vD}{{\vec{\mD}}}
\newcommand{\oV}{{\ov{V}}}
\newcommand{\oD}{{\ov{D}}}
\newcommand{\oE}{{\ov{E}}}
\newcommand{\oG}{{\ov{\mG}}}


\DeclareMathOperator{\Tmn}{\mT_m^n}
\DeclareMathOperator{\Tmnd}{\mT_{mn}^d}
\DeclareMathOperator{\oT}{\ov{\mT}}
\DeclareMathOperator{\oTmn}{\ov{\mT}_m^n}
\DeclareMathOperator{\oSmn}{\ov{\mS}_m^n}
\DeclareMathOperator{\wA}{\wt{\mA}}
\DeclareMathOperator{\wTmn}{\wt{\mT}_m^n}



%\DeclareMathOperator{\precT}{\overset{T}{\prec}}
%\DeclareMathOperator{\preceqT}{\overset{T}{\preceq}}
%\DeclareMathOperator{\precL}{\overset{L}{\prec}}
\DeclareMathOperator{\precT}{\prec_T}
\DeclareMathOperator{\precwT}{\prec_{\wt T}}
\DeclareMathOperator{\preceqT}{\preceq_T}
%\DeclareMathOperator{\succT}{\succ_T}
\DeclareMathOperator{\succeqT}{\succeq_T}
\DeclareMathOperator{\succeqwT}{\succeq_{\wt T}}
\DeclareMathOperator{\precL}{\prec_L}
\DeclareMathOperator{\preceqL}{\preceq_L}


\newcommand{\musim}{\overset{\mu}{\sim}}
\newcommand{\nmusim}{\overset{\mu}{\nsim}}
\newcommand{\Lsim}{\overset{L}{\sim}}
\newcommand{\nLsim}{\overset{L}{\nsim}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% define your title in the usual way
\title{Bijections for faces of braid-type arrangements}
%
%
%\author[Olivier Bernardi]{\texorpdfstring{Olivier Bernardi}{Olivier Bernardi}}
%\thanks{Department of Mathematics, Brandeis University, Waltham MA, USA.
%bernardi@brandeis.edu.\\% Supported by NSF grant DMS-1308441 and DMS-1800681.\\
%}
%
%
%
%\title{Bijections for faces of braid-type arrangements}
%\date{\today}

%
%\begin{abstract}
%We establish a general bijective framework for encoding faces of certain hyperplane arrangements of combinatorial interest.
%Precisely, we consider hyperplane arrangements in $\RR^n$ whose hyperplanes are all of the form $\{x_i-x_j=s\}$ for some $i,j\in[n]$ and $s\in \ZZ$.
%Such an arrangement $\mA$ is \emph{strongly-transitive} if it satisfies the following condition: if $\{x_i-x_j=s\}\notin \mA$ and $\{x_j-x_k=t\}\notin \mA$ for some $i,j,k\in [n]$ and $s,t\geq 0$, then $\{x_i-x_k=s+t\}\notin \mA$.
%For any strongly-transitive arrangement $\mA$, we establish a bijection between the faces of $\mA$ and some set of decorated plane trees. 
%\end{abstract}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Olivier Bernardi\thanks{\href{mailto:bernardi@brandeis.edu}{bernardi@brandeis.edu}. Olivier Bernardi was partially supported by NSF Grant DMS-2154242.$\partial$\;supp.}\addressmark{1}}{Olivier Bernardi}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Brandeis University, Waltham MA, USA.}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We establish a general bijective framework for encoding faces of some classical hyperplane arrangements.
Precisely, we consider hyperplane arrangements in $\RR^n$ whose hyperplanes are all of the form $\{x_i-x_j=s\}$ for some $i,j\in[n]$ and $s\in \ZZ$.
Such an arrangement $\mA$ is \emph{strongly transitive} if it satisfies the following condition: if $\{x_i-x_j=s\}\notin \mA$ and $\{x_j-x_k=t\}\notin \mA$ for some $i,j,k\in [n]$ and $s,t\in \NN$, then $\{x_i-x_k=s+t\}\notin \mA$.
For any strongly transitive arrangement $\mA$, we establish a bijection between the faces of $\mA$ and some set of decorated plane trees. }

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Hyperplane arrangements, Coxeter arrangements, regions, faces, counting}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio-hyperplanes.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle



\section{Introduction}\label{sec:intro}
%
%
%Given a set of integers $S\subseteq \ZZ$ we define, for every dimension $n>0$, the arrangement $\mA_S^n\subseteq \mA_m^n\subset \RR^n$ as follows:
%$$\mA_S^n:=\bigcup_{\substack{1\leq i<j\leq n\\ s\in S}}\{x_i-x_j=s\}.$$


In this extended abstract we establish bijective results about the faces of some classical families of hyperplane arrangements. 
Specifically, we consider real hyperplane arrangements made of a finite number of hyperplanes of the form 
\begin{equation}\label{eq:hyperplane}
\{(x_1,\ldots,x_n)\in \RR^n ~\mid~ x_i-x_j=s\},
\end{equation} 
with $i,j\in\{1,\ldots,n\}$ and $s\in \ZZ$. We call them \emph{braid-type arrangements}. From now on, we make an abuse of notation and denote by $\{x_i-x_j=s\}$ the hyperplane in~\eqref{eq:hyperplane}.


Given a set of integers $S\subseteq \ZZ$ we define, for every dimension $n>0$, the braid-type arrangement $\mA_S^n\subset \RR^n$ as follows:
$$\mA_S^n:=\bigcup_{\substack{1\leq i<j\leq n\\ s\in S}}\{x_i-x_j=s\}.$$
Classical examples include the \emph{braid}, \emph{Catalan}, \emph{Shi}, \emph{semiorder}, and \emph{Linial} arrangements represented in Figure~\ref{fig:classical-arrangements}, which correspond to $S=\{0\},~\{-1,0,1\},~\{0,1\},~\{-1,1\}$, and $\{1\}$ respectively.
% These arrangements are represented in Figure~\ref{fig:classical-arrangements}.

% OB: Maybe place the above sentence at an other place.
%; Important early references are \cite{Orlik:hyperplane-arrangements,Orlik:Poincare-hyperplanes,Zaslavsky:region-hyperplanes}.. 

\fig{width=\linewidth}{classical-arrangements}{The braid, Catalan, Shi, semiorder, and Linial arrangements in dimension $n=3$ (seen from the direction $(1,1,1)$).}
%Note that these classical arrangements correspond to all the sets $S\subseteq\{-1,0,1\}$ up to symmetry. 

There is an extensive literature on counting regions of braid-type arrangements, starting with the work of Shi \cite{Shi:nb-regions}. %We refer the reader to~\cite{Orlik:hyperplane-arrangements} or \cite{Stanley:hyperplane-arrangements} for an introduction to the theory of hyperplane arrangements. 
Seminal counting results were established by Stanley~\cite{Stanley:hyperplane-tree-inversions,Stanley:hyperplane-interval-orders-overview}, Postnikov and Stanley~\cite{Postnikov:coxeter-hyperplanes}, and Athanasiadis~\cite{Athanasiadis:finite-field-method}. Since then, the subject has become quite popular among combinatorialists, and many beautiful counting formulas and bijections were discovered for various families of arrangements; see for instance \cite{Armstrong:Shi-Ish,Athanasiadis:free-deformations,Athanasiadis:Catalan-Hyperplanes,Athanasiadis:bijection-Shi,Corteel:hyperplane-valued-graphs,Headley:hyperplane-Weyl-groups,Hopkins:bigraphical-arrangements,Leven:bijections-Ish-Shi}.% (see also Section~\ref{sec:definitions} for additional references). 

By contrast, there is a paucity of results about lower dimensional faces in braid-type arrangements. Notable exceptions are enumerative formulas by Athanasiadis  \cite{Athanasiadis:finite-field-method} and bijections by Levear \cite{Levear} about the Catalan and Shi arrangements.

In the present abstract, we develop a general bijective framework for encoding the faces of a large class of braid-type arrangements. Our framework applies to all \emph{strongly transitive} arrangements, which are the braid-type arrangements $\mA$ satisfying the following condition: if $\{x_i-x_j=s\}\notin \mA$ and $\{x_j-x_k=t\}\notin \mA$ for some distinct indices $i,j,k$ and $s,t\in \NN$, then $\{x_i-x_k=s+t\}\notin \mA$. For any such arrangement we give an explicit bijection between the set of faces of $\mA$ and a set of trees. Our bijection coincides with the one established by Levear~\cite{Levear} for the case of the Catalan and Shi arrangements, up to minor changes in notation. Our bijective results for faces of braid-type arrangements are an extension of a general bijective framework for regions of (transitive) arrangements that we established in \cite{OB}. We actually use the results from \cite{OB} to establish those in the present abstract.


The abstract is organized as follows.
In Section~\ref{sec:background} we set our notation, and recall some necessary background from \cite{OB}. 
In Section~\ref{sec:main} we state our main result, which gives a bijection for faces of strongly transitive arrangements.
In Section~\ref{sec:exp} we apply our bijection to a few classes of strongly transitive arrangements. In particular we discuss a multivariate generalization of the Catalan arrangement, a family of arrangements interpolating between the Catalan and Shi arrangements, and symmetric arrangements such as the semiorder arrangements.
The proof of our main result is sketched in Section~\ref{sec:proof}.


%%Given a set of integers $S\subseteq \ZZ$ we define, for every dimension $n>0$, the arrangement $\mA_S^n\subseteq \mA_m^n\subset \RR^n$ as follows:
%%$$\mA_S^n:=\bigcup_{\substack{1\leq i<j\leq n\\ s\in S}}\{x_i-x_j=s\}.$$
%%\OB{Define the Catalan, Shi, semiorder and Linial arrangements.}






\section{Notation and background}\label{sec:background}
In this section we set our notation and recall some relevant results from \cite{OB}.
 
For a positive integer $n$, we define $[n]:=\{1,2,\ldots,n\}$, and we denote by $\fS_n$ the set of permutations of $[n]$. For any integers $m<n$ we define $[m;n]:=\{k\in \ZZ\mid m\leq k\leq n\}$. For a real hyperplane arrangement $\mA$, we denote by $\mR(\mA)$ the set of regions of $\mA$.

\begin{definition}
Let $m,n\in \NN$. The \emph{$m$-Catalan arrangement in dimension $n$} is
$$\mA_m^n=\bigcup_{\substack{1\leq i<j\leq n\\ s\in[-m;m]}}\{x_i-x_j=s\}\subseteq\RR^n.$$
\end{definition}
%
%\newcommand{\tr}{\textrm{triple}}
%\newcommand{\trmn}{\tr_m^n}

We will now introduce a canonical way to label the hyperplanes in braid-type arrangements.


\begin{notation}
For $m,n\in \NN$ we define 
$$\trmn:=\{(i,j,s)\mid i,j\in [n],~s\in[0;m]\textrm{ such that }i\neq j \textrm{ and }(s>0\textrm{ or }i>j)\}.$$
\end{notation}
Observe that each hyperplane of $\mA_m^n$ is of the form $\{x_i-x_j=s\}$ for exactly one triple $(i,j,s)$ in $\trmn$.
For an arrangement $\mA\subseteq \mA_m^n$ we define 
$$\trmn(\mA):=\{(i,j,s)\in\trmn\mid \{x_i-x_j=s\}\in \mA\},$$
so that 
$$\ds \mA=\bigcup_{(i,j,s)\in \trmn(\mA)}\{x_i-x_j=s\}.$$
% $s\in[0;m]$ and $i,j\in [n]$ with either $s>0$ or $i>j$. In \cite{OB} bijections were established for the regions of \emph{transitive arrangements}.
 

\begin{definition}
%An arrangement $\mA\subseteq \mA_m^n$ is \emph{transitive} if for all distinct indices $i,j,k\in[n]$ and integers $s,t\geq 0$ one has: \\
%if $\{x_i-x_j=s\}\notin \mA$ with $s>0$ or $i>j$, and $\{x_j-x_k=t\}\notin \mA$ with $t>0$ or $j>k$, then $\{x_i-x_k=s+t\}\notin \mA$.\\
An arrangement $\mA\subseteq \mA_m^n$ is \emph{transitive} if for all distinct indices $i,j,k\in[n]$ and integers $s,t\geq 0$ such that $(i,j,s)$ and $(j,k,t)$ are in $\trmn$ the following holds: \\
\centerline{if $\{x_i-x_j=s\}\notin \mA$ and $\{x_j-x_k=t\}\notin \mA$, then $\{x_i-x_k=s+t\}\notin \mA$.}
\end{definition}


\begin{definition}
A \emph{$(m,n)$-tree} is a rooted $(m+1)$-ary tree with $n$ nodes labeled with distinct labels in $[n]$ (the leaves have no labels). 
We denote by $\mT_m^n$ the set of all $(m,n)$-trees (there are $\frac{n!}{mn+1}\binom{(m+1)n}{n}$ of them). 

%(It is easy to see that $|\mT_m^n|=\frac{((m+1)n)!}{(mn+1)!}$).
For a tree $T\in\mT_m^n$ we identify the nodes with their labels in $[n]$ (so that the node set of $T$ is $[n]$).
By definition, a node $j\in [n]$ of $T$ has exactly $m+1$ (ordered) children, which are denoted by $0\child(j)$, $1\child(j)$, \ldots, $m\child(j)$ respectively.

The node $i\in[n]$ is the \emph{$s$-cadet} of the node $j\in[n]$ in $T$ if $i=s\child(j)$ and $t\child(j)$ is a leaf for all $t\in[s+1;m]$. In this case, we write $i=s\cadet(j)$, and we call $\{i,j\}$ a \emph{cadet-edge}.
%A \emph{cadet edge} of $T$ is an edge $\{i,j\}$ for some nodes $i,j\in[n]$ such that $i$ is the cadet of $j$.
\end{definition}

\begin{definition}
Let $\mA\subseteq \mA_m^n$ be an arrangement. We define 
$$\Tmn(\mA):=\{T\in\mT_m^n\mid \forall (i,j,s)\in\trmn\setminus\trmn(\mA) ,~i\neq s\cadet(j)\}.$$
\end{definition}
It was established in \cite{OB} that, for any transitive arrangement $\mA$, the regions of $\mA$ are in bijection with the trees in $\Tmn(\mA)$.
In order to describe the bijection we need to introduce a total order on the vertices of each tree in $\mT_m^n$. 

\begin{definition}
For every vertex $v$ of in a tree $T$, we consider the sequence $v_0,v_1,\ldots,v_k=v$ on the path of $T$ from the root $v_0$ to the vertex $v$, and define $\pathT(v):=(s_1,\ldots,s_k)$, where $v_i=s_i\child(v_{i-1})$ for all $i\in[k]$. 
We also define the \emph{drift} of $v$ as $\ds \driftT(v):=\sum_{i=1}^k s_i.$
\end{definition}

\begin{definition}
Let $T$ be a tree in $\mT_m^n$. We define a total order $\preceqT$ on the vertices of $T$ as follows.
Let $v,w$ be distinct vertices of $T$. Let $\pathT(v)=(s_1,\ldots,s_k)$ and $\pathT(w)=(t_1,\ldots,t_\ell)$. 
Then $v\precT w$ if either 
\bitem
\item $\driftT(v)<\driftT(w)$, or 
\item $\driftT(v)=\driftT(w)$ and there exists $j\leq k$ such that $(s_1,\ldots,s_j)=(t_1,\ldots,t_j)$ and ($j=k$ or $s_{j+1}>t_{j+1}$).
\eitem
\end{definition}
%The order $\precT$ is indicated for the tree represented in Figure~\ref{fig:prec-order}.

%\fig{width=.25\linewidth}{prec-order}{The order $\preceq_T$ for a binary tree $T$. The vertices of $T$ are ordered as follows: $a\precT b\precT c\precT \cdots \precT s$. Here the horizontal placement of vertices corresponds to their drift in the tree. Hence, in this representation, the relation $v\prec_T w$ can be thought as meaning that either ``$v$ is strictly to the left of $w$'' in the tree $T$ or ``$v$ is at the vertical of $w$ but below $w$'' in the tree~$T$.}

\begin{definition}
Let $\mA\subseteq \mA_m^n$ be an arrangement. For every tree $T\in \Tmn(\mA)$ we define the polyhedron %$\Phi_A(T)\subseteq \RR^n$ as follows:
$$\phi_\mA(T):= \bigg(\bigcap_{\substack{(i,j,s)\in \trmn(\mA) \\ i\precT s\child(j)}}\{x_i-x_j<s\}\bigg)\cap \bigg(\bigcap_{\substack{(i,j,s)\in \trmn(\mA)\\ i\succeqT s\child(j)}}\{x_i-x_j>s\}\bigg).$$
\end{definition}
%It is clear from the definition that $\phi_\mA(T)$ is either empty or a region of $\mA$. In fact, it is always a region of $\mA$, and 
The following result was proved in \cite[Theorem 8.8]{OB}.

\begin{thm}[\cite{OB}]\label{thm:regions}
If an arrangement $\mA\subseteq\mA_m^n$ is transitive, then $\Phi_\mA$ is a bijection between the set $\Tmn(\mA)$ of trees and the set $\mR(\mA)$ of regions of $\mA$.
%(If $\mA$ is not transitive, then $\Phi$ is a surjection.)
\end{thm}








%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Main results}\label{sec:main}
In this section we state our main result, which is a bijection between the set of faces of any ``strongly transitive'' arrangement and some set of marked trees.

\begin{definition}
An arrangement $\mA\subseteq \mA_m^n$ is \emph{strongly transitive} if for all distinct indices $i,j,k\in[n]$ and integers $s,t\geq 0$ the following holds: \\
\centerline{if $\{x_i-x_j=s\}\notin \mA$ and $\{x_j-x_k=t\}\notin \mA$, then $\{x_i-x_k=s+t\}\notin \mA$.}
\end{definition}The only difference between transitive and strongly transitive arrangements is that the conclusion $\{x_i-x_k=s+t\}\notin \mA$ needs to hold even in the cases ($s=0$ and $i<j$) or ($t=0$ and $j<k$).
In fact, an arrangement $\mA\subseteq \mA_m^n$ is strongly transitive if and only if $\pi(\mA)$ is transitive for every permutation $\pi\in \fS_n$.

\begin{example} 
The (extended) Catalan, Shi and semiorder arrangements are strongly transitive. 
The Linial arrangement is transitive, but not strongly transitive. 
Any transitive arrangement containing the braid arrangement is strongly transitive. 
\end{example}

Let us state which arrangements of the form $\mA_S^n$ are strongly transitive (the proof is omitted): 

\begin{lemma}\label{lem:transitive-sets}
Let $S\subseteq \ZZ$ be a set of integers. The following are equivalent:
\bitem
\item[(i)] $\mA_S^n$ is strongly transitive for every integer $n> 0$,
\item[(ii)] $\mA_S^n$ is strongly transitive for at least one integer $n\geq 3$,
\item[(iii)] for all integers $s,t\notin S$, if $st\geq 0$ then $s+t\notin S$ and if $st\leq 0$ then $s-t,t-s\notin S$.
\eitem
\end{lemma}

We will now define the trees in bijection with the faces of a strongly transitive arrangement.

\begin{definition}
A \emph{marked $(m,n)$-tree} is a pair $(T,\mu)$, where $T\in\mT_m^n$ is a $(m,n)$-tree and $\mu$ is a set of cadet-edges of $T$ such that if an edge $e\in \mu$ is of the form $e=\{j,0\cadet(j)\}$ then $j<0\cadet(j)$. We refer to the edges in $\mu$ as the \emph{marked edges}. 

We denote by $\oT_m^n$ the set of marked $(m,n)$-trees. 
\end{definition}

Note that the marked edges of a marked tree in $\oT_m^n$ form a collection of vertex-disjoint paths. 
%A result of Levear \cite{Levear} is that the faces of the Catalan arrangement $\mA_m^n$ are in bijection with the set $\ov{\mT}_m^n$ of marked $(m,n)$-trees. 
%In order to define a bijection for any strongly transitive arrangement we need some additional definitions.
%\begin{definition}
Let $(T,\mu)\in\oT_m^n$ be a marked $(m,n)$-tree. For nodes $i,j\in[n]$, we write $i\musim j$ if $i=j$ or $i\neq j$ and all the edges on the path of $T$ between $i$ and $j$ are marked. 
 This is an equivalence relation, and we call its equivalence classes the \emph{blocks} of $(T,\mu)$.
%Further, we denote by $\blocks(\mu)$ the set of blocks of $(T,\mu)$ (this is a partition of $[n]$).
%\end{definition}


%$$\bPhi(T,\mu)=\left(\bigcap_{\substack{\{i,j\}\in \mu \\ i=s\child(j)}}\{x_i-x_j=s\}\right)\cap\left(\bigcap_{\substack{(i,j,s)\in \tr_m^n\\ i\nmusim j \\ i\preceqT s\child(j)}}\{x_i-x_j< s\}\right)\cap \left(\bigcap_{\substack{(i,j,s)\in \tr_m^n\\i\nmusim j \\ i\succT s\child(j)}}\{x_i-x_j>s\}\right).$$

\begin{definition}\label{def:A-connected-tree}
Let $\mA\subseteq \mA_m^n$ be an arrangement. A block $B\subseteq [n]$ of a marked tree $(T,\mu)\in \oT_m^n$ is called \emph{$\mA$-connected} if 
the graph $G$ with vertex set $B$ and edge set 
$$E=\big\{\,\{i,j\}\mid i,j\in B~\textrm{such that}~\{x_i-x_j=\driftT(i)-\driftT(j)\}\in \mA\,\big\}$$ 
is connected. We say that the marked tree $(T,\mu)$ is \emph{$\mA$-connected} if every block of $(T,\mu)$ is $\mA$-connected. 


We say that a marked tree $(T,\mu)\in\oTmn$ satisfies the \emph{$\mA$-cadet condition} if every non-marked cadet-edge $e=\{i,j\}$ of $(T,\mu)$, with $i=s\cadet(j)$, satisfies ($s=0$ and $i<j$) or (there exists $i'\musim i$ and $j'\musim j$ such that the hyperplane $\{x_{i'}-x_{j'}=\driftT(i')-\driftT(j')\}$ is in $\mA$).
 
We define $\oTmn(\mA)$ as the set of marked trees in $\oTmn$ which are $\mA$-connected and satisfy the $\mA$-cadet condition.
% 
%We denote by $\oTmn(\mA)$ the set of marked trees $(T,\mu)$ in $\oT_m^n$ such that 
%\bitem
%\item every block of $(T,\mu)$ is $\mA$-connected, 
%\item every non-marked cadet-edge $e=\{i,j\}$ of $(T,\mu)$, with $i=s\cadet(j)$, satisfies ($s=0$ and $i<j$) or (there exists $i'\musim i$ and $j'\musim j$ such that the hyperplane $\{x_{i'}-x_{j'}=\driftT(i')-\driftT(j')\}$ is in $\mA$).
%\eitem
%% OB (Note to self): if $s=0$ and there exists no such hyperplane, then $i$ and $j$ are in fact alone in their blocks assuming that $\mA$ is strongly transitive. 
\end{definition}



\begin{definition}
Let $\mA\subseteq \mA_m^n$. We associate to each marked tree $(T,\mu)$ in $\oTmn(\mA)$ a polyhedron
\begin{eqnarray*}
\bPhi_\mA(T,\mu)&:=&\bigg(\bigcap_{\substack{\{i,j\}\in \mu \\ i=s\child(j)}}\{x_i-x_j=s\}\bigg)\\
&&\cap\bigg(\bigcap_{\substack{(i,j,s)\in \trmn(\mA)\\ i\nmusim j,~ i\precT s\child(j)}}\{x_i-x_j< s\}\bigg)\cap \bigg(\bigcap_{\substack{(i,j,s)\in \trmn(\mA)\\i\nmusim j,~ i\succeqT s\child(j)}}\{x_i-x_j>s\}\bigg).
\end{eqnarray*}
\end{definition}
%
%\begin{rk}\label{rk:eqL}
%It is easy to check that for any marked tree $(T,\mu)$ in $\oTmn(\mA)$, one has
%\begin{equation}\label{eq:L2}
%\bigcap_{\substack{\{i,j\}\in \mu \\ i=s\child(j)}} \{x_i-x_j=s\} 
%= \bigcap_{\substack{(i,j,s)\in \trmn(\mA)\\ i\musim j}}\{x_i-x_j=s\}.
%\end{equation}
%Equation~\eqref{eq:L2} holds because every block of $(T,\mu)$ is $\mA$-connected, hence both sides of~\eqref{eq:L2} consists of the set of points $(x_1,\ldots,x_n)\in \RR^n$ such that $x_i-x_j=\driftT(i)-\driftT(j)$ for all $i\musim j$.
%
%Consequently, the polyhedron $\bPhi_\mA(T,\mu)$ is a face of $\mA$ (of codimension $|\mu|$), unless it is empty.
%\end{rk}
%
%For an arrangement $\mA\subset \RR^n$, we denote by $\mF(\mA)$ the set of faces of $\mA$.

We are now ready to state our main result, which is illustrated in Figure~\ref{fig:exp-face-bijection}.

\begin{thm}\label{thm:main}
If an arrangement $\mA\subseteq \mA_m^n$ is strongly transitive, then $\bPhi_\mA$ is a bijection between the set $\oTmn(\mA)$ of marked trees and the set $\mF(\mA)$ of faces of $\mA$. The number of marked edges of $(T,\mu)$ is equal to the codimension of the corresponding face $\bPhi_\mA(T,\mu)$.
\end{thm}


\fig{width=.9\linewidth}{exp-face-bijection}{The bijection $\bPhi_\mA$ between the faces of an arrangement $\mA$ and the set $\oTmn(\mA)$.}
The special cases of Theorem~\ref{thm:main} corresponding to $\mA=\mA_m^n$ (the $m$-Catalan arrangement) or $\mA=\mA_{[-m+1;m]}^n$ (the $m$-Shi arrangement) give bijections which are the same as that of Levear \cite{Levear} (up to small differences of presentation). We discuss these special cases, and some other examples, in the next section. 

%
%\begin{proof}
%Clearly, (i) implies (ii). Next, we prove that (ii) implies (iii). Suppose that $\mA_S^n$ is transitive for some $n\geq 3$. We consider some integers $s,t\notin S$, and distinguish four cases in order to prove (iii).
%\bitem
%\item[Case $s,t\geq 0$:] Since $\{x_1-x_2=s\}\notin \mA_S^n$ and $\{x_2-x_3=t\}\notin \mA_S^n$, we get $\{x_1-x_3=s+t\}\notin \mA_S^n$, hence $s+t\notin S$. 
%\item[Case $s,t\leq 0$:] Since $\{x_3-x_2=-s\}\notin \mA_S^n$ and $\{x_2-x_1=-t\}\notin \mA_S^n$, we get $\{x_3-x_1=-s-t\}\notin \mA_S^n$, hence $s+t\notin S$. 
%\item[Case $s\geq 0\geq t$:] Since $\{x_1-x_3=s\}\notin \mA_S^n$ and $\{x_3-x_2=-t\}\notin \mA_S^n$, we get $\{x_1-x_2=s-t\}\notin \mA_S^n$, hence $s-t\notin S$. Since $\{x_3-x_1=-t\}\notin \mA_S^n$ and $\{x_1-x_2=s\}\notin \mA_S^n$, we get $\{x_3-x_2=s-t\}\notin \mA_S^n$, hence $t-s\notin S$. 
%\item[Case $s\leq 0\leq t$:] Since $\{x_1-x_3=t\}\notin \mA_S^n$ and $\{x_3-x_2=-s\}\notin \mA_S^n$, we get $\{x_1-x_2=t-s\}\notin \mA_S^n$, hence $t-s\notin S$. Since $\{x_3-x_1=-s\}\notin \mA_S^n$ and $\{x_1-x_2=t\}\notin \mA_S^n$, we get $\{x_3-x_2=t-s\}\notin \mA_S^n$, hence $s-t\notin S$. 
%\eitem
%It remains to prove that (iii) implies (i). Suppose that $S$ satisfies (iii), and fix $n>0$. We consider distinct integers $i,j,k\in [n]$, and $s,t\in \NN$ such that $\{x_i-x_j=s\}\notin \mA_S^n$ and $\{x_j-x_k=t\}\notin \mA_S^n$. We need to prove $\{x_i-x_k=s+t\}\notin \mA_S^n$, and distinguish four cases.
%\bitem
%\item[Case $i<j<k$:] Since $s,t\notin S$, we get $s+t\notin S$, hence $\{x_i-x_k=s+t\}\notin \mA_S^n$. 
%\item[Case $i>j>k$:] Since $-s,-t\notin S$, we get $-s-t\notin S$, hence $\{x_i-x_k=s+t\}\notin \mA_S^n$. 
%\item[Case $i<j>k$:] Since $s,-t\notin S$, we get $s+t,-t-s\notin S$, hence $\{x_i-x_k=s+t\}\notin \mA_S^n$. 
%\item[Case $i>j<k$:] Since $-s,t\notin S$, we get $-s-t,t+s\notin S$, hence $\{x_i-x_k=s+t\}\notin \mA_S^n$. 
%\eitem
%\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Applications}\label{sec:exp}
In this section we apply Theorem~\ref{thm:main} to several families of braid-type arrangements. 

%%
%%Given a set of integers $S\subseteq \ZZ$ we define, for every dimension $n>0$, the arrangement $\mA_S^n\subseteq \mA_m^n\subset \RR^n$ as follows:
%%$$\mA_S^n:=\bigcap_{\substack{1\leq i<j\leq n\\ s\in S}}\{x_i-x_j=s\}.$$
%%The \emph{Catalan arrangement} is $\mA_{[-1;1]}^n=\mA_1^n$ and the \emph{Shi arrangement} is $\mA_{[0;1]}^n$. For $m>0$ the \emph{$m$-extended Catalan arrangement} is $\mA_m^n$ and the \emph{$m$-extended Shi arrangement} is $\mA_{[-m+1;m]}^n$.

\subsection{From the Catalan arrangement to the Shi arrangement, and back}
%Let $m,n$ be positive integers. 
Theorem~\ref{thm:main} readily implies the following results of Levear \cite{Levear}  about the $m$-Catalan and $m$-Shi arrangements.
\begin{cor}[\cite{Levear}]\label{cor:Cat}
Let $m,n$ be positive integers. The faces (of codimension $k$) of the $m$-Catalan arrangement $\mA_m^n$ are in bijection with the marked trees in $\oTmn$ (having $k$ marked edges).
\end{cor}

\begin{cor}[\cite{Levear}]\label{cor:Shi}
Let $m,n$ be positive integers. The faces (of codimension $k$) of the $m$-Shi arrangement $\mShi_m^n=\mA_{[-m+1;m]}^n$
 are in bijection with the set $\oSmn$ of marked trees $(T,\mu)$ in $\oTmn$ (having $k$ marked edges) such that if $i=m\child(j)$ for some nodes $i,j\in [n]$ of $T$, then $i<j$.
\end{cor}
It is clear that $\mA_m^n$ and $\mShi_m^n$ are strongly transitive.
We can therefore apply Theorem~\ref{thm:main}, and we only need to check that $\oTmn(\mA_m^n)=\oTmn$ and $\oTmn(\mShi_m^n)=\oSmn$. These proofs are rather straightforward. We will actually prove a more general result that interpolates between the case of the Catalan arrangement and the case of the Shi arrangement.


%
%. Before starting this proof, let us observe that for any marked tree $(T,\mu)\in\oTmn$ and any nodes $i,j$ such that $i=s\cadet(j)$ one has 
%$$\{x_i-x_j=\driftT(i)-\driftT(j)\}=\{x_i-x_j=s\}\in \mA_m^n.$$
%
%We will now check that any tree in $\oTmn$ is $\mA_m^n$-connected. Let $B$ be a block of a marked tree $(T,\mu)\in\oTmn$, and let $G$ be the graph with vertex set $B$ and edge set 
%$$E=\{\{i,j\}\mid i,j\in B~\textrm{ such that }~\{x_i-x_j=\driftT(i)-\driftT(j)\}\in \mA\}.$$ 
%The block $B$ corresponds to a path of cadet edges in $T$, so $B$ is of the form $B=\{i_1,\ldots,i_\ell\}$, where for all $j<k$, $i_{j+1}=s_j\cadet(i_j)$ for some $s_j$. Hence, by the above observation, the graph $G$ contains the path $i_1,\ldots,i_\ell$. Thus $G$ is connected. 
%This shows that any marked tree $(T,\mu)\in\oTmn$ is $\mA_m^n$-connected. 
%
%It remains to show that any marked tree in $\oTmn$ satisfies the $\mA_m^n$-cadet condition. This is obvious since, by the above observation, every non-marked cadet-edge $e=\{i,j\}$ of $(T,\mu)$ satisfies $\{x_i-x_j=\driftT(i)-\driftT(j)\}\in \mA_m^n$.
%
%Thus $\oTmn(\mA_m^n)=\oTmn$ as claimed.
%%We observe that for any marked tree $(T,\mu)\in\oTmn$ and any nodes $i,j$ such that $i=s\cadet(j)$ one has 
%%$$\{x_i-x_j=\driftT(i)-\driftT(j)\}=\{x_i-x_j=s\}\in \mA_m^n.$$
%%This clearly implies that any tree $(T,\mu)\in \oTmn$ is $\mA_m^n$-connected. Moreover, $(T,\mu)$ satisfies the $\mA$-cadet condition since for every non-marked cadet-edge $e=\{i,j\}$ of $(T,\mu)$ the hyperplane $\{x_i-x_j=\driftT(i)-\driftT(j)\}$ is in $\mA_m^n$. Thus $(T,\mu)$ is in $\oTmn(\mA_m^n)$, and $\oTmn(\mA_m^n)=\oTmn$ as wanted.
%\end{proof}
%
%
%The other family of arrangements treated in \cite{Levear} consists of the \emph{$m$-Shi arrangements}
%$$\mShi_m^n=\mA_{[-m+1;m]}^n=\bigcup_{\substack{1\leq i<j\leq n\\s\in[-m+1;m]}}\{x_i-x_j=s\}.$$
%It is easy to check that the arrangement $\mShi_m^n$ is strongly transitive. Applying Theorem~\ref{thm:main} we recover the following result of \cite{Levear} about Shi arrangements.
%\begin{cor}[\cite{Levear}]\label{cor:Shi}
%Let $m,n> 0$. The faces of the $m$-Shi arrangement $\mShi_m^n$ (of codimension $k$) are in bijection with the set of marked trees $(T,\mu)$ in $\oTmn$ (having $k$ marked edges) such that if $i=m\child(j)$ for some nodes $i,j\in [n]$ of $T$, then $i<j$.
%\end{cor}

%%
%%\begin{proof}
%%We apply Theorem~\ref{thm:main} to the strongly transitive arrangement $\mShi_m^n$, and need to check that $\oTmn(\mShi_m^n)$ is the set $\mS$ of marked trees $(T,\mu)$ in $\oTmn$ such that if $i=m\child(j)$ for some nodes $i,j\in [n]$ of $T$, then $i<j$. Before starting this proof, let us observe that for any marked tree $(T,\mu)\in\oTmn$ and any nodes $i,j$ such that $i=s\cadet(j)$ the hyperplane
%%$\{x_i-x_j=\driftT(i)-\driftT(j)\}=\{x_i-x_j=s\}$ is in $\mA$ unless $s=m$ and $i>j$. 
%%
%%
%%Now we will determine under which condition a marked tree $(T,\mu)\in\oTmn$ is $\mS_n$-connected.
%% Let $B$ be a block of $(T,\mu)$, and let $G$ with vertex set $B$ and edge set 
%%$$E=\{\{i,j\}\mid i,j\in B,~\{x_i-x_j=\driftT(i)-\driftT(j)\}\in \mS_n\}.$$
%%Recall that $B$ is of the form $B=\{i_1,\ldots,i_\ell\}$, with $i_{j+1}=s_j\cadet(i_j)$ for some $s_j\leq m$. By the above we have $\{i_j,i_{j+1}\}\in E$ whenever $s_j<m$. 
%%Hence the graph $G$ is connected if and only if for all $j<k$ such that $i_{j+1}=m\cadet(i_j)$ there exist $j'\leq j$ and $j''>j$ such that the edge $\{i_{j'},i_{j''}\}$ is in $E$. This holds if and only if $\driftT(i_{j'})=\driftT(i_j)$, $\driftT(i_{j''})=\driftT(i_{j+1})$ (so that $\driftT(i_{j''})-\driftT(i_{j'})=m$) and $i_{j'}>i_{j''}$ (so that $\{i_{j'},j_{j''}\}\in E$). Moreover, $\driftT(i_{j'})=\driftT(i_j)$ and $j'\leq j$ imply $i_{j'}\leq i_j$ (since $T\in \mTmn$) and $\driftT(i_{j''})=\driftT(i_{j+1})$ and $j''\geq j+1$ imply $i_{j''}\geq i_{j+1}$ (since $T\in \mTmn$). Hence there exists $j'\leq j$ and $j''>j$ satisfying the above conditions if and only if $i_{j}>i_{j_{j+1}}$. 
%%This shows that a marked tree $(T,\mu)\in\oTmn$ is $\mShi_m^n$-connected if and only if for all marked edge $\{i,j\}$ such that $i=m\child(j)$ one has $i<j$.
%% 
%%A similar reasoning shows that $(T,\mu)$ satisfies the $\mA$-cadet condition if and only if for any non-marked edge $\{i,j\}$ with $i=m\child(j)$ one has $i<j$. This proves that $\oTmn(\mShi_m^n)=\mS$ as claimed.
%%\end{proof}


%
%In order to prove of Corrolary~\ref{cor:Shi}, it suffices to show that the set of marked trees described there corresponds precisely to the set $\oTmn(\mShi_m^n)$. Instead of giving this proof right away, we will first present a more general result that interpolates between the case of the Catalan arrangements and the case of the Shi arrangements.
%
Observe that, for all $m,n>0$,, any arrangement $\mA$ such that $\mA_{m-1}^n\subseteq \mA \subseteq\mA_m^n$ is strongly transitive. We now describe a family of arrangements $\mA$ which interpolates between $\mA_{m-1}^n$ and $\mA_{m}^n$ and for which the set $\oTmn(\mA)$ admits a simple description.

Let $$R_n:=\{(i,j)\in [n]^2\mid i\neq j\}~\textrm{ and }~R_n^+:=\{(i,j)\in [n]^2\mid i<j\}.$$ 
For a subset $I\subseteq R_n$ we define the arrangement
$$\mB_{m,I}^n=\mA_{m-1}^n\cup\bigg(\bigcup_{(i,j)\in I}\{x_i-x_j=m\}\bigg).$$ 
Note that $\mA_{m-1}^n=\mB_{m,\emptyset}^n$, $\mA_{m}^n=\mB_{m,R_n}^n$, and $\mShi_{m}^n=\mB_{m,R_n^+}^n$.

We say that $I\subseteq R_n$ is an \emph{ideal} if the following holds for all $(i,j),(i',j')\in R_n$:\\
\centerline{if $(i,j)$ is in $I$ and $i'\leq i$ and $j'\geq j$, then $(i',j')$ is in $I$.}
Note that $\emptyset$, $R_n$ and $R_n^+$ are ideals.

\begin{thm}\label{thm:Cat2Shi} 
Let $m,n$ be positive integers. For any ideal $I\subseteq R_n$, the faces (of codimension $k$) of the arrangement $\mA=\mB_{m,I}^n$ are in bijection, via the bijection $\bPhi_\mA$, with the set of marked trees $(T,\mu)\in \oTmn$ (with $k$ marked edges) such that if $i=m\child(j)$ for some nodes $i,j\in [n]$ of $T$, then $(i,j)$ is in $I$.
\end{thm}

Note that Theorem~\ref{thm:Cat2Shi} generalizes both Corollary~\ref{cor:Cat} (which corresponds to $I=R_n$) and Corollary~\ref{cor:Shi} (which corresponds to $I=R_n^+$). 
%
%\begin{rk}
%It is easy to see that there exist ideals 
%$$\emptyset =I_0\subset I_1\subset I_2\cdots \subset I_{\binom{n}{2}}=R_n^+ \subset \cdots\subset I_{n(n-1)}=R_n,$$
%such that $|I_j\setminus I_{j-1}|=1$ for all $i\in [n(n-1)]$. Hence, upon denoting $\mB_p=\mB_{m,I_p}^n$ for all $p\in[0;n(n-1)]$, one gets a sequence of strongly transitive arrangements $\mB_0,\ldots,\mB_{n(n-1)}$ for which Theorem~\ref{thm:Cat2Shi} applies and such that 
%$$\mB_{0}=\mA_{m-1}^n,\quad \quad \mB_{\binom{n}{2}}=\mShi_m^n, \quad \quad \mB_{n(n-1)}=\mA_m^n,$$
%and for all $p\in[n(n-1)]$, $\mB_{p}$ is obtained from $\mB_{p-1}$ by adding a single hyperplane.
%\end{rk}

\begin{proof}
We apply Theorem~\ref{thm:main} to the strongly transitive arrangement $\mA=\mB_{m,I}^n$, and need to check that $\oTmn(\mA)$ is the set $\mS$ of marked trees $(T,\mu)$ in $\oTmn$ such that if $i=m\child(j)$ for some nodes $i,j\in [n]$ of $T$, then $(i,j)$ is in $I$. Before starting this proof, let us observe that for any marked tree $(T,\mu)\in\oTmn$ and any nodes $i,j$ such that $i=s\cadet(j)$ the hyperplane
$\{x_i-x_j=\driftT(i)-\driftT(j)\}=\{x_i-x_j=s\}$ is in $\mA$ unless $s=m$ and $(i,j)\notin I$. 


Now we will determine under which conditions a marked tree $(T,\mu)\in\oTmn$ is $\mA$-connected.
 Let $B$ be a block of $(T,\mu)$, and let $G$ be the graph with vertex set $B$ and edge set 
$$E=\{\{i,j\}\mid i,j\in B~\textrm{such that}~\{x_i-x_j=\driftT(i)-\driftT(j)\}\in \mA\}.$$
Recall that $B$ is of the form $B=\{i_1,\ldots,i_\ell\}$, where for all $k\in [\ell-1]$, $i_{k+1}=s_k\cadet(i_k)$ for some $s_k\leq m$. By the above observation, the edge $\{i_k,i_{k+1}\}$ is in $E$ whenever $s_k<m$. 
Hence the graph $G$ is connected if and only if for all $k\in[\ell-1]$ such that $i_{k+1}=m\cadet(i_k)$ there exist $k'\leq k$ and $k''\geq k+1$ such that $\driftT(i_{k'})=\driftT(i_k)$ and $\driftT(i_{k''})=\driftT(i_{k+1})$ (so that $\driftT(i_{k''})-\driftT(i_{k'})=m$) and $(i_{k''},i_{k'})\in I$ (so that $\{i_{k''},i_{k'}\}\in E$). 
%the edge $\{i_{j'},i_{j''}\}$ is in $E$. This holds if and only if $\driftT(i_{j'})=\driftT(i_j)$ and $\driftT(i_{j''})=\driftT(i_{j+1})$ (so that $\driftT(i_{j''})-\driftT(i_{j'})=m$) and $(i_{j'},i_{j''})\in I$ (so that $\{i_{j'},i_{j''}\}\in E$). 
Moreover, $\driftT(i_{k'})=\driftT(i_k)$ and $k'\leq k$ imply $i_{k'}\leq i_k$ (since $(T,\mu)\in \oTmn$) and similarly $\driftT(i_{k''})=\driftT(i_{k+1})$ and $k''\geq k+1$ imply $i_{k''}\geq i_{k+1}$. Hence, there exists $k'$ and $k''$ satisfying the above conditions if and only if $(i_{k+1},i_{k})\in I$ (because $I$ is an ideal). 
This shows that a marked tree $(T,\mu)\in\oTmn$ is $\mA$-connected if and only if $(i,j)$ is in $I$ for every marked edge $\{i,j\}$ such that $i=m\child(j)$.
 
A similar reasoning shows that $(T,\mu)$ satisfies the $\mA$-cadet condition if and only if $(i,j)$ is in $I$ for every non-marked edge $\{i,j\}$ such that $i=m\child(j)$.
\end{proof}

%In the next section we apply Theorem~\ref{thm:main} to additional families of hyperplane arrangements which generalize the Catalan and Shi arrangements.




\subsection{Multi-Catalan arrangements}
Let $n$ be a positive integer. Given a $n$-tuple of integers $\mm=(m_1,\ldots,m_n)\in \NN^n$, we define the \emph{$\mm$-Catalan arrangement} as
$$\mA_\mm:=\bigcup_{\substack{1\leq i<j\leq n\\ s\in [-m_i;m_j]}}\{x_i-x_j=s\}.$$
%It is easy to see that the arrangement $\mA_\mm$ is strongly transitive for all $\mm\in \NN^n$.
 %We want to describe the set of trees indexing its faces via the bijection $\Phi_{\mA_\mm}$. Let $m=\max(m_i\mid i\in[n])$.
Given a marked tree $(T,\mu)\in \oTmn$, we define the \emph{$\mm$-reach} of a node $j\in[n]$ of $T$ as
$$r_\mm(j):=\max(m_{k}+\driftT(k)-\driftT(j)\mid k\musim j\textrm{ and }k\textrm{ ancestor of }j).$$
%Note that $r_\mm(j)\geq m_j$ (since $j$ is considered an ancestor of itself). 
It is easy to see that $\mA_\mm$ is strongly transitive for all $\mm\in \NN^n$, and that applying Theorem~\ref{thm:main} gives the following bijection.

\begin{prop}
Let $n$ be a positive integer, let $\mm=(m_1,\ldots,m_n)\in \NN^n$, and let $m=\max(m_i\mid i\in[n])$. 
The faces of the $\mm$-Catalan arrangement $\mA_\mm$ are in bijection with the set of marked trees $(T,\mu)\in \oTmn$ such that for every node $j\in[n]$, the vertex $s\child(j)$ is a leaf for all $s>r_\mm(j)$.
\end{prop}
%We omit the proof.




\subsection{Generating function for symmetric transitive arrangements}
\label{sec:GF}
In this section we focus on \emph{symmetric} braid-type arrangements, that is, braid-type arrangements $\mA$ such that $\pi(\mA)=\mA$ for all $\pi\in \fS_n$. It is easy to see that the symmetric braid-type arrangements are the arrangements of the form $\mA_S^n$ for a set $S\subseteq \ZZ$ such that $S=-S$. 
%(where $-S=\{-s\mid s\in S\}$).
From Lemma~\ref{lem:transitive-sets}, one gets that the strongly transitive symmetric arrangements in dimension $n\geq 3$ are precisely the arrangements of the form $\mA_S^n$, where the set $S\subseteq\ZZ$ satisfies 
\begin{equation}\label{eq:condition-sym-trans}
S=-S\textrm{ and }~ \forall s,t\in \NN\setminus S, \quad s+t\notin S.
\end{equation}


Given a finite set $S$, we define the \emph{face generating function} of the arrangements $\mA_S^n$ as 
$$F_{S}(x,t):=\sum_{n=0}^\infty \sum_{k=0}^{n}c_{n,k} t^k \frac{x^n}{n!},$$
where $c_{n,k}$ is the number of faces of codimension $k$ of $\mA_{S}^n$. 
Applying Theorem~\ref{thm:main} gives the following result for any finite set $S\subseteq \ZZ$ satisfying~\eqref{eq:condition-sym-trans}:
%\begin{cor}\label{cor:thmGF}
%Let $S\subseteq \ZZ$ be a finite set satisfying~\eqref{eq:condition-sym-trans}. Then,% face generating function $F_S$ is equal to
$$F_S(x,t)=\sum_{(T,\mu)\in \oT(S)}t^{|\mu|}\frac{x^{|T|}}{|T|!},$$
where $\oT(S):= \bigcup_{n=0}^\infty \oTmn(\mA_S^n)$, $|T|$ is the number of nodes of the tree $T$, and $|\mu|$ is the number of marked edges.
%\end{cor}
Using this expression one can establish the following result:
\begin{thm}\label{thm:GF}
Let $S\subset \ZZ$ be a finite set satisfying~\eqref{eq:condition-sym-trans}.
The face generating function $F_S(x,t)$ is characterized by a finite equation, which is computable from $S$. This equation takes the form $P(F_S(x,t),e^{xt},e^x,t)=0$ for some (non-zero) polynomial $P$ with coefficients in $\QQ$. %If $0\in S$ then the equation is actually of the form $P(F_S(x,t),e^{xt},t)=0$.
\end{thm}

We omit the (non-trivial) proof of Theorem~\ref{thm:GF}. Let us write down two cases explicitly: the case of $m$-Catalan arrangements for which a generating function equation was established by Levear~\cite{Levear}, and the case of the semiorder arrangement (which is new).
\begin{prop}[\cite{Levear}]
The generating function $G\equiv F_{[-m;m]}(x,t)$ counting the faces of the $m$-Catalan arrangements is characterized by the following equation: 
$$G=1+\frac{1}{t}\Om(e^{xt}-1,F),~\textrm{ where }~\Om(X,Y)=\frac{XY^{m+1}}{1-XY\frac{1-Y^m}{1-Y}}.$$
\end{prop}

\begin{prop}
The generating function $H\equiv F_{[-m;m]\setminus \{0\}}(x,t)$ counting the faces of the $m$-extended semiorder arrangements is characterized by the following equation: 
$$H=1+(1-e^{-x})H^{m+1}+\frac{1}{t}\tilde\Om(e^{xt}-1,H),
~\textrm{ where }~\tilde\Om(X,Y)=X^2\frac{Y^{m+2}-Y^{2m+2}}{1-Y-XY+XY^{m+1}}.$$
\end{prop}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Proof of \texorpdfstring{Theorem~\ref{thm:main}}{the main theorem} (sketch)}\label{sec:proof}
In this section we sketch the proof Theorem~\ref{thm:main}.
Roughly speaking, the proof consists in seeing the faces of an arrangement $\mA\subseteq \mA_m^n$ as the regions of the restrictions of~$\mA$ to each subspace in the intersection lattice, and applying Theorem~\ref{thm:regions} to these arrangements.

Recall that the \emph{intersection lattice} of $\mA$ is
%$\mL(\mA)$ of $\mA$ is the set of non-empty intersections of hyperplanes in $\mA$:
$$\mL(\mA):=\bigg\{\bigcap_{i=1}^k H_i~\bigg|~ k\geq 0,H_1,\ldots,H_k\in\mA~\textrm{ such that }\bigcap_{i=1}^k H_i\neq \emptyset\bigg\}.$$
For an affine space $L\in \mL(A)$ we want to identify the restriction $\mA_L$ of $\mA$ to $L$ with an arrangement $\wA_L\subseteq \mA_{mn}^d$, where $d=\dim(L)$. 

If $L$ is contained in a hyperplane of the form $\{x_i-x_j=s\}$, we write $i\Lsim j$. This is an equivalence relation, and we denote by $\blocks(L)$ the set of equivalence classes. Let $\{B_1,\ldots,B_d\}=\blocks(L)$. %Next, we define a linear order $\precL$ within each block $B_k$ as follows: for $i,j\in B_k\subseteq[n]$, we set $i\precL j$ if for any point $(x_1,\ldots,x_n)$ in $L$ one has $x_i<x_j$ or ($x_i=x_j$ and $i<j$). 
%For all $i\in [n]$, we denote by $i_L$ the minimal element (for the order $\precL$) of the block $B_k$ containing $i$, and we denote by $\de_L(i)\in \NN$ the value of $x_i-x_{i_L}$ inside the affine space $L$. 
For all $i\in [n]$ we define $\de_L(i)=\max(x_i-x_{j}\mid j\Lsim i)$ for any point $(x_1,\ldots,x_n)$ in $L$. 
Finally, we define the arrangement $\wA_L\subseteq \RR^d$ as follows: 
\begin{equation}\nonumber %\label{eq:AL}
\wA_L:=\bigcup_{\substack{k,\ell\in[d]\\ k\neq \ell}} ~~\bigcup_{\substack{ i\in B_k,~ j\in B_\ell,~s\in\ZZ\\ \{x_i-x_j=s\}\in \mA}} \{x_k-x_\ell=s-\de_L(i)+\de_L(j)\}.
\end{equation}
It is easy to check that the arrangements $\mA_L$ and $\wA_L$ are isomorphic, and that $\wA_L\subseteq \mA_{mn}^d$, where $d=\dim(L)$.
A key observation (whose proof we omit) is the following.

\begin{lemma}\label{lem:strongly-transitive-good}
If $\mA\subseteq \mA_\infty^n$ is strongly transitive, then for any affine space $L$ in $\mL(\mA)$, the arrangement $\wA_L$ is strongly transitive.
\end{lemma}


%
%We can now describe the proof of Theorem~\ref{thm:main} more precisely. We want to prove that, for any strongly transitive arrangement $\mA$, the map $\bPhi_\mA$ is a bijection between the set $\Tmn(\mA)$ of marked trees and the set $\mF(\mA)$ of faces. We introduce two related sets:
%\begin{eqnarray*}
%\wt{\mT}(\mA)&:=&\left\{\left(L,\wt{T}\right)\mid L\in \mL(\mA),~\wt{T}\in\Tmnd(\wA_L)\right\}\\
%\wt{\mF}(\mA)&:=&\left\{\left(L,\wt{R}\right)\mid L\in \mL(\mA),~\wt{R}\in \mR(\wA_L)\right\}.
%\end{eqnarray*}
The proof of Theorem~\ref{thm:main} consists in establishing the commutative diagram of bijections represented in Figure~\ref{fig:diagramproof}, where $\mF(\mA)$ is the set of faces of $\mA$ and
\begin{align*}
    \wt{\mT}(\mA) & := \{(L,\wt{T})\mid L\!\in\! \mL(\mA),~\wt{T}\!\in\!\mT_{mn}^{\dim(L)}(\wA_L)\}, \\
    \wt{\mF}(\mA) & := \{(L,\wt{R})\mid L\!\in\! \mL(\mA),~\wt{R}\!\in\! \mR(\wA_L)\}.
\end{align*}

\begin{figure}[!ht]%\begin{center}
\[
\begin{tikzcd}
(T,\mu)\in\oTmn(\mA) \arrow[d, "\textrm{bijection }\Gamma"']\arrow[rrr,"\bPhi_\mA"] &&& F\in \mF(\mA)\\
\left(L,\wt{T}\right)\in\wt{\mT}(\mA) \arrow[rrr,"\textrm{bijection }\wt{\Phi}_\mA"'] &&& \left(L,\wt{R}\right)\in \wt{\mF}(\mA)\arrow[u, "\textrm{bijection }\Theta"]
\end{tikzcd}
\]
\caption{Commutative diagram representing the proof of Theorem~\ref{thm:main}.}\label{fig:diagramproof}
\end{figure}

\newcommand{\wTmA}{\wt{\mT}(\mA)}

We start by defining $\wt{\Phi}_\mA:\wt{\mT}(\mA)\to\wt{\mF}(\mA)$ as the map which associates to each pair $(L,\wt{T})\in\wTmA$ the pair $(L,\Phi_{\wA_L}(T))\in \wt{\mF}(\mA)$. 
By combining Lemma~\ref{lem:strongly-transitive-good} with Theorem~\ref{thm:regions} from~\cite{OB}, we deduce that $\wt{\Phi}_\mA$ is a bijection between the sets $\wt{\mT}(\mA)$ and $\wt{\mF}(\mA)$.
 It is also clear that the sets $\wt{\mF}(\mA)$ and $\mF(\mA)$ are in bijection. 
 %Indeed, the faces of $\mA$ (of dimension $d$) correspond to the regions of the restrictions of $\mA$ to subspaces (of dimension $d$) in the intersection lattice $\mL(\mA)$. 
It remains to describe the bijection $\Gamma$ between $\oTmn(\mA)$ and $\wt{\mT}(\mA)$. We first need to encode the subspaces in $\mL(\mA)$.

%, and to check that the diagram in Figure~\ref{fig:diagramproof} is commutative.
%Before describing the bijection $\Gamma$, we mention without proof a property satisfied by the arrangements of the form $\wA_L$.


%
%
%The previous lemma together with Theorem~\ref{thm:regions} from \cite{OB} immediately give the following result.
%% to encode the regions of $\mA_L$ (that is, the faces of $\mA$ of dimension $\dim(L)$ inside $L$) by some trees in $\oTmn(\mA)$. 
%\begin{cor}\label{cor:facesL}
%Let $\mA\subseteq\mA_m^n$ be a strongly transitive arrangement, and let $L\in \mL(\mA)$ be a subspace. The faces of $\mA$ of dimension $d=\dim(L)$ contained in $L$ are in bijection with the the set of trees $\Tmnd(\wA_L)\subseteq\mT_{mn}^d$. The bijection is given by $\psi_L^{-1}\circ\Phi_{\wA_L}$. 
%\end{cor}

% Before we move to the next step of the proof, we establish an additional property satisfied by the arrangements $\wA_L$.



%Our next step is to encode the elements of the intersection lattice $\mL(\mA)$.
\begin{definition}\label{def:A-connected-partition}
Let $\mA\subseteq \mA_m^n$, let $B\subseteq [n]$ be a set, and let $\de:[n]\to \NN$ be a map. The pair $(B,\de)$ is called \emph{$\mA$-connected} if the graph $G$ with vertex set $B$ and edge set 
$\ds E:=\{\{i,j\}\mid i,j\in B,~\{x_i-x_j=\de(i)-\de(j)\}\in \mA\}$ 
is connected.
We define $\mP(\mA)$ as the set of pairs $(\{B_1,\ldots,B_d\},\de)$, where $\{B_1,\ldots,B_d\}$ is a partition of~$[n]$ and $\de:[n]\to \NN$ is a map such that, $\forall k\in[d]$, $\min(\de(i)\mid i \in B_k)=0$ and $(B_k,\de)$ is $\mA$-connected.
\end{definition}

%It is not hard to prove the following:

\begin{lemma}\label{lem:code-subspace}
Let $\mA\subseteq \mA_m^n$. The lattice $\mL(\mA)$ is in bijection with $\mP(\mA)$.
 The bijection $\Lambda:\mL(\mA)\to\mP(\mA)$ associates to each affine subspace $L\in\mL(A)$ the pair $\Lambda(L)=(\blocks(L),\de_L)$. 
 %The inverse bijection is the map $\De:\mP(\mA)\to \mL(\mA)$ defined by 
%$$\De(\{B_1,\ldots,B_d\},\de)=\bigcap_{k=1}^d\bigcap_{\substack{(i,j,s)\in \trmn(\mA)\\ i,j\in B_k,~s=\de(i)-\de(j)}}\{x_i-x_j=s\}.$$
\end{lemma}
%
%\begin{proof}
%Let us first check that for any subspace $L$ in $\mL(\mA)$, the pair $(\blocks(L),\de_L)$ is in $\mP(\mA)$. The only non-trivial point is to check that every block of the set partition $\{B_1,\ldots,B_d\}=\blocks(L)$ is $\mA$-connected. Let $k\in[d]$, and let $G=(B_k,E)$ be the graph associated to $(B_k,\de_L)$ in Definition~\ref{def:A-connected-partition}. Let $i,j\in B_k$. Since $i,j$ are in the same block of the partition $\blocks(L)$, we know that $L$ is included in a hyperplane of the form $\{x_i-x_j=s\}$ for some $s\in \ZZ$. Since $L\in\mL(\mA)$, this inclusion implies the existence of some indices $i=i_0,i_1,\ldots,i_q=j$ and some integers $s_1,\ldots,s_q$ such that 
%$$L\subseteq \{x_{i_{p-1}}-x_{i_p}=s_p\}\in \mA$$ 
%for all $p\in[q]$. Hence, the indices $i=i_0,i_1,\ldots,i_q=j$ are all in $B_k$ and the edge $\{i_{p-1},i_p\}$ is in $E$ for all $p\in[q]$. This shows that $i$ and $j$ are connected by the path $i_0,i_1,\ldots,i_{q}$ in $G$. Hence every block of the set partition $\{B_1,\ldots,B_d\}=\blocks(L)$ is $\mA$-connected, and $\Lambda(L)=(\blocks(L),\de_L)$ is in $\mP(\mA)$. 
%
%Next we note that the map $\Lambda:\mL(\mA)\to \mP(\mA)$ is injective. Indeed, if it clear that an affine space $L\in \mL(\mA)$ is contained in a hyperplane $\{x_i-x_j=s\}$ of $\mA$ if and only if $i,j$ are in the same block of the partition $\blocks(L)$ and $s=\de_L(i)-\de_L(j)$. Thus $L$ can be recovered from $\Lambda(L)=(\blocks(L),\de_L)$.
%
%Lastly, one can check that $\Lambda\circ\de=\Id_{\mP(\mA)}$. Indeed, for a pair $(\{B_1,\ldots,B_d\},\de)\in \mP(\mA)$, and $L=\De(\{B_1,\ldots,B_d\},\de)$, the assumption that each block $B_k$ is $\mA$-connected ensures that $\blocks(L)=\{B_1,\ldots,B_d\}$, and it follows without difficulty that $\Lambda(L)=(\{B_1,\ldots,B_d\},\de)$. 
%
%Thus, $\Lambda$ is a bijection, and $\de$ is the inverse bijection.
%\end{proof}


%We are ready to describe the bijection $\Gamma$ from $\oTmn(\mA)$ to $\mTmA$. 
Given a marked tree $(T,\mu)\in\oTmn(\mA)$, we consider the set partition $\{B_1,\ldots,B_d\}=\blocks(\mu)$ with the convention $\min(B_1)<\min(B_2)<\cdots<\min(B_d)$. 
%Each block $B_k$ corresponds to a path of marked edges in $(T,\mu)$ and we let $a_k\in B_k$ be the node of $T$ which is the ancestor of all the other nodes in $B_k$. We define a map $\de_\mu:[n]\to \NN$ by setting $\de_\mu(i)=\driftT(i)-\driftT(a_k)$ for all $i\in B_k$. 
We define a map $\de_\mu:[n]\to \NN$ by setting $\de_\mu(i)=\max(\driftT(i)-\driftT(j)\mid j\in B_k)$ for all $i\in B_k$. 
By definition, each block $B_k$ is $\mA$-connected (see Definition~\ref{def:A-connected-tree}), which is equivalent to the fact that the pair $(B_k,\de_\mu)$ is $\mA$-connected (see Definition~\ref{def:A-connected-partition}). Thus, the pair $(\{B_1,\ldots,B_d\},\de_\mu)$ is in $\mP(\mA)$, and corresponds to a subspace $L\in \mL(\mA)$ via the bijection $\Lambda$ of Lemma~\ref{lem:code-subspace}. 
%Observe that, by Remark~\ref{rk:eqL}, 
%$$L=\bigcap_{\substack{\{i,j\}\in \mu \\ i=s\child(j)}}\{x_i-x_j=s\}.$$
Now consider the tree $\wt T$ obtained from $T$ by 
\bitem
\item[1.] contracting all the marked edges: for all $k\in[d]$, the marked path of $T$ corresponding to $B_k$ is replaced by a node of $\wT$ labeled $k$, 
\item[2.] adding leaves as right children of each node of $\wT$ so as to get a total of $mn+1$ children for each node. 
\eitem
We define $\Gamma(T,\mu):=(L,\wt T)$. This is illustrated in Figure~\ref{fig:contraction-tree}.


\fig{width=\linewidth}{contraction-tree}{The bijection $\Gamma$.}


In order to conclude the proof of Theorem~\ref{thm:main}, one needs to check that $\wt T$ is in $\Tmnd(\wA_L)$ (there is a technical subtlety there), and that any tree in $\Tmnd(\wA_L)$ is obtained uniquely in this manner. 
%We mention that a technical lemma is need to show that $\wt T\in\Tmnd(\wA_L)$:
%\begin{lemma}\label{lem:cadet-condition-simple}
%Let $\mA$ be a strongly transitive arrangement. Let $L\in\mL(\mA)$ and let $\{B_1,\ldots,B_d\}=\blocks(L)$. Let $\ell\in [d]$ and let $\de^\ell=\max(\de_L(j)\mid j\in B_\ell)$. Then, for all $k\in[d]\setminus\{\ell\}$ and all $t\in[0; \de^\ell]$, one has $\{x_k-x_\ell=t\}\in \wA_L$ unless $|B_k|=|B_\ell|=1$.
%\end{lemma}
Lastly, one must show that the diagram in Figure~\ref{fig:diagramproof} is commutative.
% In other words, one needs to show that $\bPhi_\mA=\Theta\circ \wt \Phi_\mA\circ \Gamma$. 
%We omit the proof of these facts.

%\bigskip
%\noindent{\bf Conflict of interest statement:} The authors have no conflict of interest to disclose in relation to this article.\\
%
%\smallskip
%\noindent{\bf Acknowledgments:} This work was supported by NSF Grant DMS-2154242.
%
%
%\bibliographystyle{alpha}
%\bibliography{biblio-hyperplanes}

\printbibliography



\end{document}

