%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{136}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{picins}
\usepackage{xargs}
\usepackage{amsfonts, dsfont}
\usepackage{paralist}
\usepackage{afterpage}
\usepackage{multirow}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

%% define your title in the usual way
\title{Diagonals of permutahedra and associahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~Bostan, F.~Chyzak, B.~Delcroix-Oger, G.~Laplante-Anfossi, V.~Pilaud, and K.~Stoeckl]{\texorpdfstring{
	Alin Bostan\thanks{\href{mailto:alin.bostan@inria.fr}{alin.bostan@inria.fr}. Supported by the French ANR grant DeRerumNatura (ANR-19-CE40-0018) and by the French--Austrian project EAGLES (ANR-22-CE91-0007 \& FWF I6130-N).}\addressmark{1}\addtocounter{footnote}{1},
	Frédéric Chyzak\thanks{\href{mailto:frederic.chyzak@inria.fr}{frederic.chyzak@inria.fr}. Supported by the French ANR grant DeRerumNatura (ANR-19-CE40-0018) and by the French--Austrian project EAGLES (ANR-22-CE91-0007 \& FWF I6130-N).}\addressmark{1},
	B\'er\'enice Delcroix-Oger\thanks{\href{mailto:berenice.delcroix-oger@umontpellier.fr}{berenice.delcroix-oger@umontpellier.fr}. Supported by the French ANR grants CARPLO (ANR-20-CE40-0007), HighAGT (ANR-20-CE40-0016) and S3 (ANR-20-CE48-0010).}\addressmark{2}, \\
	Guillaume Laplante-Anfossi\thanks{\href{mailto:glaplanteanfossi@imada.sdu.dk}{guillaume.laplanteanfossi@unimelb.edu.au}. Supported by the Australian Research Council Future Fellowship FT210100256 and by the Andrew Sisson Fund.}\addressmark{3},
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@ub.edu}{vincent.pilaud@ub.edu}. Supported by the French--Austrian grant PAGCAP (ANR-21-CE48-0020 \& FWF I 5788), by the Spanish--German project COMPOTE (AEI PCI2024-155081-2 \& DFG 541393733), and by the Spanish grants PID2022-137283NB-C21, 2021 SGR 00697 and CEX2020-001084-M.}\addressmark{4},
	\and
	Kurt Stoeckl\thanks{\href{mailto:kstoeckl@student.unimelb.edu.au}{kstoeckl@student.unimelb.edu.au}. Supported by the Australian Research Council Future Fellowship FT210100256 and an Australian Government Research Training Program (RTP) Scholarship.}\addressmark{5}}{
	Alin Bostan,
	Frédéric Chyzak,
	B\'er\'enice Delcroix-Oger, 
	Guillaume Laplante-Anfossi,
	Vincent Pilaud,
	and
	Kurt Stoeckl}}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}Institut National de Recherche en Informatique et en Automatique, Palaiseau, France \\
	\addressmark{2}Institut Montpelli\'erain Alexander Grothendieck, Universit\'e de Montpellier, France \\
	\addressmark{3}Institut for Matematik og Datalogi, Syddansk Universitet, Odense, Denmark \\
	\addressmark{4}Universitat de Barcelona \& Centre de Recerca Matemàtica, Barcelona, Spain \\
	\addressmark{5}School of Mathematics and Statistics, The University of Melbourne, Victoria, Australia
	}

%% 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 present enumeration formulas for the faces of cellular diagonals of the permutahedra and associahedra. For the former, we use Zaslavsky's theory to count the faces of the hyperplane arrangement obtained as the union of $\ell$ generically translated copies of the braid arrangement. This yields in particular nice formulas for the number of regions and bounded regions in terms of exponentials of generating functions of Fuss--Catalan numbers. For the latter, we use analytic or bijective methods to enumerate Tamari intervals weighted by certain binomial coefficients, leading to a surprisingly simple product formula.}

