intro.tex

\chapter*{Introduction} 
\label{s:introduction}

The purpose of this article is to study \emph{cellular diagonals} on the \emph{permutahedra}, which are cellular maps homotopic to the usual \emph{thin diagonal} ${\triangle : P \to P \times P}$ given by~${x \mapsto (x,x)}$ (\cref{def:thinDiagonal,def:cellularDiagonal}).
Such diagonals, and in particular coherent families that we call \emph{operadic diagonals} (\cref{def:operadicDiagonal}), 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}.

Cellular diagonals 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. 
The seminal case of the \emph{associahedra} has a rich history: the first algebraic diagonal was found by S.~Saneblidze and R.~Umble~\cite{SaneblidzeUmble}, followed by a second one by M.~Markl and S.~Shnider~\cite{MarklShnider}, which was conjectured to coincide with the first one. 
This has recently been shown to hold~\cite{SaneblidzeUmble-comparingDiagonals}, while a topological enhancement of the \emph{magical formula} of~\cite{MarklShnider} was provided by N.~Masuda, H.~Thomas, A.~Tonks and B.~Vallette~\cite{MasudaThomasTonksVallette}.

In~\cite{MasudaThomasTonksVallette}, the authors re-introduced the powerful technique of Fulton--Sturmfels~\cite{FultonSturmfels}, which came from the theory of fiber polytopes of~\cite{BilleraSturmfels}, to define a topological cellular diagonal of the associahedra.
We shall call such a diagonal a \emph{geometric diagonal} (\cref{def:geometricDiagonal}).
There are two remarkable features of this diagonal (or more precisely this family of diagonals, one for the Loday associahedron in each dimension).
First, it respects the operadic structure of the associahedra (in fact, forces a unique topological cellular operad structure on them!), that is, the fact that each face of an associahedron is isomorphic to a product of lower-dimensional associahedra.
Second, it satisfies the \emph{magical formula} of J.-L. Loday: the faces in the image of the diagonal are given by the pairs of faces which are comparable in the Tamari order (see \cref{sec:cellularDiagonals,rem:magicalFormula} for a precise statement). 
This magical formula for the associahedra recently lead to new enumerative results for Tamari intervals~\cite{BostanChyzakPilaud}.

Building on~\cite{MasudaThomasTonksVallette}, a general theory of geometric diagonals was developed in~\cite{LaplanteAnfossi}.
In particular, a combinatorial formula describing the image of the diagonal of any polytope was given~\cite[Thm.~1.26]{LaplanteAnfossi}.
The topological operad structure of~\cite{MasudaThomasTonksVallette} on the associahedra was generalized to the family of \emph{operahedra}, which comprise 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).

Since the operahedra are \emph{generalized permutahedra}~\cite{Postnikov}, their operadic diagonals are completely determined by the operadic diagonals of permutahedra (see~\cite[Sect.~1.6]{LaplanteAnfossi}), which is the purpose of study of the present paper.

The first cellular diagonal of the permutahedra was obtained at the algebraic level by S.~Sanebli\-dze and R.~Umble~\cite{SaneblidzeUmble}.
We shall call this diagonal the \emph{original $\SU$ diagonal}. 
The first topological cellular diagonal of the permutahedra was defined in~\cite{LaplanteAnfossi}, we shall call it the \emph{geometric $\LA$ diagonal}.
Both of these families of diagonals are \emph{operadic}, \ie they respect the product structure on the faces of permutahedra (this property is called ``comultiplicativity" in~\cite{SaneblidzeUmble}).
More precisely, the algebraic structure encoded by the permutahedra is that of permutadic $\Ainf$-algebra~\cite{LodayRonco-permutads,Markl}.

The toric varieties associated with the permutahedra are called Losev--Manin varieties, introduced in~\cite{LosevManin}.
At this level, the operadic structure is that of a reconnectad~\cite{DotsenkoKeilthyLyskov}. 
The cohomology ring structure was studied by A.~Losev and Y.~Manin, and quite extensively since then, see for instance~\cite{BergstromMinabe, Lin}. 
Our current work brings a completely combinatorially explicit description of the cup product; it would be interesting to know if this new description can lead to new results, or how it can be used to recover existing ones.

The first part of the paper derives enumerative results for the iterations of any geometric diagonal of the permutahedra. 
According to the Fulton--Sturmfels formula~\cite{FultonSturmfels} (see \cref{prop:diagonalCommonRefinement} and \cref{rem:Fulton--Sturmfels}), this amounts to the study of hyperplane arrangements made of generically translated copies of the braid arrangement.
The second part studies in depth the combinatorics of operadic diagonals of the permutahedra, providing in particular a topological enhancement of the original $\SU$ diagonal, while the third part derives consequences of this combinatorial study in the field of homotopical algebra.
We now proceed to introduce separately each part in more detail.

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

\subsection*{\cref{part:multiBraidArrangements}. Combinatorics of multiple braid arrangements}

As the dual of the permutahedron~$\Perm$ is the classical braid arrangement~$\braidArrangement$, the dual of a diagonal of the permutahedron~$\Perm$ is a hyperplane arrangement~$\multiBraidArrangement[n][2]$ made of $2$ generically translated copies of the braid arrangement~$\braidArrangement$.
In the first part of the paper, we therefore study the combinatorics of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$, defined as the union of $\ell$ generically translated copies of the braid arrangement~$\braidArrangement$ (\cref{def:multiBraidArrangement}).
We are mainly interested in the~$\ell = 2$ case for the enumeration of the faces of the diagonals of the permutahedron~$\Perm$, but the general $\ell$ case is not much harder and corresponds algebraically to the enumeration of the faces of cellular $\ell$-gonals of the permutahedron~$\Perm$.
%We observe that the flats of~$\multiBraidArrangement$ are in bijection with forests of partitions and that the faces of~$\multiBraidArrangement$ are in bijection with certain forests of ordered partitions.

\cref{sec:flatPoset} is dedicated to the combinatorial description of the flat poset of~$\multiBraidArrangement$ and its enumerative consequences.
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}).
As this description is independent of the translations of the different copies (as long as these translations are generic), we obtain by T.~Zaslavsky's theory that the number of \mbox{$k$-dimensional} faces and of bounded faces of~$\multiBraidArrangement$ only depends on~$k$, $\ell$, and~$n$. % (and not on the specific translation vectors choosen to construct~$\multiBraidArrangement$).
In fact, we obtain the following formula for the M\"obius polynomial of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$ in terms of pairs of $(\ell,n)$-partition forests.

\begin{theorem*}[\cref{thm:MobiusPolynomialMultiBraidArrangement}]
The M\"obius polynomial of the $(\ell,n)$-braid arrangement~$\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, and~$F_i[p]$ denotes the restriction of the partition~$F_i$ to the part~$p$ of~$G_i$.
\end{theorem*}

This formula is not particularly easy to handle, but it turns out to simplify to very elegant formulas for the number of vertices, regions, and bounded regions of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$.
Namely, using an alternative combinatorial description of the $(\ell,n)$-partition forests in terms of $(\ell, n)$-rainbow forests and a colored analogue of the classical Pr\"ufer code for permutations, we first obtain the number of vertices of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$.

\begin{theorem*}[\cref{thm:verticesMultiBraidArrangement}]
The number of vertices of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$ is
\[
f_0(\multiBraidArrangement) = \ell \big( (\ell-1) n + 1 \big)^{n-2}.
\]
\end{theorem*}

This result can even be refined according to the dimension of the flats of the different copies intersected to obtain the vertices of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$.

\begin{theorem*}[\cref{thm:verticesRefinedMultiBraidArrangement}]
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 the $(\ell,n)$-braid arrangement~$\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*}

We then consider the regions of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$.
We first obtain a very simple exponential formula for its characteristic polynomial.

\begin{theorem*}[\cref{thm:characteristicPolynomialMultiBraidArrangement}]
The characteristic polynomial~$\charPol[\multiBraidArrangement]$ of the \linebreak $(\ell,n)$-braid arrangement~$\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~$\displaystyle F_{\ell,m} \eqdef \frac{1}{(\ell-1)m+1} \binom{\ell m}{m}$ is the Fuss-Catalan number.
\end{theorem*}

Evaluating the characteristic polynomial at~$y = -1$ and~$y = 1$ respectively, we obtain by T.~Zaslavsky's theory the numbers of regions and bounded regions of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$.