%% put your French abstract here, or comment this out if you don't have one
\resume{Nous présentons des formules d'énumération pour les faces de diagonales cellulaires des permutaèdres et des associaèdres. Pour les premiers, nous utilisons la théorie de Zaslavsky pour dénombrer les faces de l'arrangement d'hyperplans obtenu comme union de $\ell$ copies de l'arrangement de tresses translatées génériquement. Cela donne en particulier de belles formules pour le nombre de régions et de régions bornées en termes d'exponentielles de fonctions génératrices de nombres de Fuss--Catalan. Pour les seconds, nous utilisons des méthodes analytiques ou bijectives pour énumérer les intervalles de Tamari pondérés par certains coefficients binomiaux, conduisant à une formule produit étonnamment simple.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Diagonals, $f$-vectors, permutahedra, associahedra}

%% 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, giveninits]{biblatex}
\addbibresource{diagonalsFPSAC25.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

% specific commands
\graphicspath{{figures/}}
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition
\newcommand{\resp}{resp.~} % resp
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\ordinal}{\textsuperscript{th}} % th for ordinals
\newcommand{\ordinalst}{\textsuperscript{st}} % st for ordinals
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\Bigset}[2]{\Big\{ #1 \;\Big|\; #2 \Big\}} % big set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\left\langle \, #1 \; \middle| \; #2 \, \right\rangle} % dot product
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \; \big| \; #2 \, \big\rangle} % dot product
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures
\newcommand{\card}[1]{\##1} % cardinality
% math letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\HH}{\mathbb{H}} % hyperplane
\newcommand{\one}{\b{1}} % the all one vector
\renewcommand{\b}[1]{{\boldsymbol{#1}}} % bold letters
% polytopes
\newcommand{\polytope}[1]{\mathds{#1}} % font polytopes
\newcommandx{\Perm}[1][1 = n]{\polytope{P}\mathsf{erm}(#1)} % permutahedron
\newcommandx{\Asso}[1][1 = n]{\polytope{A}\mathsf{sso}(#1)} % associahedron
\newcommandx{\Cube}[1][1 = n]{\polytope{C}\mathsf{ube}(#1)} % cube
\newcommandx{\Simplex}[1][1 = n]{\polytope{S}\mathsf{implex}(#1)} % simplex
\newcommand{\diagonal}{\triangle} % diagonal
% arrangements
\newcommandx{\arrangement}[1][1 = A]{\mathcal{#1}} % arrangement
\newcommandx{\braidArrangement}[1][1 = n]{\arrangement[B]_{#1}} % braid arrangement
\newcommandx{\multiBraidArrangement}[2][1 = n, 2 = \ell]{\arrangement[B]_{#1}^{#2}} % (l,n)-braid arrangement
\newcommandx{\facePoset}[1][1 = \arrangement]{\mathsf{Fa}(#1)} % face poset
\newcommandx{\fPol}[2][1 = \arrangement, 2 = x]{\b{f}_{\!\!#1}(#2)} % face polynomial
\newcommandx{\bPol}[2][1 = \arrangement, 2 = x]{\b{b}_{\!#1}(#2)} % bounded face polynomial
\newcommandx{\flatPoset}[1][1 = \arrangement]{\mathsf{Fl}(#1)} % intersection poset
\newcommandx{\charPol}[2][1 = \arrangement, 2 = y]{\b{\chi}_{\!#1}(#2)} % characteristic polynomial
\newcommandx{\mobPol}[3][1 = \arrangement, 2 = x, 3 = y]{\b{\mu}_{\!#1}(#2, #3)} % Mobius polynomial
\newcommandx{\partitionPoset}[1][1 = n]{\b{\Pi}_{#1}} % partition poset
\newcommandx{\forestPoset}[2][1 = n, 2 = \ell]{\b{\Phi}_{#1}^{#2}} % partition forest poset
% others
\DeclareMathOperator{\des}{des} % descents
\DeclareMathOperator{\asc}{asc} % ascents
\newcommand{\OEIS}[1]{\cite[{\rm \href{http://oeis.org/#1}{\texttt{#1}}}]{OEIS}}
\newcommand{\Ainf}{\ensuremath{\mathrm{A}_\infty}}

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

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

\section{Introduction}

%The purpose of this article is to study \emph{cellular diagonals} on the \emph{permutahedra} and \emph{associahedra}.
%Such diagonals, and in particular coherent families that are called \emph{operadic diagonals}, are of interest in algebraic geometry and topology: via the theory of Fulton--Sturmfels~\cite{FultonSturmfels}, they give explicit formulas for the cup product on Losev--Manin toric varieties~\cite{LosevManin}; they define universal tensor products of permutadic $\Ainf$-algebras~\cite{LodayRonco-permutads,Markl}; they define a coproduct on permutahedral sets, which are models of two-fold loop spaces~\cite{SaneblidzeUmble}, and their study is needed to pursue the work of H. J. Baues aiming at defining explicit combinatorial models for higher iterated loop spaces~\cite{Baues}; using the canonical projections to the operahedra, associahedra and multiplihedra, they define universal tensor products of homotopy operads, $\Ainf$-algebras and $\Ainf$-morphisms, respectively~\cite{LaplanteAnfossi,LaplanteAnfossiMazuir}.

\emph{Cellular diagonals} (\Cref{def:cellularDiagonal}) for face-coherent families of polytopes are a fundamental object in algebraic topology. 
The Alexander--Whitney diagonal for simplices~\cite{EilenbergMacLane}, and the Serre map for cubes~\cite{Serre}, allow one to define the cup product in singular simplicial and cubical cohomology. 
These two diagonals are also needed in the study of iterated loop spaces~\cite{Baues}, while other diagonals are needed in the study of the homology of fibered spaces~\cite{Saneblidze-freeLoopFibration}. %, SaneblidzeRivera, Proute}. 
In another direction, cellular diagonals allow one to define universal tensor products in homotopical algebra~\cite{LaplanteAnfossi}. 
In the present paper, we study enumerative properties of the diagonals of permutahedra and associahedra.

%The diagonals of associahedra have a rich history.
For the associahedra, the first algebraic diagonals were found in~\cite{SaneblidzeUmble} and later in~\cite{MarklShnider, Loday-diagonal}, while the first topological diagonal was given in~\cite{MasudaThomasTonksVallette} for the realizations of the associahedra of~\cite{Loday, ShniderSternberg}.
The powerful technique of~\cite{FultonSturmfels} using fiber polytopes~\cite{BilleraSturmfels} was re-introduced in~\cite{MasudaThomasTonksVallette} to define a topological diagonal of the associahedra.
We shall call such a diagonal a \emph{geometric diagonal} (\Cref{def:geometricDiagonal}).
One of these geometric diagonals, that we call ``the'' diagonal of the associahedra,  has two remarkable features.
First, it respects the operadic structure of the associahedra (each face of an associahedron is isomorphic to a product of lower-dimensional associahedra).
Second, it satisfies the \emph{magical formula}: the faces in the image of the diagonal are given by the pairs of faces which are comparable in the Tamari order (see \Cref{prop:magicalFormulaAssociahedron} for a precise statement). 

For the permutahedra, the first algebraic diagonal was found in~\cite{SaneblidzeUmble}, while the first topological diagonal was defined in~\cite{LaplanteAnfossi}, building on~\cite{MasudaThomasTonksVallette} and the theory of fiber polytopes~\cite{BilleraSturmfels}.
In fact, this approach was extended to a general theory of geometric diagonals in~\cite{LaplanteAnfossi} and applied to the family of operahedra, which contains the family of permutahedra, and encodes the notion of homotopy operad.
Cellular diagonals of the operahedra do \emph{not} satisfy the magical formula, and the combinatorial difficulty of describing their image is what prompted the development of the theory in~\cite{LaplanteAnfossi}.
%In fact, there is an interesting dichotomy between the families of polytopes which satisfy the magical formula (simplices, cubes, freehedra, associahedra) and those who do not (permutahedra, multiplihedra, operahedra).

This extended abstract presents enumerative formulas for the number of faces of diagonals of permutahedra and associahedra, borrowed from the two preprints~\cite{DelcroixOgerLaplanteAnfossiPilaudStoeckl, BostanChyzakPilaud} and summarized in \Cref{table:formulas}.
While both formulas are combinatorially appealing, the approaches to find and prove these formulas are quite different.

For the associahedra, we exploit the magical formula (\Cref{prop:magicalFormula,prop:magicalFormulaAssociahedron}).
Computing the $f$-vector of the diagonal of the associahedron boils down to enumerating intervals in the Tamari lattice weighted by a binomial coefficient involving some natural additional parameters.
This in turn can be achieved either by analytic methods following a decomposition of Tamari intervals from~\cite{Chapoton1}, or by bijective methods exploiting existing bijections between Tamari intervals and \mbox{planar~maps~\cite{BernardiBonichon, FusyHumbert}} (\Cref{thm:fVectorDiagonalAssociahedron}).

For the permutahedra, we exploit the duality between diagonals of a polytope~$P$ and common refinements of two translated copies of the normal fan of~$P$ (\Cref{prop:diagonalCommonRefinement}).
The $f$-vector of any geometric diagonal of the permutahedron \mbox{is thus the (reverse of) the} \mbox{$f$-vector} of the hyperplane arrangement obtained as the union of two generically translated copies of the braid arrangement.
At no additional cost, we study the arrangement $\multiBraidArrangement$ obtained as the union of $\ell$ generically translated copies of the braid arrangement~$\braidArrangement$ (\Cref{def:multiBraidArrangement}), using Zaslavsky's enumerative theory~\cite{Zaslavsky} (\Cref{thm:Zaslavsky}).
We first observe that the flats of~$\multiBraidArrangement$ are in bijection with \emph{$(\ell,n)$-partition forests}, defined as $\ell$-tuples of (unordered) partitions of~$[n]$ whose intersection hypergraph is a hyperforest (\Cref{def:partitionForests}).
We then derive a summation formula for the M\"obius polynomial of the arrangement~$\multiBraidArrangement$, hence for its number of faces and bounded faces (\Cref{thm:MobiusPolynomialMultiBraidArrangement}) by~\cite{Zaslavsky}.
It simplifies to short closed formulas for the number of vertices and facets of~$\multiBraidArrangement$, involving exponentials of generating \mbox{functions of Fuss--Catalan numbers (\mbox{\Cref{thm:verticesMultiBraidArrangement,thm:characteristicPolynomialMultiBraidArrangement}}).}

Note we must use these two distinct approaches.
On the one hand, the normal fan of the associahedron (and thus the common refinement of two translated copies of this fan) is not defined by a hyperplane arrangement, so that the enumerative tools of~\cite{Zaslavsky} do not apply.
On the other hand, diagonals of the permutahedra do not satisfy the magical formula so that it does not suffice to enumerate intervals of the weak order (and in fact, the latter do not yield nice \mbox{enumerative formulas).}

We refer to~\cite{DelcroixOgerLaplanteAnfossiPilaudStoeckl, BostanChyzakPilaud} for many details and all proofs omitted in this extended abstract. % due to space limitations.

\begin{table}
	\centerline{
		\renewcommand{\arraystretch}{1.8}
		\begin{tabular}{@{}c@{\;}|@{\;}c@{\;}|@{\;}c@{\;}|@{\;}c@{}}
			Simplex & Cube & Associahedron & Permutahedron
			\\
			\hline
			\multirow{2}{*}{\small$\displaystyle (k+1) \binom{n+1}{k+2}$} & \multirow{2}{*}{\small$\displaystyle \binom{n-1}{k} 2^k 3^{n-1-k}$} & \multirow{2}{*}{\small$\displaystyle \frac{\displaystyle 2 \binom{n-1}{k} \binom{4n+1-k}{n+1} }{(3n+1)(3n+2)}$} & \small$\displaystyle f_0 = {n! \, [z^n] \exp \Bigl( \sum\limits_{m \ge 1} \frac{C_m \, z^m}{m} \Bigr)}$ \\[-.2cm]
			& & & \small$f_{n-1} = 2 (n + 1)^{n-2}$
			\\[-.3cm]
			\Cref{rem:magicalFormula} & \Cref{rem:magicalFormula} & \Cref{thm:fVectorDiagonalAssociahedron} & \Cref{thm:fVectorDiagonalPermutahedron,,thm:MobiusPolynomialMultiBraidArrangement,,thm:verticesMultiBraidArrangement,,thm:characteristicPolynomialMultiBraidArrangement}
%			\\[-.1cm]
		\end{tabular}
	}
	\caption{Numbers~$f_k$ of $k$-dim. faces in the diagonals of the $(n-1)$-dim. simplex, cube, associahedron, and permutahedron (for the latter, we just report here~$f_0$~and~$f_{n-1}$).}
	\label{table:formulas}
\end{table}

%\begin{table}
%	\centerline{
%		\begin{tabular}{c|c|c|c}
%			polytope & \# vertices & \# $k$-faces & \# facets \\
%			\hline
%			simplex & & $\displaystyle (k+1) \binom{n+1}{k+2}$ & \\
%			cube & & $\displaystyle \binom{n-1}{k} 2^k 3^{n-1-k}$ & \\
%			associahedron & & $\displaystyle \frac{\displaystyle 2 \binom{n-1}{k} \binom{4n+1-k}{n+1} }{(3n+1)(3n+2)}$ & \\
%			permutahedron & 
%		\end{tabular}
%	}
%\end{table}

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

\section{Cellular diagonals of polytopes}
\label{sec:cellularDiagonalsPolytopes}

We now proceed to define thin, cellular, and geometric diagonals.

\begin{definition} 
\label{def:thinDiagonal}
The \defn{thin diagonal} of a set $X$ is the map~$\smash{\delta : \Bigl\{\begin{array}{ccc} X & \to & X \! \times \! X \\ x & \mapsto & (x,x) \end{array}}$. See \Cref{fig:examplesDiagonals1}\,(left).
\end{definition}

\begin{definition} 
\label{def:cellularDiagonal}
A \defn{cellular diagonal} of a $d$-polytope $P$ is a continuous map ${\Delta : P \to P \! \times \! P}$ where
\begin{compactitem}
\item its image is a union of $d$-dimensional faces of $P\times P$ (\ie it is \defn{cellular}),
\item it agrees with the thin diagonal of~$P$ on the vertices of $P$, and
\item it is homotopic to the thin diagonal of~$P$, relative to the image of the vertices of~$P$. 
\end{compactitem}
See \Cref{fig:examplesDiagonals1}\,(mid.~left).
A cellular diagonal is said to be \defn{face coherent} if its restriction to a face of~$P$ is itself a cellular diagonal for that face. 
\end{definition}

 

\begin{figure}[t]
	\centerline{\scalebox{1.16}{
	\begin{tabular}{@{}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{}}
		\includegraphics[scale=1.2]{diagonalSegment1} &
		\includegraphics[scale=1.2]{diagonalSegment2} &
		\raisebox{-.2cm}{\includegraphics[scale=1]{diagonalSegment3}} &
		\raisebox{-.2cm}{\includegraphics[scale=1]{diagonalSegment4}}
		\\
		\includegraphics[scale=.9]{diagonalTriangle1} &
		\includegraphics[scale=.9]{diagonalTriangle2} &
		\includegraphics[scale=.6]{diagonalTriangle3} &
		\includegraphics[scale=.6]{diagonalTriangle4}	
		\\
		\includegraphics[scale=.9]{diagonalSquarre1} &
		\includegraphics[scale=.9]{diagonalSquarre2} &
		\includegraphics[scale=.6]{diagonalSquarre3} &
		\includegraphics[scale=.6]{diagonalSquarre4}
	\end{tabular}
	}}
	\caption{Cellular diagonals of the segment (top), the triangle (middle) and the square (bottom). For each of them, we have represented the thin diagonal of~$P$ (left, in blue) and a cellular diagonal of~$P$ (mid.~left, in red) both represented in~$P \times P$, the associated polytopal subdivision of~$P$ (mid.~right) and the common refinement of the two copies of the normal fan of~$P$ (right) both represented in~$P$.}
	\label{fig:examplesDiagonals1}
\end{figure}

A powerful geometric technique to define face coherent cellular diagonals on polytopes first appeared in~\cite{FultonSturmfels}, was presented in~\cite{MasudaThomasTonksVallette}, and was fully developed in~\cite{LaplanteAnfossi}.
We give in \Cref{thm:diagonal} the precise (but technical) definition of these diagonals, even though we will only use the characterizations of the faces in their image in \Cref{prop:diagonalCommonRefinement,prop:magicalFormula}.

The key idea is that any vector $\b{v}$ in generic position with respect to $P$ defines a cellular diagonal of $P$.
For a point~$\b{z}$ of $P$, we denote by $\rho_{\b{z}} P \eqdef 2\b{z}-P$ the reflection of $P$ with respect to the point~$\b{z}$.
We first define a notion of genericity with respect to~$P$.

\begin{definition}
The \defn{fundamental hyperplane arrangement}~$\mathcal{H}_P$ of a polytope~$P \subset \R^d$ is the set of all linear hyperplanes of~$\R^d$ orthogonal to the edges of $P\cap \rho_{\b{z}} P$ for all $\b{z} \in P$. 
See \Cref{fig:examplesHyperplanes}.
A vector is \defn{generic with respect to~$P$} if it does not belong to the union of the hyperplanes of the fundamental hyperplane arrangement~$\mathcal{H}_P$.
\end{definition}

\begin{figure}
	\centerline{
		\includegraphics[scale=.28]{HypSimplex.png} \hspace{-.6cm}
		\includegraphics[scale=.32]{HypCube.png} \hspace{-.3cm}
		\includegraphics[scale=.2]{HypAsso.png}
		\includegraphics[scale=.28]{HypPermuto.png}
	}
	\caption{The fundamental hyperplane arrangements of the $3$-dimensional simplex (left), cube (mid.~left), associahedron (mid.~right) and permutahedron (right). The hyperplanes perpendicular to edges of some intersection $P\cap \rho_z P$, which are \emph{not} edges of the polytope~$P$, are colored in blue. Left and rightmost illustrations from~\cite[Figure~12]{LaplanteAnfossi}.}
	\label{fig:examplesHyperplanes}
\end{figure}

In particular, such a vector is not perpendicular to any edge of $P$, and we denote by~$\min_{\b{v}}(P)$ (\resp $\max_{\b{v}}(P)$) the unique vertex of~$P$ which minimizes (\resp maximizes) the scalar product with~$\b{v}$. 
%Note that the datum of a polytope~$P$ together with a vector~$\b{v}$ generic with respect to~$P$ was called \defn{positively oriented polytope} in~\cite{MasudaThomasTonksVallette,LaplanteAnfossi,LaplanteAnfossiMazuir}.

\begin{theorem}
\label{thm:diagonal}
For any vector $\b{v} \in \R^d$ generic with respect to~$P$, the tight coherent section~$\triangle_{(P,\b{v})}$ of the projection $P \times P \to P$ given by~$(\b{x}, \b{y}) \mapsto (\b{x}+\b{y})/2$ selected by the vector~$(-\b{v}, \b{v})$ defines a cellular diagonal of~$P$.
Said differently, we have %$\triangle_{(P,\b{v})}$ is given by
\(
\smash{\triangle_{(P,\b{v})}(\b{z}) \! \eqdef \! \bigl( \min_{\b{v}}(P\cap \rho_{\b{z}} P), \, \max_{\b{v}}(P\cap \rho_{\b{z}} P) \bigr)},
\)
where $\rho_{\b{z}} P \eqdef 2\b{z}-P$ denotes the reflection of~$P$ with respect to the point~$\b{z}$. 
\end{theorem}

\begin{definition}
\label{def:geometricDiagonal}
A \defn{geometric diagonal} of a polytope~$P$ is a diagonal of the form~$\smash{\triangle_{(P,\b{v})}}$ for some vector~$\b{v} \in \R^d$ generic with respect to~$P$.
\end{definition}

Note that the geometric diagonal~$\triangle_{(P,\b{v})}$ only depends on the region of~$\mathcal{H}_P$ containing~$\b{v}$, see~\cite[Proposition~1.23]{LaplanteAnfossi}.

Now the following \defn{universal formula}~\cite[Theorem~1.26]{LaplanteAnfossi} expresses combinatorially the faces in the image of the geometric diagonal~$\smash{\triangle_{(P,\b{v})}}$.
Recall that the \defn{normal cone} of a face~$F$ of a polytope~$P$ in~$\R^d$ is the cone of directions~$\b{c} \in \R^d$ such that the maximum of the scalar product~$\dotprod{\b{c}}{\b{x}}$ over~$P$ is attained for some~$\b{x}$ in~$F$.

\begin{theorem}[{\cite[Theorem~1.26]{LaplanteAnfossi}}]
\label{thm:universalFormula}
Fix a vector $\b{v} \in \R^d$ generic with respect to $P$.
For each hyperplane~$H$ of the fundamental hyperplane arrangement~$\mathcal{H}_P$, denote by~$H^{\b{v}}$ the open half space defined by~$H$ and containing~$\b{v}$.
The faces of~$P \times P$ in the image of the geometric diagonal~$\triangle_{(P,\b{v})}$ are the faces~$F \times G$ where~$F$ and~$G$ are faces of~$P$ such that either the normal cone of~$F$ intersects~$H^{-\b{v}}$ or the normal cone of~$G$ intersects~$H^{\b{v}}$, for each~$H \in \mathcal{H}_P$.
\end{theorem}

The image of $\smash{\triangle_{(P,\b{v})}}$ is a union of pairs of faces $F \times G$ of the Cartesian product~${P \times P}$.
By drawing the polytopes~${(F+G)/2}$ for all pairs of faces $(F,G) \in \triangle_{(P,\b{v})}$, we can visualize~$\triangle_{(P,\b{v})}$ as a polytopal subdivision of $P$.
See \Cref{fig:examplesDiagonals1}\,(mid.~right) and \Cref{fig:examplesDiagonals2}.

\begin{figure}
	\centerline{\scalebox{.97}{
		\includegraphics[scale=.2]{diagonalSimplexGuillaume.png}
		\includegraphics[scale=.23]{diagonalCubeGuillaume.png}
		\includegraphics[scale=.22]{diagonalAssociahedronGuillaume.png}
		\includegraphics[scale=.2]{diagonalPermutahedronGuillaume.png}
	}}
	\caption{The subdivisions induced by cellular diagonals of the $3$-dimensional simplex (left), cube (mid.~left), associahedron (mid.~right), and permutahedron (right). Illustrations from~\cite[Figure~13]{LaplanteAnfossi}.}
	\label{fig:examplesDiagonals2}
\end{figure}

It turns out that the dual of this complex is just the common refinement of two translated copies of the normal fan of~$P$.
See \Cref{fig:examplesDiagonals1}\,(right).
Recall that the \defn{normal fan} of~$P$ is the fan formed by the normal cones of all faces of~$P$.
We thus obtain the following statement, which will be instrumental in \Cref{sec:cellularDiagonalsPermutahedra}.

\begin{proposition}[{\cite[Corollary~1.4]{LaplanteAnfossi}}]
\label{prop:diagonalCommonRefinement}
The inclusion poset on the faces in the image of the diagonal~$\smash{\triangle_{(P,\b{v})}}$ is isomorphic to the reverse inclusion poset on the faces of the common refinement of two copies of the normal fan of~$P$, translated from each other by the vector~$\b{v}$. 
\end{proposition}

Finally, the following statement relates the image of the diagonal~$\triangle_{(P, \b{v})}$ to the intervals of the poset obtained by orienting the graph of~$P$ in direction~$\b{v}$.
This statement and its converse will be fundamental in \Cref{sec:cellularDiagonalsAssociahedra}.

\begin{proposition}[{\cite[Proposition 1.17]{LaplanteAnfossi}}]
\label{prop:magicalFormula}
For any vector $\b{v}$ generic with respect to~$P$, the image of the diagonal~$\triangle_{(P, \b{v})}$ is contained in~$\bigcup F \times G$ where the union ranges over all pairs~$(F,G)$ of faces of~$P$ such that~$\max_{\b{v}}(F) \le \min_{\b{v}}(G)$.
%we have
%\begin{equation}
%\label{eq:magique}
%\Ima\triangle_{(P, \b{v})} \quad \subseteq \bigcup_{\substack{F,G \text{ faces of } P \\ \max_{\b{v}}(F) \, \le \, \min_{\b{v}}(G)}} F \times G .
%\end{equation}
\end{proposition}

\begin{remark}
\label{rem:magicalFormula}
For some polytopes such as the simplices~\cite{EilenbergMacLane}, the cubes~\cite{Serre}, the freehedra~\cite{Saneblidze-freeLoopFibration}, and the associahedra~\cite{MasudaThomasTonksVallette}, the reverse inclusion also holds.
According to~\cite{MasudaThomasTonksVallette}, the resulting equality enhancing~\Cref{prop:magicalFormula} was called the \defn{magical formula} by J.-L. Loday.
This equality simplifies the computation of the $f$-vectors of diagonals.
For instance, the reader is invited to derive that the $f$-vectors of the diagonals of the $(n-1)$-dimensional simplex and cube are given by
\[
f_k(\triangle_{\Simplex}) = (k+1) \binom{n+1}{k+2} % \text{\OEIS{A127717}},
% choose k+2 points of [n] where 2 consecutive are distinguished and might be equal, and the rest is distinct
% this is the same as choosing k+2 points of [n+1], and the position of the consecutive pair of distinguished points among them
% hence (k+1) \binom{n+1}{k+2}
\qquad\text{and}\qquad
f_k(\triangle_{\Cube}) = \binom{n-1}{k} 2^k 3^{n-1-k}. % \text{\OEIS{A038220},}
% choose a < b <= c < d in the boolean lattice such that |b-a| + |d-c| = k.
% choose the positions of the ones in (b-a) + (d-c) => \binom{n}{k}
% choose whether each of this ones is in (b-a) or in (d-c) => 2^k
% choose the values of b and c on the remaining n-k positions to be either 00, 01 or 11 => 3^(n-k)
\]
(The latter diagonals are known as the \emph{Alexander--Whitney} map~\cite{EilenbergMacLane} and \emph{Serre} map~\cite{Serre}).
Polytopes of greater complexity such as the multiplihedra~\cite{LaplanteAnfossiMazuir} or the operahedra~\cite{LaplanteAnfossi}, which include the permutahedra~\cite{DelcroixOgerLaplanteAnfossiPilaudStoeckl}, do not possess this exceptional property, and the $f$-vectors of their diagonals are harder to compute.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\section{Cellular diagonals of permutahedra}
\label{sec:cellularDiagonalsPermutahedra}

Recall that the \defn{permutahedron}~$\Perm$ is the polytope defined equivalently as
\begin{compactitem}
\item the convex hull of the points~$\sum_{i \in [n]} i \, \b{e}_{\sigma(i)}$ for all permutations~$\sigma$ of~$[n]$, %, see \cite{Schoute},
\item the intersection of the hyperplane~$\smash{\HH_n \eqdef \bigset{\b{x} \in \R^n}{{\displaystyle\sum\nolimits_{i \in [n]}} x_i = \binom{n+1}{2}}}$ with the halfspaces~$\smash{\bigset{\b{x} \in \R^n}{{\displaystyle\sum\nolimits_{i \in I}} x_i \ge \binom{\#I+1}{2}}}$ for~${\varnothing \ne I \subsetneq [n]}$. %, see \cite{Rado}.
\end{compactitem}

\medskip
\parpic(8.7cm,3.9cm)(2pt,108pt)[r][b]{\raisebox{-.2cm}{\includegraphics[scale=.5]{braidFan}}\includegraphics[scale=.5]{permutahedronWeakOrder}}
The normal fan of the permutahedron $\Perm$ is the \defn{braid fan}, defined by the \defn{braid arrangement}~$\braidArrangement$ formed by the hyperplanes~$\bigset{\b{x} \in \R^n}{x_i = x_j}$ for all~${1 \le i < j \le n}$.
%The braid fan~$\c{B}_d$ is the normal fan of the permutahedron~$\Perm$.
See on the right.

\medskip
When oriented in the direction \linebreak ${\b{\omega}_n \eqdef (n,\dots,1) - (1,\dots,n)}$, the graph of $\Perm$ is the Hasse diagram of the~\defn{weak order} on permutations of~$[n]$, whose cover relations are transpositions of adjacent~letters.

\medskip
The study of geometric diagonals of the permutahedron was initiated in~\cite{LaplanteAnfossi}.
Such a diagonal does not satisfy the magical formula: some intervals of the weak order do not correspond to faces of the diagonal.
%However, we benefit from the fact that the normal fan of the permutahedron is the braid arrangement to obtain the following statement.
However, we have the following statement.

\begin{theorem}[{\cite[Corollary~4.22]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{thm:fVectorDiagonalPermutahedron}
The $f$-vector of any geometric diagonal~$\diagonal\Perm$ is the reverse of the \mbox{$f$-vector} of the arrangement~$\multiBraidArrangement[n][2]$ obtained as the union of two generically translated copies of the braid arrangement~$\braidArrangement$.
%In particular, $\diagonal\Perm$ has $\smash{\displaystyle n! \, [z^n] \exp \Big( \sum\limits_{m \ge 1} \raisebox{-.15cm}{$\displaystyle\frac{C_m \, z^m}{m}$} \Big)}$ vertices and $2 (n + 1)^{n-2}$ facets, where~$\smash{C_m \eqdef \frac{1}{m+1} \binom{2m}{m}}$ is the Catalan number.
%In particular, $\diagonal\Perm$ has $2 (n + 1)^{n-2}$ facets, ${n!  [z^n] \exp \bigl( \sum\nolimits_{m \ge 1} \frac{C_m \, z^m}{m} \bigr)}$ vertices, and ${(n-1)! [z^{n-1}] \exp \bigl( \sum_{m \ge 1} C_m \, z^m \bigr)}$ internal vertices, where~${C_m \eqdef \frac{1}{m+1} \binom{2m}{m}}$ is the Catalan~number.
Hence, the number of vertices and facets of~$\diagonal\Perm$~are
\[
f_0(\diagonal\Perm) = {n!  [z^n] \exp \bigl( \sum\limits_{m \ge 1} \frac{C_m \, z^m}{m} \bigr)}
\qquad\text{and}\qquad
f_{n-1}(\diagonal\Perm) = 2 (n + 1)^{n-2},
\]

\noindent
where~${C_m \eqdef \frac{1}{m+1} \binom{2m}{m}}$ is the Catalan~number.
See \Cref{table:enumerationDiagonalPermutahedra}.
%\begin{compactitem}
%\item $2 (n + 1)^{n-2}$ facets,
%\item $n \binom{n-1}{k_1} (n-k_1)^{k_1-1} (n-k_2)^{k_2-1}$ facets corresponding to pairs~$(F_1, F_2)$ of faces of the permutahedron~$\Perm$ with~$\dim(F_1) = k_1$ and~$\dim(F_2) = k_2$ (thus~$k_1 + k_2 = n-1$),
%\item $\displaystyle n! \, [z^n] \exp \bigg( \sum_{m \ge 1} \frac{C_m \, z^m}{m} \bigg)$ vertices,
%\item $\displaystyle (n-1)! \, [z^{n-1}] \exp \bigg( \sum_{m \ge 1} C_m \, z^m \bigg)$ internal vertices,
%\end{compactitem}
%where~$\displaystyle C_m \eqdef \frac{1}{m+1} \binom{2m}{m}$ denotes the $m$\ordinal{} Catalan number.
\end{theorem}

\begin{table}[h]
	\centerline{\footnotesize
		\begin{tabular}[t]{c|ccccccccccc}
			$n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $\dots$ & OEIS \\
			\hline
			vertices & $1$ & $3$ & $17$ & $149$ & $1809$ & $28399$ & $550297$ & $12732873$ & $343231361$ & $\dots$ & \OEIS{A213507} \\
			facets & $1$ & $2$ & $8$ & $50$ & $432$ & $4802$ & $65536$ & $1062882$ & $20000000$ & $\dots$ & \OEIS{A007334}
%			int. verts. & $1$ & $1$ & $5$ & $43$ & $529$ & $8501$ & $169021$ & $4010455$ & $110676833$ & $\dots$ & \OEIS{A251568}
		\end{tabular}
	}
%	\caption{The numbers of facets, vertices, and internal vertices of~$\diagonal\Perm$ for~$n \in [9]$.}
	\caption{The numbers of vertices and facets of~$\diagonal\Perm$ for~$n \in [9]$.}
	\label{table:enumerationDiagonalPermutahedra}
\end{table}

\parpic(3.8cm,2.3cm)(-2pt,100pt)[r][b]{\includegraphics[scale=.5]{multiBraidArrangement3}}
In fact, the second part of~\Cref{thm:fVectorDiagonalPermutahedron} extends to $\ell$ copies of the braid arrangement~$\braidArrangement$, and involves relevant combinatorial objects and surprising formulas that we briefly present below.

\begin{definition}[{\cite[Section~1.3]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{def:multiBraidArrangement}
The \defn{$(\ell,n)$-braid arrangement}~$\multiBraidArrangement$ is the arrangement obtained as the union of $\ell$ generically translated copies of the braid arrangement~$\braidArrangement$.
See on the right for an illustration of~$\multiBraidArrangement[2][3]$.
\end{definition}

%To study~$\multiBraidArrangement$, we use the classical enumerative toolbox on hyperplane arrangements.

\begin{definition}
\label{def:facePoset}
Consider a (affine real) hyperplane arrangement~$\arrangement$.
The \defn{faces} of~$\arrangement$ are the closures of the regions of~$\arrangement$ and all their intersections with a hyperplane of~$\arrangement$.
The \defn{$f$-polynomial} and \defn{$b$-polynomial} of~$\arrangement$ are the polynomials~$\fPol \eqdef \sum_{k = 0}^d f_k(\arrangement) \, x^k$ and~$\bPol \eqdef \sum_{k = 0}^d b_k(\arrangement) \, x^k$, where~$f_k(\arrangement)$ and~$b_k(\arrangement)$ respectively denote the numbers of $k$-faces and bounded $k$-faces of~$\arrangement$.
\end{definition}

\begin{definition}
\label{def:flatPoset}
Consider an arrangement~$\arrangement$.
A \defn{flat} of~$\arrangement$ is a non-empty affine subspace of~$\R^d$ that can be obtained as the intersection of some hyperplanes of~$\arrangement$.
The \defn{flat poset} of~$\arrangement$ is the poset of flats of~$\arrangement$ ordered by reverse inclusion.
The \defn{M\"obius polynomial} of~$\arrangement$ is the polynomial
\[
\mobPol \eqdef \sum_{F \supseteq G} \mu(F,G) \, x^{\dim(F)} \, y^{\dim(G)},
\]
where~$F \supseteq G$ ranges over all intervals of the flat poset of~$\arrangement$, and~$\mu(F,G)$ is the \defn{M\"obius function} on the flat poset of~$\arrangement$ defined by~$\mu(F, F) = 1$ and~$\smash{\sum\nolimits_{F \supseteq G \supseteq H} \mu(F,G) = 0}$ for all~$F \supsetneq H$.
The \defn{characteristic polynomial} of~$\arrangement$ is the coefficient of~$x^d$ in~$\mobPol$, \ie
\(
\charPol \eqdef \sum_F \mu(\R^d,F) \, y^{\dim(F)} .
\)
\end{definition}

\begin{theorem}[{\cite[Theorem~A]{Zaslavsky}}]
\label{thm:Zaslavsky}
The $f$-polynomial, the $b$-polynomial, and the M\"obius polynomial of an arrangement~$\arrangement$ are related by~$\fPol = \mobPol[\arrangement][-x][-1]$ and~$\bPol = \mobPol[\arrangement][-x][1]$.
In particular, $f_d(\arrangement) = (-1)^d \, \charPol[\arrangement][-1]$ and~$b_d(\arrangement) = (-1)^d \, \charPol[\arrangement][1]$.
\end{theorem}

\vspace{-.5cm}
\parpic(5cm,1.8cm)(2pt,115pt)[r][b]{\includegraphics[scale=.75]{braidArrangement3Labeled}}
\begin{example}
The braid arrangement~$\braidArrangement$ has
\begin{compactitem}
\item a $k$-face for each ordered partition of~$[n]$ into~$k+1$ parts, %or equivalently, for each surjection from~$[n]$ to~$[k+1]$,
\item a $k$-flat for each unordered partition of~$[n]$ into $k+1$ parts.
\end{compactitem}
See \Cref{fig:braidArrangementPosets}.
The M\"obius function of the set partitions poset is given by ${\mu(\pi, \omega) = \prod_{p \in \omega} (-1)^{\card{\pi[p]}-1}(\card{\pi[p]}-1)!}$, where~$\pi[p]$ denotes the restriction of~$\pi$ to the part~$p$ of~$\omega$, and $\card{\pi[p]}$ denotes its number of parts.
The M\"obius polynomial of~$\braidArrangement$ is given by $\mobPol[\braidArrangement] = \sum_{k \in [n]} x^{k-1} S(n,k) \prod_{i \in [k-1]} (y-i)$, where~$S(n,k)$ denotes the Stirling number of the second kind \OEIS{A008277}, \ie the number of set partitions of~$[n]$ into~$k$ parts.
\end{example}

\begin{figure}[b]
	\centerline{
		\includegraphics[scale=.54]{facePosetBraidArrangement3}
		\qquad\quad
		\includegraphics[scale=.53]{flatPosetBraidArrangement3}
	}
	\caption{The face poset of~$\braidArrangement[3]$ labeled by faces (left) and ordered partitions (mid.~left), and the flat poset of~$\braidArrangement[3]$ labeled by flats (mid.~right) and unordered partitions (right).}
	\label{fig:braidArrangementPosets}
\end{figure}
 
%\begin{figure}
%	\centerline{\includegraphics[scale=.7]{forestsLong}}
%	\caption{Some $(3,6)$-partition forests with their intersection hypergraphs.}
%	\label{fig:forests}
%\end{figure}

\parpic(4.5cm,7.5cm)(-2pt,250pt)[r][b]{\includegraphics[scale=.9]{forest}}
We now consider the arrangement~$\multiBraidArrangement$ of~\Cref{def:multiBraidArrangement} and describe its flat poset.

\begin{definition}[{\cite[Section~2.1]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{def:partitionForests}
The \defn{intersection hypergraph} of a \mbox{$\ell$-tuple} $\b{F} \eqdef (F_1, \dots, F_\ell)$ of set partitions of~$[n]$ is the $\ell$-regular \mbox{$\ell$-par}\-tite hypergraph on all parts of all the partitions~$F_i$ for~${i \in [\ell]}$, with a hyperedge connecting the parts containing~$j$  for each~$j \in [n]$.
An \defn{$(\ell,n)$-par\-tition forest} is a $\ell$-tuple~$\b{F} \eqdef (F_1, \dots, F_\ell)$ of set partitions of~$[n]$ whose intersection hypergraph is a hyperforest.
For instance, the picture on the right represents a $(3,6)$-partition forest on top, and its intersection hyperforest on bottom. % \Cref{fig:forests}.
%The \defn{dimension} of~$\b{F}$ is~$\smash{{\dim(\b{F}) \eqdef n - 1 - \ell n + \sum_{i \in [\ell]} \card{F_i}}}$.
The \defn{$(\ell,n)$-partition forest poset} is the poset~$\forestPoset$ on $(\ell,n)$-partition forests ordered by componentwise refinement.
\end{definition}

\begin{proposition}[{\cite[Proposition~2.3]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{prop:flatPosetMultiBraidArrangement}
The flat poset of~$\multiBraidArrangement$ is isomorphic to the $(\ell,n)$-partition forest poset~$\forestPoset$.
\end{proposition}

From this description of the flat poset of~$\multiBraidArrangement$, we derive the following enumerative results by~\Cref{thm:Zaslavsky}.

\begin{theorem}[{\cite[Theorem~2.4 \& Corollary~2.6]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{thm:MobiusPolynomialMultiBraidArrangement}
The M\"obius polynomial of~$\multiBraidArrangement$ is given by
\[
\mobPol[\multiBraidArrangement] = x^{n-1-\ell n} y^{n-1-\ell n} \sum_{\b{F} \le \b{G}} \prod_{i \in [\ell]} x^{\card{F_i}} y^{\card{G_i}} \prod_{p \in G_i} (-1)^{\card{F_i[p]}-1} (\card{F_i[p]}-1)! \; ,
\]
where~$\b{F} \le \b{G}$ ranges over all intervals of the $(\ell,n)$-partition forest poset~$\forestPoset$, and~$F_i[p]$ denotes the restriction of the partition~$F_i$ to the part~$p$ of~$G_i$.
Hence, the $f$- and $b$-polynomials of~$\multiBraidArrangement$ are
\begin{align*}
\fPol[\multiBraidArrangement] & = x^{n-1-\ell n}\sum_{\b{F} \le \b{G}} \prod_{i \in [\ell]} x^{\card{F_i}} \prod_{p \in G_i} (\card{F_i[p]}-1)!\\
\text{and}\qquad
\bPol[\multiBraidArrangement] & = (-1)^\ell x^{n-1-\ell n} \sum_{\b{F} \le \b{G}} \prod_{i \in [\ell]} x^{\card{F_i}} \prod_{p \in G_i} -(\card{F_i[p]}-1)!.
\end{align*}
\end{theorem}

\begin{theorem}[{\cite[Theorems~2.18 \& 2.19]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{thm:verticesMultiBraidArrangement}
The number of vertices of~$\multiBraidArrangement$ is
\(
% f_0(\multiBraidArrangement) =
{\ell \big( (\ell \!-\! 1) n \!+\! 1 \big)^{n-2}}.
\)
In fact, 
%for any~$k_1, \dots, k_\ell$ such that~$0 \le k_i \le n-1$ for~$i \in [\ell]$ and~${\sum_{i \in [\ell]} k_i = n-1}$, 
the number of vertices~$v$ of~$\multiBraidArrangement$ such that the smallest flat of the $i$\ordinal{} copy of~$\braidArrangement$ containing~$v$ has dimension~${n-k_i-1}$ is given by
\(
n^{\ell-1} \binom{n-1}{k_1, \dots, k_\ell} \prod_{i \in [\ell]} (n-k_i)^{k_i-1}.
\)
\end{theorem}

\begin{theorem}[{\cite[Theorems~2.20 \&~2.21]{DelcroixOgerLaplanteAnfossiPilaudStoeckl}}]
\label{thm:characteristicPolynomialMultiBraidArrangement}
The characteristic polynomial of~$\multiBraidArrangement$ is given~by
\[
\charPol[\multiBraidArrangement] = \frac{(-1)^n n!}{y} \, [z^n] \, \exp \bigg( - \sum_{m \ge 1} \frac{F_{\ell,m} \, y \, z^m}{m} \bigg) ,
\]
where~$F_{\ell,m} \eqdef \frac{1}{(\ell-1)m+1} \binom{\ell m}{m}$ is the Fuss--Catalan number.
Hence, the numbers of regions and of bounded regions of~$\multiBraidArrangement$ are
\[
%n! [z^n] \exp \Bigl( \sum_{m \ge 1} \frac{F_{\ell,m} \, z^m}{m} \Bigr)
%\qquad\text{and}\qquad
%(n-1)! [z^{n-1}] \exp \Bigl( (\ell-1) \sum_{m \ge 1} F_{\ell,m} \, z^m \Bigr).
 f_{n-1}(\multiBraidArrangement) \! = \! 
n! [z^n] \exp \Bigl( \! \sum_{m \ge 1} \! \frac{F_{\ell,m} \, z^m}{m} \! \Bigr)
\;\;\text{and}\;\;
 b_{n-1}(\multiBraidArrangement) \! = \! 
(n-1)! [z^{n-1}] \exp \Bigl( \! (\ell-1) \! \sum_{m \ge 1} \! F_{\ell,m} \, z^m \! \Bigr).
\]
\end{theorem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\section{Cellular diagonals of associahedra}
\label{sec:cellularDiagonalsAssociahedra}

Recall that the \defn{associahedron}~$\Asso$ is the polytope defined equivalently as
\begin{compactitem}
\item the convex hull of the points~$\sum_{i \in [n]} \ell(T,i) \, r(T,i) \, \b{e}_i$ for all binary trees~$T$ with $n$~internal nodes, where $\ell(T,i)$ and~$r(T,i)$ respectively denote the numbers of leaves in the left and right subtrees of the $i$th node of~$T$ in infix labeling, see~\cite{Loday},
\item the intersection of the hyperplane~$\smash{\HH_n \eqdef \bigset{\b{x} \in \R^n}{{\displaystyle\sum\nolimits_{i \in [n]}} x_i = \binom{n+1}{2}}}$ with the halfspaces~$\smash{\bigset{\b{x} \in \R^n}{{\displaystyle\sum\nolimits_{i \le \ell \le j}} x_\ell \ge \binom{j-i+2}{2}}}$ for all~$1 \le i \le j \le n$, see~\cite{ShniderSternberg}.
\end{compactitem}

\medskip
\parpic(5.5cm,3cm)(-2pt,120pt)[r][b]{\includegraphics[scale=.5]{associahedronTamariLattice}}
When oriented in the direction~$\omega_n$, its graph is the Hasse diagram of the \defn{Tamari lattice}~\cite{Tamari} on binary trees with $n$ internal nodes, whose cover relations are right rotations.
See on the right.

\medskip
There is one specific geometric diagonal~$\diagonal\Asso$ of the associahedra which respects the Tamari lattice and satisfies the magical formula~ \cite{SaneblidzeUmble, MarklShnider, Loday-diagonal, MasudaThomasTonksVallette, LaplanteAnfossi}.

\medskip
\begin{proposition}[{\cite[Theorem~2]{MasudaThomasTonksVallette}}]
\label{prop:magicalFormulaAssociahedron}
The $k$-faces of the diagonal~$\diagonal\Asso$ correspond to the pairs $(F,G)$ of faces of~$\Asso$ with~$\dim(F) + \dim(G) = k$ and~$\max(F) \le \min(G)$ (where~$\le$, $\max$ and~$\min$ refer to the order given by the Tamari lattice).
\end{proposition}

\begin{theorem}[{\cite[Proposition~7 \!\&\! Theorem~2]{BostanChyzakPilaud}}]
\label{thm:fVectorDiagonalAssociahedron}
%The $f$-vector of the diagonal~$\diagonal\Asso$ % of the $(n-1)$-dimensional associahedron~$\Asso$
%is given by
The number of $k$-faces of~$\diagonal\Asso$ is
%\begin{equation}
%\label{eq:fVectorDiagonalAssociahedron}
\[
f_k \big( \diagonal\Asso \big) = 
\frac{2}{(3n+1)(3n+2)} \binom{n-1}{k} \binom{4n+1-k}{n+1}.
\]
%\end{equation}
\end{theorem}

\begin{remark}
\begin{compactenum}[(i)]
\item \textbf{Tamari intervals} are enumerated by
\(
f_0 \big( \diagonal\Asso \big) = \frac{2}{(3n+1)(3n+2)} \binom{4n+1}{n+1}.
\)
This formula was proved in~\cite{Chapoton1} and appears as~\OEIS{A000260}. It also counts the rooted $3$-connected planar triangulations with $2n+2$ faces, and explicit bijections between Tamari intervals and $3$-connected triangulations were given in~\cite{BernardiBonichon,FangFusyNadeau}.
\medskip
\item \textbf{Synchronized Tamari intervals} are enumerated by
\(
f_{n-1} \big( \diagonal\Asso \big) = \frac{2}{n(n+1)} \binom{3n}{n-1}. % = \frac{2}{(n+1)(2n+1)} \binom{3n}{n}
\)
This formula was proved in~\cite{FangPrevilleRatelle} and appears as~\OEIS{A000139}. It also counts the rooted non-separable planar maps with $n+1$ edges, and the $2$-stack sortable permutations of~$[n]$.
\end{compactenum}
\end{remark}

\begin{table}[t]
	\centerline{\footnotesize
	\begin{tabular}{c|ccccccccc}
		$n \backslash k$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\
		\hline
		$1$ & $1$ \\
		$2$ & $3$ & $2$ \\
		$3$ & $13$ & $18$ & $6$ \\
		$4$ & $68$ & $144$ & $99$ & $22$ \\
		$5$ & $399$ & $1140$ & $1197$ & $546$ & $91$ \\
		$6$ & $2530$ & $9108$ & $12903$ & $8976$ & $3060$ & $408$ \\
		$7$ & $16965$ & $73710$ & $131625$ & $123500$ & $64125$ & $17442$ & $1938$ \\
		$8$ & $118668$ & $604128$ & $1302651$ & $1540770$ & $1078539$ & $446292$ & $100947$ & $9614$ \\
		$9$ & $857956$ & $5008608$ & $12660648$ & $18086640$ & $15958800$ & $8898240$ & $3058770$ & $592020$ & $49335$
	\end{tabular}
	}
	\caption{The first few values of $f_k \big( \diagonal\Asso \big)  = \frac{2}{(3n+1)(3n+2)} \binom{n-1}{k} \binom{4n+1-k}{n+1}$. Note that the first column is~\OEIS{A000260} while the diagonal is~\OEIS{A000139}.}
	\label{table:fVectorDiagonal}
\end{table}

%\begin{proof}[Proof sketch of \Cref{thm:fVectorDiagonalAssociahedron}]
We finally briefly discuss the ideas behind \Cref{thm:fVectorDiagonalAssociahedron}.
For a binary tree~$T$, let~$\des(T)$ (resp.~$\asc(T)$) denote the number of binary trees covered by~$T$ (resp.~covering~$T$) in the Tamari lattice.
As the associahedron is a simple polytope, there are precisely~$\smash{\binom{\des(T)}{\ell}}$ (resp.~$\smash{\binom{\asc(T)}{\ell}}$) $\ell$-faces of the associahedron whose maximal (resp.~minimal) vertex is~$T$.
We thus directly derive from the magical formula of~\Cref{prop:magicalFormula} that the number of $k$-faces~of~$\diagonal\Asso$~is
\[
\sum_{S \le T} \sum_{0 \le \ell \le k} \binom{\des(S)}{\ell} \binom{\asc(T)}{k-\ell} = \sum_{S \le T} \binom{\des(S) + \asc(T)}{k}.
\]
At this point, there are at least two possible proofs for~\Cref{thm:fVectorDiagonalAssociahedron}, discussed in~\cite{BostanChyzakPilaud}:
\begin{compactitem}
\item The first proof is analytic.
Using a natural recursive decomposition, one obtains a quadratic equation on the generating function of Tamari intervals with one additional catalytic variable~\cite{Chapoton1}.
By the quadratic method, this equation can be transformed into a polynomial equation on~$A(t,z) \eqdef \sum_{n,k} \sum_{S \le T} \binom{\des(S) + \asc(T)}{k} t^n z^k$.
One then obtains~\Cref{thm:fVectorDiagonalAssociahedron} by extracting the coefficients of~$A(t,z)$ by Lagrange inversion after an adequate reparameterization of our polynomial equation.
%Here, there is also an alternative (more systematic and robust) analytic method, based on recurrence relations obtained by creative telescoping.
\item The second proof is bijective.
For a Tamari interval~$S \le T$, the statistics~$\des(S)$ and~$\asc(T)$ can be translated in terms of canopy agreement between~$S$ and~$T$.
Through the bijection of~\cite{BernardiBonichon}, a simple expression for the generating function of Tamari intervals with variables recording the canopy patterns of the two trees was obtained in~\cite{FusyHumbert}.
We then obtain~\Cref{thm:fVectorDiagonalAssociahedron} by specializing variables in this generating function and extracting coefficients by Lagrange inversion again.
%We note that an even simpler bijective approach can be obtained from the recent direct bijection of~\cite{FangFusyNadeau} between Tamari intervals and blossoming trees.
%\qedhere
\end{compactitem}
%\end{proof}

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

%\acknowledgements{...}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}