\begin{theorem*}[\cref{thm:regionsMultiBraidArrangement}]
The numbers of regions and of bounded regions of the $(\ell,n)$-braid arrangement~$\multiBraidArrangement$ are given by
\begin{align*}
f_{n-1}(\multiBraidArrangement) 
& = n! \, [z^n] \exp \Bigg( \sum_{m \ge 1} \frac{F_{\ell,m} \, z^m}{m} \Bigg) \\
\text{and}\qquad
b_{n-1}(\multiBraidArrangement)
%& = - n! \, [z^n] \exp \Bigg( - \sum_{m \ge 1} \frac{F_{\ell,m} \, z^m}{m} \Bigg) 
& = (n-1)! \, [z^{n-1}] \exp \bigg( (\ell-1) \sum_{m \ge 1} F_{\ell,m} \, z^m \bigg),
\end{align*}
where~$\displaystyle F_{\ell,m} \eqdef \frac{1}{(\ell-1)m+1} \binom{\ell m}{m}$ is the Fuss-Catalan number.
\end{theorem*}

Finally, \cref{sec:facePoset} is dedicated to the combinatorial description of the face poset of~$\multiBraidArrangement$.
We observe that the faces of~$\multiBraidArrangement$ are in bijection with certain \emph{ordered} $(\ell,n)$-partition forests, defined as $\ell$-tuples of ordered partitions of~$[n]$ whose underlying unordered partitions form an (unordered) $(\ell,n)$-partition forest (\cref{def:orderedPartitionForest}).
Here, which ordered $(\ell,n)$-partition forests actually appear as faces of~$\multiBraidArrangement$ depends on the choice of the translations of the different copies.
We provide a combinatorial description of the possible orderings of a $(\ell,n)$-partition forest compatible with some given translations in terms of certain paths in the forest (\cref{prop:PFtoOPF1,prop:PFtoOPF2}), and a combinatorial characterization of the ordered partition forests which appear for some given translations in terms of the circuits of a certain oriented graph (\cref{prop:characterizationOPFs}).

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

\subsection*{\cref{part:diagonalsPermutahedra}. Diagonals of permutahedra}

We present cellular diagonals, the Fulton--Sturmfels method, the magical formula and specialize the results of \cref{part:multiBraidArrangements} to the permutahedra in \cref{sec:cellularDiagonals}.
Then, we initiate in \cref{sec:operadicDiagonals} the study of operadic diagonals (\cref{def:operadicDiagonal}).
These are families of diagonals of the permutahedra which are compatible with the property that faces of permutahedra are product of lower-dimensional permutahedra. 

\begin{theorem*}[\cref{thm:unique-operadic,thm:bijection-operadic-diagonals}]
There are exactly four operadic geometric diagonals of the permutahedra, the geometric $\LA$ and $\SU$ diagonals and their opposites, and only the first two respect the weak order on permutations.
Moreover, their cellular images are isomorphic as posets.
\end{theorem*}

It turns out that the facets and vertices of operadic diagonals admit elegant combinatorial descriptions. 
The following is a consequence of a general geometrical result, that holds for any diagonal (\cref{prop:PFtoOPF1}).

\begin{theorem*}[\cref{thm:facet-ordering}]
A pair of ordered partitions $(\sigma,\tau)$ forming a partition tree is a facet of the $\LA$ (\resp $\SU$) geometric diagonal if and only if the minimum (\resp maximum) of every directed path between two consecutive blocks of $\sigma$ or $\tau$ is oriented from $\sigma$ to $\tau$ (\resp from $\tau$ to $\sigma$).
\end{theorem*}

Vertices of operadic diagonals are pairs of permutations, and form a strict subset of intervals of the weak order. 
They admit an analogous description in terms of pattern-avoidance. 

\begin{theorem*}[\cref{thm:patterns}]
A pair of permutations of $[n]$ is a vertex of the $\LA$ (\resp $\SU$) diagonal if and only if for any~$k\geq 1$ and for any $I=\{i_1, \dots, i_k\}$, ${J=\{j_1, \dots, j_k\} \subset [k]}$ such that $i_1=1$ (\resp $j_k=2k$) it avoids the patterns 
\begin{align}
	(j_1 i_1 j_2 i_2 \cdots j_k i_k,\ i_2 j_1 i_3 j_2 \cdots i_k j_{k-1} i_1 j_k), \tag{LA} \\
	\text{ \resp } (j_1 i_1 j_2 i_2 \cdots j_k i_k, \ i_1 j_k i_2 j_1 \cdots i_{k-1} j_{k-2}i_k j_{k-1}), \tag{SU}
\end{align}
For each $k \ge 1$, there are $\binom{2k-1}{k-1,k}(k-1)!k!$ such patterns, which are $(21,12)$ \linebreak for~$k=1$, and the following for~$k=2$
\begin{itemize}
	\item $\LA$ avoids the patterns
	$(3142,2314)$, $(4132,2413)$,
	$(2143,3214)$, $(4123,3412)$,
	$(2134,4213)$, $(3124,4312)$,
	\item $\SU$ avoids the patterns
	$(1243,2431)$, $(1342,3421)$,
	$(2143,1432)$, $(2341,3412)$,
	$(3142,1423)$, $(3241,2413)$.
\end{itemize}
\end{theorem*}

In \cref{sec:shifts}, we introduce \emph{shifts} that can be performed on the facets of operadic diagonals.
These allow us to show that the geometric $\SU$ diagonal is a topological enhancement of the original $\SU$ diagonal. 

\begin{theorem*}[\cref{thm:recover-SU}]
The original and geometric $\SU$ diagonals coincide. 
\end{theorem*}

The proof of this result, quite technical, proceeds by showing the equivalence between $4$ different descriptions of the diagonal: the original, $1$-shift, $m$-shift and geometric $\SU$ diagonals (\cref{subsec:topological-SU}).
This brings a positive answer to~\cite[Rem.~2.19]{LaplanteAnfossi}, showing that the original $\SU$ diagonal can be recovered from a choice of chambers in the fundamental hyperplane arrangement of the permutahedron. 
Our formulas for the number of facets also agrees with the experimental count made in~\cite{VejdemoJohansson}.
Moreover, it provides a new proof that all known diagonals on the associahedra coincide~\cite{SaneblidzeUmble-comparingDiagonals}.
Indeed, since the family of vectors inducing the geometric $\SU$ diagonal all have strictly decreasing coordinates, the diagonal induced on the associahedron is given by the magical formula~\cite[Thm.~2]{MasudaThomasTonksVallette}, see also~\cite[Prop.~3.8]{LaplanteAnfossi}.

The above theorem also allows us to translate the different combinatorial descriptions of the facets of operadic diagonals from one to the other, compiled in the following table. 

\begin{figure}[h!]
	\begin{center}
	\begin{tabular}{c|c|c}
	Description & $\SU$ diagonal & $\LA$ diagonal \\
	\hline
	Original & \cite{SaneblidzeUmble} & \cref{def:classical-LA} \\
	Geometric & \cref{thm:minimal} & \cite{LaplanteAnfossi} \\
	Path extrema & \cref{thm:facet-ordering} & \cref{thm:facet-ordering} \\
	$1$-shifts & \cref{def:classical-SU} & \cref{def:classical-LA} \\
	$m$-shifts & \cref{def:classical-SU} & \cref{def:classical-LA} \\
	Lattice & \cref{prop:shift lattice} & \cref{prop:shift lattice} \\
	Cubical & \cite{SaneblidzeUmble} & \cref{prop:LA-cubical} \\
	Matrix & \cite{SaneblidzeUmble} & \cref{subsec:matrix} 
	\end{tabular}
	\end{center}
\end{figure}

In \cref{sec:Shift-lattice}, we show that the facets of operadic diagonals are disjoint unions of lattices, that we call the \emph{shift lattices}.
These lattices are isomorphic to a product of chains, and are indexed by the permutations of $[n]$.
Moreover, while the pairs of facets of operadic diagonals are intervals of the facial weak order (\cref{sec:facial-weak-order}), the shift lattices are not sub-lattices of this order's product (see \cref{fig: Inversion and lattice counter example}). 

Finally, we present the alternative cubical (\cref{sec:Cubical}) and matrix (\cref{subsec:matrix}) descriptions of the $\SU$ diagonal from \cite{SaneblidzeUmble,SaneblidzeUmble-comparingDiagonals}, providing proofs of their equivalence with the other descriptions, and giving their $\LA$ counterparts. 
The existence of this cubical description, based on a subdivision of the cube combinatorially isomorphic to the permutahedron, finds its conceptual root in the bar-cobar resolution of the associative permutad. 
Indeed, this resolution is encoded by the dual subdivision of the permutahedron, which is cubical since $\Perm$ is a simple polytope, and a diagonal can be obtained from the classical Serre diagonal via retraction, in the same fashion as for the associahedra, see \cite{MarklShnider, Loday-diagonal} and \cite[Sec. 5.1]{LaplanteAnfossiMazuir}.

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

\subsection*{\cref{part:higherAlgebraicStructures}. Higher algebraic structures}

In this shorter third part of the paper, we derive some higher algebraic consequences of the preceding results, which were the original motivation for the present study.
They concern the \emph{operahedra}, a family of polytopes indexed by planar trees, which encode (non-symmetric non-unital) homotopy operads \cite{LaplanteAnfossi}, and the \emph{multiplihedra}, a family of polytopes indexed by $2$-colored nested linear trees, which encode $\Ainf$-morphisms \cite{LaplanteAnfossiMazuir}.
Both of these admit realizations ``\`a la Loday", which generalize the Loday realizations of the associahedra. 
The faces of an operahedron are in bijection with \emph{nestings}, or parenthesization, of the corresponding planar tree, while the faces of a multiplihedron are in bijection with $2$-colored nestings of the corresponding linear tree. 
The main results concerning the operahedra are summarized as follows. 

\begin{theorem*}[\cref{thm:operahedra,thm:top-iso,thm:infinity-iso}] 
There are exactly 
\begin{enumerate}
	\item two geometric operadic diagonals of the Loday operahedra, the $\LA$ and $\SU$ diagonals, 
	\item two geometric topological cellular colored operad structures on the Loday operahedra,
	\item two geometric universal tensor products of homotopy operads,
\end{enumerate}
which agree with the generalized Tamari order on fully nested trees. 
Moreover, the two topological operad structures are isomorphic, and the two tensor products are not strictly isomorphic, but are related by an $\infty$-isotopy. 
\end{theorem*}

As the associahedra and the permutahedra are part of the family of operahedra, we get analogous results for $\Ainf$-algebras and permutadic $\Ainf$-algebras. 
The main results concerning the multiplihedra are summarized as follows. 

\begin{theorem*}[{\cref{thm:multiplihedra,thm:top-iso-2,thm:infinity-iso-2}}]
	There are exactly 
	\begin{enumerate}
	\item two geometric operadic diagonals of the Forcey multiplihedra, the $\LA$ and $\SU$ diagonals,
	\item two geometric topological cellular operadic bimodule structures (over the Loday associahedra) on the Forcey multiplihedra,
	\item two compatible geometric universal tensor products of $\Ainf$-algebras and $\Ainf$-morphisms,
	\end{enumerate}
	which agree with the Tamari-type order on atomic $2$-colored nested linear trees. 
	Moreover, the two topological operadic bimodule structures are isomorphic, and the two tensor products are not strictly isomorphic, but are related by an $\infty$-isotopy. 
\end{theorem*}

Here, by the adjective ``geometric", we mean diagonal, operadic structure and tensor product which are obtained geometrically on the polytopes via the Fulton--Sturmfelds method. 
By ``universal", we mean formulas for the tensor products which apply to \emph{any} pair of homotopy operads or $\Ainf$-morphisms.

However, the isomorphisms of topological operads (\resp operadic bimodules) takes place in a category of polytopes $\PolySub$ for which the morphisms are \emph{not} affine maps \cite[Def. 4.13]{LaplanteAnfossi}, and it does \emph{not} commute with the diagonal maps (\cref{ex:iso-not-Hopf,ex:iso-not-Hopf-2}).
Moreover, the pairs of faces in the image of the two operadic diagonals are in general not in bijection (see \cref{ex:operahedra-LA-SU,ex:multiplihedra-LA-SU}), yielding different (but $\infty$-isomorphic) tensor products of homotopy operads (\resp \mbox{$\Ainf$-morphisms}).