%~Mouliné par MaN_auto v.0.33.1 2024-12-19 08:45:02 \documentclass[AHL,Unicode,longabstracts,published]{cedram} \usepackage{xcolor} \usepackage{xargs} \usepackage{etoolbox} \usepackage{tikz} \usepackage{tikz-qtree} \usepackage[external]{forest} \usepackage{dsfont} \usepackage{picins/picins} \usepackage{enumerate} \DeclareMathOperator{\conv}{conv} %\DeclareMathOperator{\vect}{vect} %\DeclareMathOperator{\cone}{cone} %\DeclareMathOperator{\inv}{inv} %\DeclareMathOperator{\Binv}{inv^\textsc{b}} %\DeclareMathOperator{\Ima}{Im} %\DeclareMathOperator{\Vol}{Vol} %\DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\rev}{rev} \DeclareMathOperator{\rank}{rk} \usetikzlibrary{trees, decorations, decorations.markings, shapes, arrows, matrix, calc, fit, intersections, patterns, angles} %\AtBeginDocument{ %\newtheorem{myname}[cdrthm]{My beautiful theorem} } %\graphicspath{{figures/}} %\makeatletter %\newcommand*\failedinput{{figures/}}\makeatother \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\rul}{\mathrm{ul}} %\newcommand{\Z}{\mathbb{Z}} %\newcommand{\C}{\mathbb{C}} %\newcommand{\I}{\mathbb{I}} %\newcommand{\HH}{\mathbb{H}} %\newcommand{\K}{k} %\newcommand{\fA}{\mathfrak{A}} %\newcommand{\fB}{\mathfrak{S}^\textsc{b}} %\newcommand{\cA}{\mathcal{A}} %\newcommand{\cC}{\mathcal{C}} \newcommand{\cS}{\mathcal{S}} %\newcommand{\uR}{\underline{R}} %\newcommand{\uS}{\underline{S}} %\newcommand{\uT}{\underline{T}} %\newcommand{\oS}{\overline{S}} %\newcommand{\ucS}{\underline{\cS}} \renewcommand{\c}[1]{\mathcal{#1}} \renewcommand{\b}[1]{\boldsymbol{#1}} \newcommand{\f}[1]{\mathfrak{#1}} %\newcommand{\h}{\widehat} \newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} \newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} %\newcommand{\Bigset}[2]{\Big\{ #1 \;\Big|\; #2 \Big\}} %\newcommand{\setangle}[2]{\left\langle #1 \;\middle|\; #2 \right\rangle} \newcommand{\ssm}{\smallsetminus} \newcommand{\dotprod}[2]{\left\langle \, #1 \; \middle| \; #2 \, \right\rangle} %\newcommand{\symdif}{\,\triangle\,} \newcommand{\one}{\b{1}} \newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} \newcommand{ \defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} \newcommand{\simplex}{\triangle} %\renewcommand{\implies}{\Rightarrow} %\newcommand{\transpose}[1]{{#1}^t} \newcommand{\ie}{i.e.~} %\newcommand{\eg}{\textit{e.g.}~} %\newcommand{\Eg}{\textit{E.g.}~} %\newcommand{\apriori}{\textit{a priori}} %\newcommand{\viceversa}{\textit{vice versa}} %\newcommand{\versus}{\textit{vs.}~} \newcommand{\aka}{a.k.a.~} %\newcommand{\perse}{\textit{per se}} %\newcommand{\ordinal}{\textsuperscript{th}} %\newcommand{\ordinalst}{\textsuperscript{st}} \definecolor{darkblue}{RGB}{0,167,212} \definecolor{green}{RGB}{57,181,74} \definecolor{violet}{RGB}{147,39,143} \newcommand{\darkblue}{\color{darkblue}} \renewcommand{\defn}[1]{\textsl{\darkblue #1}} %\newcommand{\para}[1]{\bigskip\noindent\textbf{\uline{#1.}}} %\newcommand{\paraspace}[1]{\bigskip\noindent\textbf{#1.}\medskip} %\renewcommand{\topfraction}{1} %\renewcommand{\bottomfraction}{1} %\newcommand{\ex}{_{\textrm{exm}}} %\newcommand{\pa}{_{\textrm{pa}}} %\newcommand{\identity}{12 \dots n} \newcommand{\OEIS}[1]{{\rm \href{http://oeis.org/#1}{\texttt{#1}}}} % operations on graphs \makeatletter \newcommand{\ostar}{\mathbin{\mathpalette\make@circled\star}} \newcommand{\make@circled}[2]{% \ooalign{$\m@th#1\smallbigcirc{#1}$\cr\hidewidth$\m@th#1#2$\hidewidth\cr}% } \newcommand{\smallbigcirc}[1]{% \vcenter{\hbox{\scalebox{0.77778}{$\m@th#1\bigcirc$}}}% } \makeatother \newcommand{\superpositionGraph}{\oplus} % superposition of two graphs \newcommand{\joinGraph}{\ostar} % join of graphs of deformed permutahedra % shuffle \newcommand{\shuffleDP}{\star} % shuffle of graphs of deformed permutahedra \newcommandx{\poset}[1][1=P]{\mathbb{#1}} \newcommand{\less}{\vartriangleleft} \newcommand{\more}{\vartriangleright} %\newcommand{\bless}{\blacktriangleleft} %\newcommand{\bmore}{\blacktriangleright} \newcommand{\meet}{\wedge} \newcommand{\join}{\vee} %\newcommand{\bigMeet}{\bigwedge} %\newcommand{\bigJoin}{\bigvee} \newcommand{\projDown}{\pi_\downarrow} \newcommand{\projUp}{\pi^\uparrow} %\newcommand{\tc}[1]{#1^{\mathrm{tc}}} \newcommandx{\Fan}[1][1=n]{\mathcal{F}(#1)} \newcommand{\polytope}[1]{\mathds{#1}} \newcommandx{\DefoPerms}[1][1=n]{\polytope{DP}(#1)} \newcommandx{\Perm}[1][1=n]{\polytope{P}\mathrm{erm}(#1)} \newcommandx{\Asso}[1][1=n]{\polytope{A}\mathrm{sso}(#1)} \newcommandx{\Ossa}[1][1=n]{\polytope{A}\overline{\mathrm{sso}}(#1)} \newcommandx{\Para}[1][1=n]{\polytope{P}\mathrm{ara}(#1)} \newcommandx{\Zono}[1][1=G]{\polytope{Z}\mathrm{ono}(#1)} \newcommandx{\Point}[1][1=n]{\polytope{P}\mathrm{oint}(#1)} \newcommandx{\Multiplihedron}[2][1=m, 2=n]{\polytope{M}\mathrm{ul}(#1, #2)} \newcommandx{\Constrainahedron}[2][1=m, 2=n]{\polytope{C}\mathrm{onstr}(#1, #2)} \newcommandx{\Biassociahedron}[2][1=m, 2=n]{\polytope{B}\mathrm{ias}(#1, #2)} \newcommand{\surjections}[2]{\mathsf{S}(#1,#2)} %\newcommand{\ao}[1]{\mathsf{AO}(#1)} %\newcommand{\bc}[1]{\mathsf{BC}(#1)} \newcommand{\nc}[1]{\mathsf{NC}(#1)} \newcommand{\pp}[2]{\mathsf{PP}_{#1}(#2)} \newcommand{\children}{\mathsf{C}} \newcommand{\node}[1]{\mathsf{#1}} %\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}} \newcommand{\sylv}{\mathrm{sylv}} \newcommand{\stump}[1]{\overline{#1}} \newcommand{\cut}[1]{\underline{#1}} %\newcommand{\imagetop}[1]{\vtop{\null\hbox{#1}}} \newcommandx{\tree}[3][2=15pt, 3=22pt]{ \begin{tikzpicture}[level~1/.style={level distance=#2}, level distance=#3] \Tree #1 \end{tikzpicture} } \newcommandx{\PT}[1][1=T]{\mathbb{#1}} \newcommandx{\CT}[1][1=T]{\mathbb{#1}} \newcommandx{\BT}[1][1=T]{\mathbb{#1}} %\newcommand{\STGF}{\mathcal{ST}} \newcommand{\PTGF}{\mathcal{PT}} %\newcommand{\PBTGF}{\mathcal{PBT}} \newcommand{\BTGF}{\mathcal{BT}} \newcommand{\CTGF}{\mathcal{BT}} \newcommand{\CGF}{\mathcal{C}} \newcommand{\tCGF}{\mathcal{C}_\ast} \newcommand{\SGF}{\mathcal{S}} \newcommand{\tSGF}{\mathcal{S}_\ast} %\setcounter{tocdepth}{4} %\makeatletter %\newcommand*\l@part{\@tocline{1}{8pt}{0pc}{}{}} %\newcommand*\l@section{\@tocline{1}{9pt}{0pc}{}{}} %\makeatother \let\oldtocpart=\tocpart \let\oldtocsection=\tocsection \let\oldtocsubsubsection=\tocsubsubsection %\renewcommand{\tocpart}[2]{\sc\large\oldtocpart{#1}{#2}} %\renewcommand{\tocsection}[2]{\bf\oldtocsection{#1}{#2}} %\renewcommand{\tocsubsubsection}[2]{\quad\oldtocsubsubsection{#1}{#2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \graphicspath{{./figures/}} \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} %\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} \let\oldhat\hat \renewcommand*{\hat}[1]{\mathchoice{\widehat{#1}}{\widehat{#1}}{\oldhat{#1}}{\oldhat{#1}}} \newcommand{\llbracket}{\mathopen{[\mkern -2.7mu[}} \newcommand{\rrbracket}{\mathclose{]\mkern -2.7mu]}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title[Shuffles of deformed permutahedra]{Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra} \alttitle{Mélanges de permutaèdres déformés, multiplièdres, constrainaèdres et biassociaèdres} \subjclass{52B11, 52B12, 05A15, 05E99, 06B99} \keywords{Deformed permutahedra, permutahedra, associahedra} \author[\initial{F.} \lastname{Chapoton}]{\firstname{Frédéric} \lastname{Chapoton}} \address{CNRS, Institut de Recherche\\ Mathématique Avancée,\\ Université de Strasbourg,\\ 7 rue René Descartes,\\ F-67084 Strasbourg Cedex (France)} \email{chapoton@math.unistra.fr} \thanks{Partially supported by the French ANR grants CAPPS~17 CE40 0018 and CHARMS~19 CE40 0017, by the French--Austrian project PAGCAP (ANR-21-CE48-0020 \& FWF I 5788), by the Spanish grant PID2022-137283NB-C21 of MCIN/AEI/10.13039/501100011033 / FEDER, UE, and by Departament de Recerca i Universitats de la Generalitat de Catalunya (2021 SGR 00697).} \author[\initial{V.} \lastname{Pilaud}]{\firstname{Vincent} \lastname{Pilaud}} \address{Departament de Matemàtiques\\ i Informàtica,\\Universitat de Barcelona,\\ Gran via de les Corts\\ Catalanes 585,\\ 08007 Barcelona (Spain)} \email{vincent.pilaud@ub.edu} \begin{abstract} We introduce the shuffle of deformed permutahedra (a.k.a.~generalized permutahedra), a simple associative operation obtained as the Cartesian product followed by the Minkowski sum with the graphical zonotope of a complete bipartite graph. Besides preserving the class of graphical zonotopes (the shuffle of two graphical zonotopes is the graphical zonotope of the join of the graphs), this operation is particularly relevant when applied to the classical permutahedra and associahedra. First, the shuffle of an $m$-permutahedron with an $n$-associahedron gives the $(m,n)$-multiplihedron, whose face structure is encoded by \mbox{$m$-painted} $n$-trees, generalizing the classical multiplihedron. We show in particular that the graph of the $(m,n)$-multiplihedron is the Hasse diagram of a lattice generalizing the weak order on permutations and the Tamari lattice on binary trees. Second, the shuffle of an $m$-associahedron with an $n$-associahedron gives the $(m,n)$-constrainahedron, whose face structure is encoded by $(m,n)$-cotrees, and reflects collisions of particles constrained on a grid. Third, the shuffle of an $m$-anti-associahedron with an $n$-associahedron gives the $(m,n)$-biassociahedron, whose face structure is encoded by $(m,n)$-bitrees, with relevant connections to bialgebras up to homotopy. We provide explicit vertex, facet, and Minkowski sum descriptions of these polytopes, as well as summation formulas for their $f$-polynomials based on generating functionology of decorated trees. \end{abstract} \begin{altabstract} Nous introduisons le mélange de permutaèdres déformés (ou permutaèdres généralisés), une opération associative simple obtenue comme le produit cartésien suivi de la somme de Minkowski avec le zonotope graphique d'un graphe biparti complet. En plus de préserver la classe des zonotopes graphiques (le mélange de deux zonotopes graphiques est le zonotope graphique de la jointure des graphes), cette opération est particulièrement pertinente lorsqu'on l'applique aux permutaèdres et aux associaèdres classiques. Premièrement, le mélange d'un $m$-permutaèdre avec un $n$-associaèdre donne le $(m,n)$-multiplièdre, dont la structure des faces est encodée par des $n$-arbres $m$-peints, généralisant le multiplièdre classique. Nous montrons en particulier que le graphe du $(m,n)$-multiplièdre est le diagramme de Hasse d'un treillis généralisant l'ordre faible sur les permutations et le treillis de Tamari sur les arbres binaires. Deuxièmement, le mélange d'un $m$-associaèdre avec un $n$-associaèdre donne le $(m,n)$-constrainaèdre, dont la structure des faces est encodée par des $(m,n)$-coarbres, et reflète les collisions de particules contraintes sur une grille. Troisièmement, le mélange d'un $m$-anti-associaèdre avec un $n$-associaèdre donne le $(m,n)$-biassociaèdre, dont la structure des faces est codée par des $(m,n)$-biarbres, qui ont des liens intéressants avec les bigèbres à l'homotopie près. Nous fournissons des descriptions explicites des sommets, des facettes et des décompositions en somme de Minkowski de ces polytopes, ainsi que des formules de sommation pour leurs $f$-polynômes basées sur les fonctions génératrices d'arbres décorés. \end{altabstract} \datereceived{2022-09-15} \dateaccepted{2024-07-02} \editors{X. Caruso and M. Bousquet-Mélou} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dateposted{2025-02-07} \begin{document} \maketitle \setcounter{tocdepth}{4} \tableofcontents \begin{figure}[h] \centerline{\includegraphics[scale=.88]{frontPage}} \caption{The $(2,3)$-multiplihedron.}\label{fig:multiplihedron23} \end{figure} \pagebreak \section*{Introduction}\label{sec:intro} The \emph{associahedra}, now very classical objects, have their origin in algebraic topology~\cite{Stasheff}, where they are used to define \emph{associative spaces up-to-homotopy} and \emph{associative algebras up-to-homotopy}. They were first defined as topological cell complexes and later realized as convex polytopes, as explained in~\cite{CeballosZiegler}. For any integer~$n$, the associahedron $\Asso$ is a polytope of dimension $n-1$ whose vertices are labeled by binary trees with $n$ nodes. The axioms of $A_\infty$ algebras encode the fact that each facet of an associahedron can be identified with a product of two smaller associahedra. One important and natural question is to search for a similar clean description of the axioms for \emph{bialgebras up-to-homotopy}. This has been studied by several people~\cite{Markl,MerkulovWillwacher, SaneblidzeUmble-matrads} who have found that one meets new difficulties. The expected picture is the existence, for any pair of integers $(m,n)$, of a \emph{$(m,n)$-biassociahedron} $\Biassociahedron$, a polytope of dimension $m+n-1$ whose vertices are labeled by \emph{binary $(m,n)$-bitrees} (which are pairs of binary trees, growing in opposite directions, with $n$ and $m$ nodes respectively, and that are somehow shuffled). These polytopes are called \emph{step-one biassociahedra} in~\cite{Markl}. The new difficulty is that the facets of these polytopes are no longer products of two smaller biassociahedra, but rather fiber products with respect to natural projection maps to associahedra. This implies that, in order to associate an algebraic homotopy to each facet of a biassociahedra, one needs to decompose each problematic facet into several cells. In the smallest concrete case, the $(2,1)$-biassociahedron $\polytope{B}_{2,1}$ is an hexagon, but one of its edges appears as the diagonal of a square, and must be replaced by half the boundary of this square. For more details on all this, the reader may consult the given references. In this article, we give the first complete description of all biassociahedra as convex polytopes, with detailed vertex and facet descriptions. As far as we know, these objects were previously only known as topological cell complexes, except in small dimensions. As an historical and futile remark, the first author had the idea of the corresponding fans more than twenty years ago, and asked at least twice the second author whether these fans could be normal fans of convex polytopes. While we do not consider here the question of finding good axioms for the bialgebras up-to-homotopy, we hope that our simple setting could be helpful to make progress on this subtle question, whose current status is not really satisfactory. The \emph{constrainahedra} are another family of polytopes closely related to the associahedra and arising in algebraic topology. They should describe the up-to-homotopy version of double semigroups, namely structures endowed with two associative products (horizontal $\bullet$ and vertical $\circ$) that satisfy the compatibility axiom $(a \bullet b) \circ (c \bullet d) = (a \circ b) \bullet (c \circ d)$. To our knowledge, this has not appeared in the literature, possibly because it would involve a variant of operads with two-dimensional inputs. Instead, constrainahedra were introduced as constrained versions of the $2$-associahedra of~\cite{Bottman}. A first sketch-definition of the constrainahedra appeared in~\cite{Tierney}, which was based on a private communication from N.~Bottman. The complete rigorous definition appeared in~\cite{BottmanPoliakova,Poliakova}, where the constrainahedra are also realized as convex polytopes. For any pair of integers $(m,n)$, the \emph{$(m,n)$-constrainahedron} $\Constrainahedron$ is a polytope of dimension $m+n-1$ whose vertices are labeled by good rectangular orders on $[m+n]$ or equivalently by maximal rectangular bracketings in the $(m \times n)$-grid (see~\cite{BottmanPoliakova,Poliakova} for details). Here, we prefer to interpret the vertices as \emph{binary $(m,n)$-cotrees} (which are pairs of binary trees, growing in the same direction, with $n$ and $m$ nodes respectively, and that are somehow shuffled). We provide alternative polytopal realizations of these polytopes, with detailed vertex, facet, and Minkowski sum descriptions. As a side note, let us mention that arbitrary $2$-associahedra do not fit in the framework of this paper. The \emph{multiplihedra} are yet other close relatives of the associahedra, with a very similar story in algebraic topology~\cite{Stasheff-HSpaces}. Their original source is the study of maps between $A_\infty$ algebras, but they appear under various other guises~\cite{ForceyLauveSottile, MauWoodward,SaneblidzeUmble-diagonals}. For instance, because the coproduct in Hopf algebras is a morphism of algebras, the multiplihedra belong to the family of biassociahedra. The interested reader can find a detailed historical exposition in the introduction of~\cite{Forcey-multiplihedra}. As the associahedra, the multiplihedra were originally built as topological cell complexes (or polytopes with subdivided faces), until a polytopal realization was provided in~\cite{ArdilaDoker,Forcey-multiplihedra}. For any integer $n$, the multiplihedron $\polytope{M}\rul(n)$ is a polytope of dimension $n-1$ whose vertices are labeled by painted binary trees with $n$ nodes. In this paper, we include the multiplihedra in a larger family of polytopes. Namely, for any pair of integers $(m,n)$, we construct a \emph{$(m,n)$-multiplihedron} $\Multiplihedron$, a polytope of dimension $m+n-1$ whose vertices are labeled by \emph{$m$-painted binary $n$-trees} (which are binary trees with $n$ nodes painted with $m$ colors). Again, we give detailed vertex, facet, and Minkowski sum descriptions of these polytopes. The classical multiplihedra are obtained when $m = 1$, but our polytopes provide a different realization from that of~\cite{ArdilaDoker,Forcey-multiplihedra}. For general $m$, there is no clear interpretation of the $(m,n)$-multiplihedra in terms of algebraic topology. Our main result is that these three constructions are actually instances of a common natural \emph{shuffle operation} on the family of \emph{deformed permutahedra}. These polytopes are those obtained from the classical permutahedron by moving facets parallely without passing a vertex, or equivalently those whose normal fans coarsen the braid fan. They were studied under the name \emph{polymatroids} by J.~Edmonds~\cite{Edmonds} and rediscovered under the name \emph{generalized permutahedra} by A.~Postnikov~\cite{Postnikov}. Relevant examples of deformed permutahedra include the permutahedra themselves, the graphical zonotopes, the matroid polytopes, the associahedra of~\cite{HohlwegLange,Loday,ShniderSternberg}, the permutreehedra of~\cite{PilaudPons-permutrees}, the quotientopes of~\cite{PadrolPilaudRitter,PilaudSantos-quotientopes}, etc. This paper focuses on the following simple operation on deformed permutahedra. \begin{defi} The \emph{shuffle} of two deformed permutahedra $\polytope{P} \subseteq \R^m$ \linebreak and $\polytope{Q} \subseteq \R^n$ is the Minkowski sum of the Cartesian product $\polytope{P} \times \polytope{Q}$ with the \linebreak segments $[\b{e}_i, \b{e}_{m+j}]$ for all $i \in [m]$ and $j \in [n]$. \end{defi} This shuffle operation preserves deformed permutahedra (since the Cartesian product and the Minkowski sum do). It also preserves the family of graphical zonotopes: the shuffle of two graphical zonotopes is the graphical zonotope of the join of the graphs. But more importantly, it turns out that shuffles of permutahedra and associahedra provide polytopal realizations of the above-mentioned algebraic structures, whose combinatorics is described in details in Sections~\ref{sec:multiplihedra}, \ref{sec:constrainahedra} and~\ref{sec:biassociahedra}. \begin{prop} Let $m$ and $n$ be two positive integers. \begin{enumerate} \item\label{prop0.2.1} The shuffle of an $m$-permutahedron by an $n$-associahedron is an \linebreak \emph{$(m,n)$-multiplihedron}, whose faces are encoded by \emph{$m$-painted $n$-trees}, \item\label{prop0.2.2} The shuffle of an $m$-associahedron by an $n$-associahedron is an \emph{$(m,n)$-cons\-trainahedron}, whose faces are encoded by \emph{$(m,n)$-cotrees}, \item\label{prop0.2.3} The shuffle of an $m$-anti-associahedron by an $n$-associahedron is an \linebreak \emph{$(m,n)$-biassociahedron}, whose faces are encoded by \emph{$(m,n)$-bitrees}. \end{enumerate} \end{prop} This enables us to give precise integer vertex and facet descriptions of polytopal realizations of the $(m,n)$-multiplihedron, the $(m,n)$-constrainahedron, and the $(m,n)$-biassociahedron. Along the way, we also provide summation formulas for their $f$-polynomials based on generating functionology of decorated~trees. As a side note, observe that the shuffle of an $m$-permutahedron with a graph associahedron also generalizes the graph multiplihedra of~\cite{DevadossForcey}. Finally, we study the behavior of the shuffle operation with respect to lattice properties of the deformed permutahedra. Our motivation is the classical fact that, when oriented in the direction $\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n)$, the graph of the permutahedron is the Hasse diagram of the weak order on permutations, and the graph of the associahedron is the Hasse diagram of the Tamari lattice on binary trees. In view of these examples, we say that a deformed permutahedron has the \emph{lattice property} when its graph oriented in the direction $\b{\omega}$ is the Hasse diagram of a lattice. Unfortunately, the shuffle operation does not preserve the lattice property: for instance, the \mbox{$(3,3)$-constrainahedron} and the $(3,3)$-biassociahedron do not have the lattice property. However, the shuffle with a permutahedron preserves the lattice property. \begin{prop} If a deformed permutahedron $\polytope{P}$ has the lattice property, then the shuffle ${\polytope{P} \shuffleDP \Perm}$ has the lattice property for any integer $n \ge 1$. In particular, the graph of the $(m,n)$-multiplihedron oriented by $\b{\omega}$ defines a lattice structure on the $m$-painted $n$-trees. \end{prop} In fact, it is well-known that the Tamari lattice is the quotient of the weak order by the sylvester congruence (where two permutations are equivalent when the corresponding cones of the braid fan belong to the same cone of the normal fan of the associahedron). This implies in particular that the classes of the sylvester congruence are intervals of the weak order. We say that a deformed permutahedron has the \emph{congruence property} (resp.~the \emph{interval property}) when the corresponding equivalence relation on permutations is a lattice congruence of the weak order (resp.~admits only intervals as equivalence classes). We observe that the shuffle operation preserves the interval property but not the congruence property. The paper is organized as follows. In Section~\ref{sec:preliminaries}, we recall definitions and properties of permutahedra, associahedra, graphical zonotopes, deformed permutahedra and lattice congruences. In Section~\ref{sec:shuffles}, we define the shuffle of two deformed permutahedra, describe combinatorially its faces, and discuss the shuffle with a point and the shuffle of graphical zonotopes. Finally, using shuffles of permutahedra and associahedra, we construct the $(m,n)$-multiplihedron in Section~\ref{sec:multiplihedra}, the $(m,n)$-constrainahedron in Section~\ref{sec:constrainahedra}, and the $(m,n)$-associahedron in Section~\ref{sec:biassociahedra}, provide their vertex and facet descriptions, describe their face lattices, and compute their $f$-polynomials. \section{Preliminaries}\label{sec:preliminaries} This section recalls classical definitions and properties concerning polyhedral geometry (Section~\ref{subsec:fansPolytopes}), permutahedra (Section~\ref{subsec:permutahedra}), associahedra (Section~\ref{subsec:associahedra}), graphical zonotopes (Section~\ref{subsec:graphicalZonotopes}), deformed permutahedra (Section~\ref{subsec:deformedPermutahedra}), and lattice congruences (Section~\ref{subsec:latticeProperties}). The reader familiar with these notions is invited to jump directly to Section~\ref{sec:shuffles} and to refer to this section only for conventions and notations. We omit the proofs of all results of this section as they are either well-known or immediate. In fact, we try to attribute properly the results of this section, but consider some of them as folklore, and do not claim anything new in this section. \subsection{Fans and polytopes}\label{subsec:fansPolytopes} We refer to~\cite{Ziegler-polytopes} for a standard reference on polyhedral geometry. We denote by~$(\b{e}_i)_{i\,\in\,[n]}$ the standard basis of $\R^n$. \begin{defi}\label{def:cone} A (polyhedral) \emph{cone} is defined equivalently as \begin{itemize} \item the cone \[ \R_{\ge\,0} \b{R} \eqdef \set{\sum_{\b{r}\,\in \,\b{R}}\lambda_{\b{r}} \b{r}}{\lambda_{\b{r}} \ge 0 \text{ for all } \b{r} \in \b{R}} \] generated by a finite set $\b{R} \subset \R^n$, \item the cone $\{\b{x} \!\in\! \R^n\,|\,\dotprod{\b{n}}{\b{x}} \ge 0 \text{ for all } \b{n} \!\in\! \b{N}\}$ defined by a finite set ${\b{N} \!\subset\! \R^n}$. \end{itemize} A \emph{face} of a cone $\polytope{C}$ is the intersection of $\polytope{C}$ with a supporting hyperplane of $\polytope{C}$. In this paper, we also consider $\polytope{C}$ itself as a face, but ignore the empty face. \end{defi} \begin{defi}\label{def:fan} A (polyhedral) \emph{fan} is a collection $\c{F}$ of cones of $\R^n$ such that \begin{itemize} \item any face of a cone in $\c{F}$ is also in $\c{F}$, \item the intersection of any two cones of $\c{F}$ is a face of both. \end{itemize} The \emph{rays} (resp.~ \emph{walls}, resp.~ \emph{chambers}) of $\c{F}$ are its $1$-dimensional (resp.~codimension~$1$, resp.~full-dimensional) cones. \end{defi} \begin{defi}\label{def:polytope} A \emph{polytope} is defined equivalently as \begin{itemize} \item the convex hull \[ \set{\sum_{\b{v}\, \in\,\b{V}} \lambda_{\b{v}} \b{v}}{\lambda_{\b{v}} \ge 0 \text{ for all } \b{v} \in \b{V} \text{ and } \sum_{\b{v}\,\in\,\b{V}} \lambda_{\b{v}} = 1} \] of a finite set ${\b{V} \in \R^n}$, \item a bounded intersection of a finite number of affine half-spaces of $\R^n$. \end{itemize} A \emph{face} of a polytope $\polytope{P}$ is the intersection of $\polytope{P}$ with a supporting hyperplane of $\polytope{P}$. The \emph{vertices} (resp.~ \emph{edges}, resp.~ \emph{facets}) are the $0$-dimensional (resp. $1$-dimensional, resp.~codimension $1$) faces. In this paper, we also consider $\polytope{P}$ itself as a face, but ignore the empty face. \end{defi} Any polytope defines a fan as follows (in contrast, not all fans come from polytopes). \begin{defi}\label{def:normalFan} Let $\polytope{P}$ be a polytope and $\polytope{F}$ be a face of $\polytope{P}$. The \emph{normal cone} of $\polytope{F}$ is the cone \[ \c{N}(\polytope{F}) \eqdef \set{\b{v} \in \R^n}{\dotprod{\b{v}}{\b{f}} \ge \dotprod{\b{v}}{\b{p}} \text{ for all } \b{f} \in \polytope{F} \text{ and } \b{p} \in \polytope{P}} \] of linear functions maximized over $\polytope{P}$ by all the face $\polytope{F}$. The \emph{normal fan} of $\polytope{P}$ is the fan \[ \c{N}(\polytope{P}) \eqdef \set{\c{N}(\polytope{F})}{\polytope{F} \text{ face of } \polytope{P}} \] containing the normal cones of all faces of $\polytope{P}$. \end{defi} In this paper, we will use the following standard operations on fans and polytopes. \begin{defi}\label{def:directSumCommonRefinement} Let $\c{F} \subset \R^m$ and $\c{G} \subset \R^n$ be two fans. Then \begin{itemize} \item the \emph{direct sum} of $\c{F}$ and $\c{G}$ is the fan \[ \c{F} \oplus \c{G} \eqdef \set{C \times D}{C \in \c{F} \text{ and } D \in \c{G}}, \] \item if $m = n$, the \emph{common refinement} of $\c{F}$ and $\c{G}$ is the fan \[ \c{F} \wedge \c{G} \eqdef \set{C \cap D}{C \in \c{F} \text{ and } D \in \c{G}}. \] \end{itemize} \end{defi} \begin{defi}\label{def:CartesianProductMinkowskiSum} Let $\polytope{P} \subset \R^m$ and $\polytope{Q} \subset \R^n$ be two polytopes. Then \begin{itemize} \item the \emph{Cartesian product} of $\polytope{P}$ and $\polytope{Q}$ is the polytope \[ \polytope{P} \times \polytope{Q} \eqdef \set{(\b{p},\b{q})}{\b{p} \in \polytope{P} \text{ and } \b{q} \in \polytope{Q}}, \] \item if $m = n$, the \emph{Minkowski sum} of $\polytope{P}$ and $\polytope{Q}$ is the polytope \[ \polytope{P} + \polytope{Q} \eqdef \set{\b{p}+\b{q}}{\b{p} \in \polytope{P} \text{ and } \b{q} \in \polytope{Q}}. \] \end{itemize} \end{defi} The following connection between Definitions~\ref{def:directSumCommonRefinement} and~\ref{def:CartesianProductMinkowskiSum} is classical, see~\cite[Lems.~7.7 \& 7.12]{Ziegler-polytopes}. \begin{prop}\label{prop:CartesianProductMinkowskiSum} Let $\polytope{P} \subset \R^m$ and $\polytope{Q} \subset \R^n$ be two polytopes. Then \begin{itemize} \item the normal fan of the Cartesian product $\polytope{P} \times \polytope{Q}$ is the direct sum of the normal fans of $\polytope{P}$~and $\polytope{Q}$, that is $\c{N}(\polytope{P} \times \polytope{Q}) = \c{N}(\polytope{P}) \oplus \c{N}(\polytope{Q})$, \item if $m = n$, the normal fan of the Minkowski sum $\polytope{P} + \polytope{Q}$ is the common refinement of the normal fans of $\polytope{P}$ and $\polytope{Q}$, that is $\c{N}(\polytope{P} + \polytope{Q}) = \c{N}(\polytope{P}) \wedge \c{N}(\polytope{Q})$. \end{itemize} \end{prop} \subsection{Permutahedra}\label{subsec:permutahedra} Let $\f{S}_n$ denote the symmetric group of permutations of $[n] \eqdef \{1,\, \dots,\, n\}$. \begin{figure} \centerline{ \includegraphics[scale=.55]{permutahedron} \quad \raisebox{-.1cm}{\includegraphics[scale=.55]{braidFan}} \quad \includegraphics[scale=.50]{weakOrder}} \caption{The permutahedron, the braid fan, and the weak order.}\label{fig:permutahedron} \end{figure} \begin{defi}\label{def:permutahedron} The \emph{permutahedron} $\Perm$ is the polytope in $\R^n$ equivalently defined as: \begin{itemize} \item the convex hull of the points $\sum_{i\,\in\,[n]} i \, \b{e}_{\sigma(i)}$ for all permutations $\sigma \in \f{S}_n$, \item or the intersection of the hyperplane $\{\b{x} \in \R^n\,|\,\sum_{i\,\in\,[n]} x_i = (\begin{smallmatrix}n+1\\2\end{smallmatrix})\}$ with the affine half-spaces $\{\b{x} \in \R^n\,|\,\sum_{i\,\in\,I} x_i \ge (\begin{smallmatrix}|I|+1\\2\end{smallmatrix})\}$ for all ${\varnothing \ne I \subsetneq [n]}$, \item or (a translate of) the Minkowski sum of all segments $[\b{e}_i, \b{e}_j]$ for\newline all $1 \le i < j \le n$. \end{itemize} See Figure~\ref{fig:permutahedron}$\MK$(left). \end{defi} The permutahedron $\Perm$ has dimension $n-1$ but it will be convenient to consider it embedded in $\R^n$. Note that the point corresponding to a permutation $\sigma$ is the point of coordinates $(\sigma^{-1}(1),\, \dots,\,\sigma^{-1}(n))$. The face structure of the permutahedron is encoded by ordered~partitions. \begin{defi}\label{def:orderedPartitions} An \emph{ordered partition} of $[n]$ is a partition $\mu \eqdef \mu_1 | \dots | \mu_p$ of~$[n]$ into non-empty parts, with a total order on the parts (but each part is unordered). It defines a preposet (\ie a reflexive and transitive binary relation) $\preccurlyeq_\mu$ on $[n]$ where~${i \preccurlyeq_\mu j}$ if the part of $\mu$ containing $i$ is before or equal to the part of~$\mu$ containing~$j$. The resulting preposets are all total preposets, that is, where any two elements of~$[m]$ are comparable (\ie $i \preccurlyeq j$ or $i \succcurlyeq j$ or both). For two ordered partitions $\mu$ and~$\nu$, we say that $\mu$ \emph{refines} $\nu$ (and $\nu$ \emph{coarsens} $\mu$) when $i \preccurlyeq_\mu j$ implies~$i \preccurlyeq_\nu j$ for any~$i,j \in [n]$. We denote by $\f{P}_n$ the set of ordered partitions of $[n]$. \end{defi} \begin{prop}\label{prop:permutahedron} The face lattice of the permutahedron $\Perm$ is isomorphic to the refinement poset on $\f{P}_n$ (augmented with a minimal element). \end{prop} \begin{prop}\label{prop:braidFan} The normal fan of the permutahedron $\Perm$ is the \emph{braid fan} with one cone $\polytope{C}(\mu) \eqdef \{\b{x} \in \R^n\,|\,x_i \le x_j \text{ if } i \preccurlyeq_\mu j\}$ for each $\mu \in \f{P}_n$. Its walls are given by the arrangement of the hyperplanes $\{\b{x} \in \R^n\,|\,x_i = x_j\}$ for \linebreak all ${1 \le i < j \le n}$. See Figure~\ref{fig:permutahedron}$\MK$(middle). \end{prop} We now recall the connection between the graph of the permutahedron $\Perm$ and the weak order on permutations of $\f{S}_n$. \begin{defi}\label{def:weakOrder} An \emph{inversion} of a permutation $\sigma$ is a pair $(\sigma_i, \sigma_j)$ such that~${i < j}$ but ${\sigma_i > \sigma_j}$. The \emph{weak order} is the lattice on permutations of $[n]$ defined by inclusion of their inversion sets. See Figure~\ref{fig:permutahedron}$\MK$(right). \end{defi} \begin{prop}\label{prop:weakOrder} When oriented in the direction \[ \b{\omega} \eqdef (n,\dots,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i, \] the graph of the permutahedron $\Perm$ is the Hasse diagram of the weak order on~$\f{S}_n$. \end{prop} \subsection{Associahedra}\label{subsec:associahedra} We now recall the classical associahedra, whose vertices (resp.~faces) correspond to binary trees (resp.~Schr\"oder trees). We start with some formal definitions on rooted plane trees used later in Sections~\ref{subsec:paintedTrees}, \ref{subsec:cotrees} and~\ref{subsec:bitrees}. Definitions~\ref{def:tree}, \ref{def:inorder}, \ref{def:treeDeletion} and~\ref{def:binaryTreeSchroderTree} are illustrated in Figure~\ref{fig:trees}. \begin{defi}\label{def:tree} A (rooted plane) \emph{tree} is either a \emph{leaf} $|$ or a \emph{node} $\node{n}$ with an ordered non-empty list $\children(\node{n})$ of (rooted plane) trees. The node $\node{n}$ is the \emph{parent} of the nodes in $\children(\node{n})$, which are the \emph{children} of $\node{n}$. The \emph{degree} of $\node{n}$ is its number of children. The \emph{root} is the unique node with no parent. An \emph{$n$-tree} is a tree with $n+1$ leaves. \end{defi} \begin{defi}\label{def:inorder} A $n$-tree $T$ is labeled in \emph{inorder} when each degree $\ell$ node is labeled by an $(\ell-1)$-subset $\{x_1,\,\dots,\, x_{\ell-1}\}$ of $[n]$ such that all labels in its $i^{\rm th}$ subtree are larger than $x_{i-1}$ and smaller than $x_i$ (where by convention $x_0 = 0$ and $x_\ell = n+1$). It defines a preposet $\preccurlyeq_T$ on $[n]$ where $i \preccurlyeq_T j$ if there is a (possibly empty) path from the node containing $i$ to the node containing $j$ in the tree $T$ oriented towards the root. The resulting preposets are all preposets $\preccurlyeq$ such that any $1 \le i < k \le n$ are comparable (\ie $i \preccurlyeq k$ or $i \succcurlyeq k$ or both) if and only if there is no $i < j < k$ such that~$i \prec j \succ k$. \end{defi} \begin{defi}\label{def:treeDeletion} The \emph{deletion} of a node $\node{n}$ with parent $\node{p}$ consists in replacing $\node{n}$ by the list $\children(\node{n})$ in the list $\children(\node{p})$. Intuitively, this operation contracts the edge from $\node{n}$ to $\node{p}$ in the tree. \end{defi} \begin{figure}[b] \centerline{ \begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c} \includegraphics[scale=.9]{tree1} & \includegraphics[scale=.9]{tree2} & \includegraphics[scale=.9]{tree3} & \includegraphics[scale=.9]{tree4} \\[-.1cm] $T_1$ & $T_2$ & $T_3$ & $T_4$ \end{tabular} } \caption{A (plane rooted) tree $T_1$ with a circled node, the tree $T_2$ obtained by deletion of the circled node in $T_1$, a binary tree $T_3$, and a Schr\"oder tree $T_4$. All trees are labeled in inorder (at each node, we simply write the word $x_1 \dots x_{\ell-1}$ for the set $\{x_1,\,\dots,\,x_{\ell-1}\}$).}\label{fig:trees} \end{figure} \begin{defi}\label{def:binaryTreeSchroderTree} A \emph{binary} (resp.~ \emph{Schr\"oder}) \emph{tree} is a rooted plane tree whose internal nodes have degree exactly (resp.~at least) $2$. We denote by $\f{B}_n$ (resp. $\f{T}_n$) the set of \mbox{binary (resp.~Schr\"oder) $n$-trees.} \end{defi} \begin{prop}\label{prop:SchroderTreeDeletion} For any integer $n \ge 0$, the set $\f{T}_n$ is stable by deletion, and the deletion graph is the Hasse diagram of a poset ranked by \[ {\rank(T) = \sum_{\node{n}\,\in\,T} \big(\!\deg(\node{n})-2 \big)} = n - |T|. \] In this poset, $S$ is smaller than $T$ if and only if $\preccurlyeq_S$ refines $\preccurlyeq_T$. The binary trees are the minimal elements, and the corolla is the unique maximal element of this poset. \end{prop} \begin{defi}\label{def:SchroderTreeDeletionPoset} The \emph{$n$-Schr\"oder tree deletion poset} is the poset on $\f{T}_n$ where a Schr\"oder tree is covered by all Schr\"oder trees that can be obtained by a deletion. \end{defi} We now recall a classical geometric realization of this poset, tracing back to~\cite{Loday, Postnikov,ShniderSternberg}. Generalizations of this construction were explored in~\cite{HohlwegLange, HohlwegLangeThomas, HohlwegPilaudStella, PilaudPons-permutrees, PadrolPaluPilaudPlamondon, Pilaud-acyclicReorientationLattices} among others. See~\cite{PilaudSantosZiegler} for a recent survey. \begin{figure} \centerline{\includegraphics[scale=.53]{associahedron} \quad \raisebox{-.1cm}{\includegraphics[scale=.53]{sylvesterFan}} \quad \includegraphics[scale=.47]{TamariLattice}} \caption{The associahedron, the sylvester fan, and the Tamari lattice.}\label{fig:associahedron} \end{figure} \begin{defi}\label{def:associahedron} The \emph{associahedron} $\Asso$ is the polytope in $\R^n$ equivalently defined as: \begin{itemize} \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 \!\in\! \f{B}_n}$, where $\ell(T,i)$ and $r(T,i)$ respectively denote the numbers of leaves in the left and right subtrees of the $i^{\rm th}$ node of $T$ in inorder (see~\cite{Loday}), \item or the intersection of the hyperplane $\{\b{x} \in \R^n\,|\,\sum_{i\,\in\,[n]} x_i = (\begin{smallmatrix}n+1\\ 2\end{smallmatrix})\}$ with the affine half-spaces $\{\b{x} \in \R^n\,|\,\sum_{i\,\le\,\ell \,\le\,j} x_\ell \ge (\begin{smallmatrix} j-i+2\\2\end{smallmatrix})\}$ for all $1 \le i \le j \le n$ (see~\cite{ShniderSternberg}), \item or (a translate of) the Minkowski sum of the faces $\simplex_{[i,j]}$ of the standard simplex $\simplex_{[n]}$ for all ${1 \le i \le j \le n}$, where $\simplex_X \eqdef \conv\{\b{e}_x\,|\,x \in X\}$ for $X \subseteq [n]$ (see~\cite{Postnikov}). \end{itemize} See Figure~\ref{fig:associahedron}$\MK$(left). \end{defi} The associahedron $\Asso$ has dimension $n-1$, although it is convenient to consider it embedded in $\R^n$. Note that any facet defining inequality for $\Asso$ is also a facet defining inequality for $\Perm$. In other words, the associahe\-dron~$\Asso$ is a \emph{removahedron}: it can be obtained by deleting some inequalities in the facet description of the permutahedron $\Perm$. \begin{prop}[\cite{Loday}]\label{prop:associahedron} The face lattice of the associahedron $\Asso$ is isomorphic to the deletion poset on $\f{T}_n$ (augmented with a minimal element). \end{prop} \begin{prop}\label{prop:sylvesterFan} The normal fan of the associahedron $\Asso$ is the \emph{sylvester fan} with one cone $\polytope{C}(S) \eqdef \{\b{x} \in \R^n\,|\,x_i \le x_j \text{ if } i \preccurlyeq_S j\}$ for each $S \in \f{T}_n$. See Figure~\ref{fig:associahedron}\,(middle). \end{prop} Note that here and throughout, sylvester is an ancient adjective for woody, and has nothing to do with the mathematician James Joseph Sylvester. It turns out that the sylvester fan of Proposition~\ref{prop:sylvesterFan} coarsens the braid fan of Proposition~\ref{prop:braidFan}. \begin{prop}\label{prop:fanRefinementSylvester} The braid fan refines the sylvester fan. More precisely, for any Schr\"oder tree $S$, the sylvester cone $\polytope{C}(S)$ is the union of the braid cones $\polytope{C}(\mu)$ for the ordered partitions $\mu$ such that $\preccurlyeq_\mu$ extends $\preccurlyeq_S$ (meaning that $i \!\preccurlyeq_S\! j$ implies~$i \!\preccurlyeq_\mu\! j$ for any $i,j \in [n]$). \end{prop} This can be interpreted as equivalence relations on permutations and on ordered partitions. \begin{defi}\label{def:sylvesterRelation} The \emph{sylvester relation} on ordered partitions of $[n]$ is the equivalence relation $\equiv_\sylv$ defined by $\mu \equiv_\sylv \nu$ if and only if the cones $\polytope{C}(\mu)$ and~$\polytope{C}(\nu)$ of the braid fan belong precisely to the same cones of the sylvester fan. It also restricts to an equivalence relation on permutations. \end{defi} \begin{rema}\label{rem:sylvesterRelation} The sylvester relation on permutations admits several equivalent definitions. Namely, two permutations $\sigma, \tau \in \f{S}_n$ are equivalent when: \begin{itemize} \item $\sigma$ and $\tau$ are linear extensions of the poset $\preccurlyeq_T$ for the same binary tree $T$ of~$\f{B}_n$, \item $\sigma$ and $\tau$ are sent to the same binary tree $T$ via right-to-left binary search tree insertions, \item the braid cones $\polytope{C}(\sigma)$ and $\polytope{C}(\tau)$ of the braid fan belong to the same sylvester cone $\polytope{C}(T)$, \item $\sigma$ and $\tau$ are connected via a sequence of rewritings of the form $UacVbW \equiv UcaVbW$ where $1 \le a < b < c \le n$ and $U,V,W$ are words on $[n]$. \end{itemize} \end{rema} We now recall the connection between the graph of the associahedron $\Asso$ and the Tamari lattice on binary trees of $\f{B}_n$ illustrated in Figure~\ref{fig:associahedron}$\MK$(right). \begin{defi}\label{def:TamariLattice} A \emph{right rotation} is the operation on binary trees illustrated on the right (this operation can be applied locally anywhere in the tree). The \emph{Tamari lattice} is the lattice on $\f{B}_n$ whose Hasse diagram is the graph of right rotations. See Figure~\ref{fig:associahedron}$\MK$(right). \end{defi} \begin{prop}\label{prop:TamariLattice} When oriented in the direction \[ \b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i, \] the graph of the associahedron $\Asso$ is the Hasse diagram of the Tamari lattice on $\f{B}_n$. \end{prop} \begin{rema}\label{rem:latticeQuotient} In fact, the sylvester relation is a lattice congruence of the weak order (meaning that it respects meets and joins), and the Tamari lattice is the quotient of the weak order by the sylvester congruence. This perspective has been largely explored by N.~Reading in his study of lattice congruences of the weak order~\cite{Reading-latticeCongruences}. In this paper, we do not consider this property as it is not stable by the shuffle operation we focus on. See Section~\ref{subsec:latticeProperties}. \end{rema} We conclude with some classical numerology on binary and Schr\"oder trees that will be generalized to multiplihedra, constrainahedra, and biassociahedra in Sections~\ref{subsec:numerologyMultiplihedra}, \ref{subsec:numerologyConstrainahedra} and~\ref{subsec:numerologyBiassociahedra}. \begin{nota}\label{not:CatalanSchroderGF} Let $C(n) = \frac{1}{n+1} \binom{2n}{n}$ denote the \emph{Catalan number} of binary trees with $n+1$ leaves and let $S(n,p)$ denote the \emph{Schr\"oder number} of Schr\"oder trees with $n+1$ leaves and $n-p$ internal nodes. We denote the corresponding generating functions by \[ \CGF(y) \eqdef \sum_{n\,\ge\,1} C(n) \, y^n \qquad\text{and}\qquad \SGF(y,z) \eqdef \sum_{n\,\ge\,1,\,p\,\ge\,0} S(n,p) \, y^n \, z^p. \] \end{nota} \begin{prop}\label{prop:CatalanSchroderGF} The generating functions $\CGF(y)$ of binary trees (\ie vertices of associahedra) and $\SGF(y,z)$ of Schr\"oder trees (\ie faces of associahedra) satisfy \[ \CGF(y) = y + \CGF(y)^2 \qquad\text{and}\qquad \SGF(y,z) = y + \frac{\SGF(y,z)^2}{1-z\SGF(y,z)} \] and are therefore given by \[ \CGF(y) = \frac{1-\sqrt{1-4y}}{2} \qquad\text{and}\qquad \SGF(y,z) = \frac{1+yz-\sqrt{1-4y-2yz+y^2z^2}}{2(z+1)}. \] \end{prop} \subsection{Graphical zonotopes}\label{subsec:graphicalZonotopes} In this section, we consider a simple (no loop nor multiple edges) non-oriented graph $G$, with vertex set $V(G)$ and edge set $E(G)$. We say that $G$ is an integer graph when $V(G) = [n]$, and we then represent the edges of $G$ by ordered pairs $(i,j)$ with~$1 \le i < j \le n$. \begin{defi}\label{def:graphicalZonotope} The \emph{graphical zonotope} $\Zono[G]$ of an integer graph $G$ is the Minkowski sum of the segments $[\b{e}_i, \b{e}_j]$ for ${(i,j) \in E(G)}$. See Figure~\ref{fig:graphicalZonotopes}$\MK$(left). \end{defi} \begin{figure} \centerline{ \raisebox{.6cm}{\includegraphics[scale=.9]{graphicalZonotope2}} \quad \includegraphics[scale=.6]{graphicalFan2} \quad \includegraphics[scale=.8]{acyclicReorientationPoset2} } \caption{A graphical zonotope, its graphical fan, and its acyclic orientation poset.}\label{fig:graphicalZonotopes} \end{figure} For instance, the graphical zonotope of the complete graph (resp.~path, resp.~empty graph) on $[n]$ is the permutahedron $\Perm$ (resp.~a parallelotope denoted $\Para$, resp.~a point denoted $\Point$). We need the following definition to describe the face structure of graphical zonotopes. We refer to~\cite{Greene} and~\cite[Sect.~7]{GreeneZaslavsky} for the original references. \pagebreak \begin{defi}\label{def:Gpartition} A \emph{$G$-ordered partition} is a pair $\Pi = (\pi, \omega)$, where \begin{itemize} \item $\pi$ is a partition of $[n]$ where each part induces a connected subgraph of $G$, \item $\omega$ is an acyclic orientation on the quotient graph $G/\pi$. \end{itemize} It defines a preposet $\preccurlyeq_\Pi$ on $[n]$, where $i \preccurlyeq_\Pi j$ if and only if there is a (possibly empty) oriented path in $\omega$ joining the part of $\pi$ containing $i$ to the part of $\pi$ containing $j$. For two $G$-ordered partitions $\Pi$ and $\Theta$, we say that $\Pi$ refines $\Theta$ (and $\Theta$ coarsens $\Pi$) when $i \preccurlyeq_\Pi j$ implies $i \preccurlyeq_\Theta j$ for any $i,j \in [n]$. \end{defi} \begin{prop}[{\cite[Sect.~7]{GreeneZaslavsky}}]\label{prop:facesGraphicalZonotope} The face lattice of the graphical zonotope~$\Zono[G]$ is isomorphic to the refinement poset on $G$-ordered partitions (augmented with a minimal element). In particular, \begin{itemize} \item the vertices of $\Zono[G]$ are in bijection with \emph{acyclic orientations} of $G$, \item the facets of $\Zono[G]$ are in bijection with \emph{biconnected subsets} of $G$, \ie non-empty connected subset $U \subset V$ whose complement $\bar U$ in its connected component of $G$ is also non-empty and connected. \end{itemize} \end{prop} For instance for the complete graph $K_n$, the $K_n$-ordered partitions are all ordered partitions (in the classical sense), the acyclic orientations are given by permutations, and the biconnected subsets are all proper subsets. \begin{prop}\label{prop:graphicalFan} The normal fan of the graphical zonotope $\Zono[G]$ is the \emph{graphical fan} $\Fan[G]$ with one cone $\polytope{C}(\pi) \eqdef \{\b{x} \in \R^n\,|\,x_i \le x_j \text{ if } i \preccurlyeq_\Pi j\}$ for each \linebreak $G$-ordered partition $\Pi$. Its walls are given by the arrangement of the hyperplanes \linebreak $\{\b{x} \in \R^n\,|\,x_i = x_j\}$ for all $(i,j) \in E(G)$. See Figure~\ref{fig:graphicalZonotopes}\,(middle). \end{prop} As for the sylvester fan of Proposition~\ref{prop:sylvesterFan}, the graphical fan of Proposition~\ref{prop:graphicalFan} coarsens the braid fan of Proposition~\ref{prop:braidFan}. \begin{prop}\label{prop:fanRefinementGraphical} The braid fan refines the graphical fan $\Fan[G]$. More precisely, for a $G$-ordered partition $\Pi$, the cone $\polytope{C}(\Pi)$ is the union of the braid cones~$\polytope{C}(\mu)$ for the ordered partitions $\mu$ such that $\preccurlyeq_\mu$ extends $\preccurlyeq_\Pi$. \end{prop} This can be interpreted as an equivalence relation on permutations and on ordered partitions, similar to the sylvester relation discussed in Definition~\ref{def:sylvesterRelation} and Remark~\ref{rem:sylvesterRelation}. \begin{defi}\label{def:graphicalRelation} The \emph{graphical relation $\equiv_G$} on ordered partitions of $[n]$ is defined by $\mu \equiv_G \nu$ if and only if the cones $\polytope{C}(\mu)$ and $\polytope{C}(\nu)$ of the braid fan belong precisely to the same cones of the graphical fan $\Fan[G]$. Equivalently, $\mu \equiv_G \nu$ if and only if $i \preccurlyeq_\mu j \iff i \preccurlyeq_\nu j$ for any edge $(i,j)$ of $G$. It restricts to an equivalence relation on permutations, which can also be seen as the transitive closure of the rewriting rule $UabV \equiv_G UbaV$ for all words $U,V$ on $[n]$ and elements $a,b$ in $[n]$ which do not form an edge of $G$. \end{defi} We now orient the graph of the graphical zonotope $\Zono[G]$ as in Propositions~\ref{prop:weakOrder} and~\ref{prop:TamariLattice}. \begin{defi}\label{def:inversionAcyclicOrientation} An \emph{inversion} of an acyclic orientation $\omega$ of an integer \linebreak graph $G$ is an edge $\{i, j\}$ of $G$ such that $i < j$ but the edge goes from $j$ to $i$ in the orientation $\omega$. The \emph{acyclic orientation poset} of $G$ is the poset on acyclic orientations of $G$ defined by inclusion of their inversion sets. See Figure~\ref{fig:graphicalZonotopes}$\MK$(right). \end{defi} \begin{prop}\label{prop:acyclicOrientationPoset} When oriented in the direction \[ {\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}, \] the graph of the graphical zonotope $\Zono[G]$ is the Hasse diagram of the acyclic orientation poset of $G$. \end{prop} \begin{rema}\label{rem:acyclicOrientationPosetNotLattice} In contrast to Propositions~\ref{prop:weakOrder} and~\ref{prop:TamariLattice}, the acyclic orientation poset is not always a lattice, as will be discussed in more details in Proposition~\ref{prop:latticePropertiesGraphicalZonotopes} (see also~\cite{Pilaud-acyclicReorientationLattices}). \end{rema} In contrast to the permutahedra and braid fans of Section~\ref{subsec:permutahedra} and as illustrated in Figure~\ref{fig:graphicalZonotopes}, the graphical zonotope $\Zono[G]$ is not always simple and the graphical fan~$\Fan[G]$ is not always simplicial. The following characterization was stated in~\cite[Rem.~6.2]{Kim}, \cite[Prop.~5.2]{PostnikovReinerWilliams} and~\cite[Prop.~52]{Pilaud-acyclicReorientationLattices} (the immediate proof is omitted in the first two). \begin{prop}\label{prop:simpleGraphicalZonotope} The graphical zonotope $\Zono[G]$ is simple (or equivalently, the graphical fan $\Fan[G]$ is simplicial) if and only if $G$ is chordful, meaning that any cycle of $G$ induces a clique of $G$. \end{prop} We now want to underline that the Cartesian products and Minkowski sums of Definition~\ref{def:CartesianProductMinkowskiSum} preserve the family of graphical zonotopes. \begin{defi}\label{def:disjointUnionEdgeUnionGraphs} For two graphs $G$ and $H$, \begin{itemize} \item if $V(G) \cap V(H) = \varnothing$, then the \emph{disjoint union} $G \sqcup H$ is the graph with \linebreak $V(G \sqcup H) = V(G) \sqcup V(H)$ and $E(G \sqcup H) = E(G) \sqcup E(H)$, \item if $V(G) = V(H)$ and $E(G) \cap E(H) = \varnothing$, then the \emph{superposition} $G \oplus H$ is the graph with ${V(G \oplus H) = V(G) = V(H)}$ and $E(G \oplus H) = E(G) \sqcup E(H)$. \end{itemize} \end{defi} \begin{defi}\label{def:shiftedIntegerGraphs} For two graphs $G$ on $[m]$ and $H$ on $[n]$, define \begin{itemize} \item the \emph{shifted graph} $H^{+m}$ as the graph with vertices $[n]^{+m} \eqdef \{m+1,\,\dots,\,m+n\}$ and edges $E(H)^{+m} \eqdef \{(m+i, m+j)\,|\,(i,j) \in E(H)\}$, \item the \emph{shifted union} as $G \otimes H \eqdef G \sqcup H^{+m}$. \end{itemize} \end{defi} \begin{prop}\label{prop:operationsGraphsZonotopes} For all graphs $G$ on $[m]$ and $H$ on $[n]$, \begin{itemize} \item $\Zono[G] \times \Zono[H] = \Zono[G \otimes H]$. \item if $m = n$ and $E(G) \cap E(H) = \varnothing$, then $\Zono[G] + \Zono[H] = \Zono[G \oplus H]$. \end{itemize} \end{prop} Note that if $E(G) \cap E(H) \ne \varnothing$, then $\Zono[G \oplus H]$ has the same combinatorics, but not the same geometry as $\Zono[G] + \Zono[H]$. In this paper, we will anyway only need Minkowski sums of graphical zonotopes of graphs with disjoint edge sets. Finally, we briefly describe the graphical zonotopes of complete multipartite \linebreak graphs, that will play a crucial role in this paper. \begin{defi}\label{def:completeMultipartiteGraphicalZonotope} We consider a $k$-tuple $\b{n} = (n_1,\,\dots,\,n_k)$ of positive integers, and let ${n \eqdef n_1 + \dots + n_k}$ and $V_1 \eqdef [n_1]$, $V_2 \eqdef [n_2]^{+n_1}$, \dots, $V_k \eqdef [n_k]^{+n_1 + \dots + n_{k-1}}$. We denote by $K_{\b{n}}$ the \emph{complete multipartite graph} with vertex set $V(K_{\b{n}}) \eqdef [n] = V_1 \sqcup \dots \sqcup V_k$ and edge set $E(K_{\b{n}}) \eqdef \bigcup_{1\,\le\,i\,< \,j\,\le\,k} V_i \times V_j$. We denote by ${\polytope{Z}_{\b{n}} = \Zono[K_{\b{n}}]}$ its graphical zonotope. For $m,n \in \N$, we often write $K_{m,n}$ and $\polytope{Z}_{m,n}$ instead of $K_{(m,n)}$ and $\polytope{Z}_{(m,n)}$. \end{defi} \begin{figure} \centerline{\includegraphics[scale=1]{labelingsGraphicalZonotope}} \caption{The graphical zonotope $\polytope{Z}_{(2,1)}$ with faces labeled by $K_{(2,1)}$-ordered partitions (left) and by ordered partitions of $[3]$ with no two consecutive parts contained in $\{1,2\}$ (right).}\label{fig:labelingsGraphicalZonotope} \end{figure} As discussed in Definition~\ref{def:Gpartition} and Proposition~\ref{prop:facesGraphicalZonotope}, the combinatorial structure of~$\polytope{Z}_{\b{n}}$ is given by $K_{\b{n}}$-ordered partitions. It turns out that these $K_{\b{n}}$-ordered partitions are almost ordered partitions of $[n]$ in the classical sense. Indeed, note that \begin{itemize} \item a subset of $[n]$ induces a connected subgraph of $K_{\b{n}}$ if and only if either it is a singleton or it is not contained in one of the $V_i$'s, \item two such sets are connected by an edge except if they are two singletons in the same $V_i$. \end{itemize} Therefore, given a $K_{\b{n}}$-ordered partition $\Pi = (\pi,\omega)$, the preposet $\preccurlyeq_\Pi^\star$ obtained from~$\preccurlyeq_\Pi$ by adding all relations between incomparable elements of $\preccurlyeq_\Pi$ is the preposet of an ordered partition, with the property that no two consecutive parts are included in the same $V_i$. Conversely, given such an ordered partition $\mu$, the preposet $\preccurlyeq_\mu^{\b{n}}$ obtained from $\preccurlyeq_\mu$ by deleting all relations inside each part of $\mu$ completely contained in one of the $V_i$'s is the preposet of a $K_{\b{n}}$-ordered partition. The correspondence between these two combinatorial descriptions of the faces of $\polytope{Z}_{\b{n}}$ is illustrated in Figure~\ref{fig:labelingsGraphicalZonotope}. The following statement summarizes this observation. \begin{prop}\label{prop:completeMultipartiteGraphicalZonotopeFaces} The faces of the graphical zonotope $\polytope{Z}_{\b{n}}$ are in bijection with the ordered partitions of $[n]$ where no two consecutive parts are included in the same $V_i$. The vertices of $\polytope{Z}_{\b{n}}$ then correspond to those ordered partitions where each part is included in some $V_i$. \end{prop} The poset of Proposition~\ref{prop:acyclicOrientationPoset} can then be read on the partition model as follows. %\pagebreak \begin{prop}\label{prop:completeMultipartiteGraphicalZonotopeRotationPosets} Consider two ordered partitions $\mu$ and $\mu'$ where each part is contained in some $V_i$, and let $\b{v}$ and $\b{v}'$ denote the corresponding vertices of $\polytope{Z}_{\b{n}}$. There is a path from $\b{v}$ to $\b{v}'$ in the graph of $\polytope{Z}_{\b{n}}$ oriented in the direction~${\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}$ if and only if $p \preccurlyeq_\mu q$ implies~$p \preccurlyeq_{\mu'} q$ for any $p \in V_i$ and $q \in V_j$ with $1 \le i < j \le k$. \end{prop} One also easily derives from Proposition~\ref{prop:completeMultipartiteGraphicalZonotopeFaces} the number of vertices of $\polytope{Z}_{\b{n}}$ by encoding such an ordered partition into a word with no consecutive identical letters and some surjections. For ${\b{n} = (m,n)}$, this yields poly-Bernoulli numbers, see~\cite{ArakawaKaneko-multipleZetaValues,ArakawaKaneko-polyBernoulli,BenyiHajnal-polyBernoulli1, BenyiHajnal-polyBernoulli2,CameronGlassSchumacher,Kaneko-polyBernoulli}. \begin{prop}\label{prop:completeMultipartiteGraphicalZonotopeNumberVertices} Let $\surjections{n}{k}$ denotes the number of surjections from $[n]$ to~$[k]$ (see~\cite[\OEIS{A019538}]{OEIS}). The number of vertices of the graphical zonotope $\polytope{Z}_{\b{n}}$ is given by the summation formula \[ \sum_{w\, \in\,W_k}\; \prod_{i\,\in\,[k]} \surjections{n_i}{|w|_i}, \] where $W_k$ is the set of words on the alphabet $[k]$ containing at least one copy of each letter and no consecutive identical letters, and $|w|_i$ denotes the number of letters $i$ in the word $w$. In particular, when $\b{n} = (m,n)$, we obtain the poly-Bernoulli number (see~\cite{Kaneko-polyBernoulli}, \cite [\OEIS{A099594}]{OEIS}, and~\cite{CameronGlassSchumacher} for an explanation of the formula) \[ B(-m,n) \eqdef \sum_{\ell\,\ge\,0} \frac{\surjections{m+1}{\ell+1} \, \surjections{n+1}{\ell+1}}{(\ell+1)^2}. \] \end{prop} The number of facets of $\polytope{Z}_{\b{n}}$ will appear later as a special case of Proposition~\ref{prop:numberFacetsShuffleGraphicalZonotopes}. \subsection{Deformed permutahedra}\label{subsec:deformedPermutahedra} We now consider deformations of the permutahedron of Section~\ref{subsec:permutahedra}, introduced by A.~Postnikov~\cite{Postnikov, PostnikovReinerWilliams}. They are usually called ``generalized permutahedra'' but we prefer the term ``deformed permutahedra'' which we find more explicit. \begin{defi}\label{def:generalizedPermutahedron} A \emph{deformed permutahedron} is a polytope whose normal fan coarsens that of the permutahedron $\Perm$. We denote by $\DefoPerms$ the set of deformed permutahedra in $\R^n$. \end{defi} \begin{rema}\label{rem:alternativeDefinitionsDeformedPermutahedra} There are further equivalent definitions of deformed permutahedra, among others: \begin{itemize} \item they are all polytopes obtained by moving parallely the facet defining inequalities of the permutahedron $\Perm$ without passing any vertex~\cite{Postnikov,PostnikovReinerWilliams}, \item their right-hand-sides are described by submodular functions~\cite{Edmonds,Postnikov,PostnikovReinerWilliams}, \item they are all weak Minkowski summands of the permutahedron\linebreak \cite{Meyer,McMullen-typeCone}, \item they are all polytopes obtained by Minkowski sums and differences of faces of the standard simplex~\cite{ArdilaBenedettiDoker}. \end{itemize} \end{rema} \begin{exam} Examples of deformed permutahedra include permutahedra (see Section~\ref{subsec:permutahedra}), associahedra (see Section~\ref{subsec:associahedra}), graphical zonotopes (see Section~\ref{subsec:graphicalZonotopes}), and all polytopes discussed in this paper in particular multiplihedra (see Section~\ref{subsec:multiplihedra}), constrainahedra (see Section~\ref{subsec:constrainahedra}), and biassociahedra (see Section~\ref{subsec:biassociahedra}). \end{exam} By Definition~\ref{def:generalizedPermutahedron}, the normal cones of the faces of a deformed permutahedron are defined by inequalities of the form $x_i \le x_j$. This justifies the following definition. \begin{defi}\label{def:facePreposet} Each face $\polytope{F}$ of a deformed permutahedron $\polytope{P}$ defines a preposet $\preccurlyeq_\polytope{F}$ on $[n]$ such that the normal cone of $\polytope{F}$ is given by ${\{\b{x} \!\in\! \R^n\,|\,x_i \!\le\! x_j \text{ if } i \!\preccurlyeq_\polytope{F}\! j\}}$. This preposet is a poset when $\polytope{F}$ is a vertex of $\polytope{P}$. We call them \emph{face preposets} of $\polytope{P}$ or shortly \emph{$\polytope{P}$-preposets}, and \emph{vertex poset} of $\polytope{P}$ or shortly \emph{$\polytope{P}$-posets}. The face lattice of $\polytope{P}$ is isomorphic to the refinement lattice on the $\polytope{P}$-preposets. \end{defi} \begin{rema}\label{rem:simpleDeformedPermutahedra} In contrast to the permutahedra of Section~\ref{subsec:permutahedra} and the associahedra of Section~\ref{subsec:associahedra}, not all deformed permutahedra are simple polytopes. It is immediate that a deformed permutahedron $\polytope{P}$ is simple if and only if the Hasse diagrams of its vertex posets are all forests. \end{rema} These preposets (resp.~posets) naturally define an equivalence relation on ordered partitions (resp.~on permutations), similar to the sylvester congruence presented in Definition~\ref{def:sylvesterRelation}. \begin{defi}\label{def:equivalenceRelationDeformedPermutahedron} A deformed permutahedron $\polytope{P}$ defines an equivalence relation $\equiv_{\polytope{P}}$ on ordered partitions by $\mu \equiv_{\polytope{P}} \nu$ if and only if the cones $\polytope{C}(\mu)$ and $\polytope{C}(\nu)$ of the braid fan belong precisely to the same cones of the normal fan of $\polytope{P}$. Said differently, each face $\polytope{F}$ of $\polytope{P}$ defines an equivalence class of $\equiv_\polytope{P}$ consisting in all ordered partitions~$\mu$ such that $i \preccurlyeq_\polytope{F} j$ implies $i \preccurlyeq_\mu j$ for all $i,j \in [n]$. This relation~$\equiv_\polytope{P}$ also restrict to an equivalence relation on permutations, with one equivalence class for each vertex of $\polytope{P}$. \end{defi} \begin{rema}\label{rem:equivalenceNotCongruence} In contrast to the sylvester congruence $\equiv_\sylv$ presented in Definition~\ref{def:sylvesterRelation}, the equivalence relation $\equiv_{\polytope{P}}$ is not necessarily a lattice congruence of the weak order. See Section~\ref{subsec:latticeProperties}. \end{rema} We now orient the graphs of arbitrary deformed permutahedra as in Propositions~\ref{prop:weakOrder}, \ref{prop:TamariLattice} and~\ref{prop:acyclicOrientationPoset}. \begin{defi}\label{def:rotationPoset} The \emph{rotation graph} of $\polytope{P} \in \DefoPerms[n]$ is the directed graph on $\polytope{P}$-posets obtained by orienting the graph of $\polytope{P}$ in the direction \[ {\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}. \] The \emph{rotation poset} $\le_\polytope{P}$ is the transitive closure of the rotation graph. \end{defi} \begin{rema}\label{rem:equivalenceNotLattice} In contrast to the Tamari lattice presented in Definition~\ref{def:TamariLattice}, the rotation poset $\le_\polytope{P}$ is not always a lattice. See Section~\ref{subsec:latticeProperties}. \end{rema} %\pagebreak We finally want to underline that the Cartesian products and Minkowski sums of Definition~\ref{def:CartesianProductMinkowskiSum} and Proposition~\ref{prop:CartesianProductMinkowskiSum} preserve deformed permutahedra. \begin{prop}\label{prop:CartesianProductMinkowskiSumDeformedPermutahedra} Let $\polytope{P} \in \DefoPerms[m]$ and $\polytope{Q} \in \DefoPerms[n]$ be two deformed permutahedra. Then \begin{itemize} \item the Cartesian product ${\polytope{P} \times \polytope{Q}}$ is a deformed permutahedron in $\DefoPerms[m+n]$, \item if $m = n$, then the Minkowski sum $\polytope{P} + \polytope{Q}$ is a deformed permutahedra in~$\DefoPerms[m]$. \end{itemize} \end{prop} To describe the resulting face preposets, equivalence relations on ordered partitions (or on permutations), and rotation posets on vertex posets, we need the following standard notations. \break \begin{defi}\label{def:restrictionShift} For a preposet $\preccurlyeq$ on $[n]$ and an integer $m \in [n]$, we define \begin{itemize} \item by $\preccurlyeq_{[m]}$ the \emph{restriction} of $\preccurlyeq$ to $[m]$, \item by $\preccurlyeq^{\pm m}$ the \emph{shift} of $\preccurlyeq$ by $\pm m$, defined by $i \pm m \preccurlyeq^{\pm m} j \pm m \iff i \preccurlyeq j$. \end{itemize} We use similar notations for ordered partitions and permutations. \end{defi} Using the notations of Definition~\ref{def:restrictionShift}, we first describe the behavior of the Cartesian product and Minkowski sum on the face preposets of Definition~\ref{def:facePreposet}. \begin{prop}\label{prop:CartesianProductMinkowskiSumFacePreposets} For any two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and \linebreak $\polytope{Q} \in \DefoPerms[n]$, and any two faces $\polytope{F}$ of $\polytope{P}$ and $\polytope{G}$ of $\polytope{Q}$, \begin{itemize} \item $\preccurlyeq_\polytope{F} \sqcup \; {\preccurlyeq_\polytope{G}}^{+m}$ is a face preposet of $\polytope{P} \times \polytope{Q}$, \item when $m = n$, if $\preccurlyeq_\polytope{F}$ and $\preccurlyeq_\polytope{G}$ have a common extension and any three of the relations ${i \preccurlyeq_\polytope{F} j}$, ${j \preccurlyeq_\polytope{F} i}$, ${i \preccurlyeq_\polytope{G} j}$, ${j \preccurlyeq_\polytope{G} i}$ imply the fourth, then the transitive closure of ${\preccurlyeq_\polytope{F} \cup \preccurlyeq_\polytope{G}}$ is a face preposet~of $\polytope{P} + \polytope{Q}$. \end{itemize} Moreover, any face preposet of $\polytope{P} \times \polytope{Q}$ and $\polytope{P} + \polytope{Q}$ is uniquely obtained this way. \end{prop} We next describe the behavior of the Cartesian product and Minkowski sum on the equivalence relations on ordered partitions of Definition~\ref{def:equivalenceRelationDeformedPermutahedron}. \begin{prop}\label{prop:CartesianProductMinkowskiSumEquivalenceRelations} For any two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and \linebreak $\polytope{Q} \in \DefoPerms[n]$, and any two ordered partitions $\mu \in \f{P}_m$ and $\nu \in \f{P}_n$, \begin{itemize} \item $\mu \equiv_{\polytope{P} \times \polytope{Q}} \nu$ if and only if $\mu_{[m]} \equiv_{\polytope{P}} \nu_{[m]}$ and ${\mu^{-m}}_{[n]} \equiv_{\polytope{Q}} {\nu^{-m}}_{[n]}$, \item if $m = n$, then ${\mu \equiv_{\polytope{P} + \polytope{Q}} \nu}$ if and only if $\mu \equiv_{\polytope{P}} \nu$ and $\mu \equiv_{\polytope{Q}} \nu$. \end{itemize} \end{prop} Finally, we describe the behavior of the Cartesian product and Minkowski sum on the rotation posets of Definition~\ref{def:rotationPoset}. \begin{prop}\label{prop:CartesianProductMinkowskiSumRotationPosets} For any two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and \linebreak $\polytope{Q} \in \DefoPerms[n]$, and any four vertices ${\b{v}, \b{v}' \in \polytope{P}}$ and $\b{w}, \b{w}' \in \polytope{Q}$, we have \begin{itemize} \item ${\preccurlyeq_{\b{v}} \sqcup \; {\preccurlyeq_{\b{w}}}^{+m}} \le_{\polytope{P} \times \polytope{Q}} {\preccurlyeq_{\b{v}'} \sqcup \; {\preccurlyeq_{\b{w}'}}^{+m}}$ if and only if ${\preccurlyeq_{\b{v}}} \le_\polytope{P} {\preccurlyeq_{\b{v}'}}$ and ${\preccurlyeq_{\b{w}}} \le_\polytope{Q} {\preccurlyeq_{\b{w}'}}$, \item if $m = n$ and the transitive closure $\preccurlyeq$ of $\preccurlyeq_{\b{v}} \cup \preccurlyeq_{\b{w}}$ (resp. $\preccurlyeq'$ of $\preccurlyeq_{\b{v}'} \cup \preccurlyeq_{\b{w}'}$) is a vertex poset of $\polytope{P} + \polytope{Q}$, then ${\preccurlyeq} \; \le_{\polytope{P} + \polytope{Q}} \; {\preccurlyeq}'$ if and only if ${\preccurlyeq_{\b{v}}} \le_\polytope{P} {\preccurlyeq_{\b{v}'}}$ and~${\preccurlyeq_{\b{w}}} \le_\polytope{Q} {\preccurlyeq_{\b{w}'}}$. \end{itemize} \end{prop} \subsection{Lattice properties of rotation posets}\label{subsec:latticeProperties} As mentioned in Propositions~\ref{prop:weakOrder}, \ref{prop:TamariLattice} and~\ref{prop:acyclicOrientationPoset}, the graphs of the permutahedron~$\Perm$, of the associahedron $\Asso$, and of the graphical zonotope $\Zono[G]$, oriented in the direction $\b{\omega}$ are the Hasse diagrams of the weak order, of the Tamari lattice, and of the acyclic orientation poset of $G$, respectively. More generally, we have defined in Definition~\ref{def:rotationPoset} the rotation poset $\le_\polytope{P}$ of a deformed permutahedron~$\polytope{P}$ by orienting its graph in the direction $\b{\omega}$. It turns out that the Tamari lattice is a lattice quotient of the weak order. More generally, the graph of any quotientope of~\cite{PilaudSantos-quotientopes} oriented by $\b{\omega}$ is the Hasse diagram of a lattice quotient of the weak order. In contrast, not all acyclic orientation posets are lattices, even less lattice quotients of the weak order. In this section, we discuss lattice properties of the rotation posets of deformed permutahedra. We start by recalling some basic facts about lattice congruences. \begin{defi}\label{def:quotientRelation} Given a binary relation $R$ and an equivalence relation $\equiv$ on the same set $X$, the \emph{quotient relation} $R/{\equiv}$ is the binary relation on $X/{\equiv}$ defined by $I \; R/{\equiv} \; J$ if and only if there is $i \in I$ and $j \in J$ such that $i \; R \; j$. \end{defi} \begin{prop}\label{prop:rotationPoset} For any deformed permutahedron $\polytope{P}$, the rotation poset~$\le_\polytope{P}$ is the poset quotient of the weak order on $\f{S}_n$ by the equivalence relation $\equiv_\polytope{P}$. \end{prop} \begin{defi}\label{def:latticeCongruence} A \emph{congruence} of a lattice $(L, \le, \meet, \join)$ is an equivalence relation on $L$ compatible with the meet and join operations, meaning that ${x \meet y \equiv x' \meet y'}$ and $x \join y \equiv x' \join y'$ for any $x \equiv x'$ and $y \equiv y'$. The quotient $\le/{\equiv}$ is then automatically a lattice on $L/{\equiv}$. \end{defi} \begin{prop}\label{prop:characterizationLatticeCongruence} An equivalence relation $\equiv$ on a lattice $L$ is a lattice congruence if and only if \begin{itemize} \item its equivalent classes are intervals of $L$, \item the map $\projDown$ (resp. $\projUp$) sending an element to the minimum (resp.~maximum) element in its equivalence class is order preserving. \end{itemize} \end{prop} In view of Proposition~\ref{prop:characterizationLatticeCongruence}, we define the following properties of equivalence relations on permutations. Note that the first two properties are independent, and are both implied by (but do not imply) the third one. \begin{defi}\label{def:intervalLatticeProperty} We say that an equivalent relation $\equiv$ on $\f{S}_n$ has \begin{itemize} \item the \emph{ interval property} if its classes are intervals of the weak order, \item the \emph{lattice property} if the quotient of the weak order by $\equiv$ is a lattice on~$\f{S}_n/{\equiv}$, \item the \emph{congruence property} if it is a lattice congruence (see Definition~\ref{def:latticeCongruence} and Proposition~\ref{prop:characterizationLatticeCongruence}). \end{itemize} By extension, we say that a deformed permutahedron $\polytope{P}$ has these properties when the corresponding equivalence relation $\equiv_\polytope{P}$ of Definition~\ref{def:equivalenceRelationDeformedPermutahedron} does. In particular, $\polytope{P}$ has the lattice property when the rotation poset $\le_\polytope{P}$ is a lattice. \end{defi} To illustrate these notions, we characterize in the next statements the graphs whose zonotope has the interval, the lattice, or the congruence property. We will need the following definitions, see~\cite{BarnardMcConville, Pilaud-acyclicReorientationLattices}. \begin{defi}\label{def:filledEdges} An integer graph $G$ is \begin{itemize} \item \emph{filled} if ${(i,k) \in E(G)}$ implies $(i,j) \in E(G)$ and $(j,k) \in E(G)$ for all $i < j < k$, \item \emph{half-filled} if ${(i,k) \in E(G)}$ implies $(i,j) \in E(G)$ or $(j,k) \in E(G)$ for \linebreak all $i < j < k$, \item \emph{vertebrate} if the transitive reduction of any induced subgraph of $G$ is a forest. \end{itemize} \end{defi} \begin{prop}\label{prop:latticePropertiesGraphicalZonotopes} The graphical zonotope $\Zono$ has the interval (resp. lattice, resp.~congruence) property if and only if $G$ is half-filled (resp.~vertebrate, resp.~filled). \end{prop} The characterizations of the lattice and congruence properties in Proposition~\ref{prop:latticePropertiesGraphicalZonotopes} were already proved in~\cite{Pilaud-acyclicReorientationLattices}. We just prove here the characterization of the interval property as it did not appear in the literature. For this, we need the classical characterization of the weak order intervals~\cite{BjornerWachs}. \begin{prop}\label{prop:characterizationWOIP} A poset $\less$ on $[n]$ defines an interval of the weak order if and only if $i \less k$ implies $i \less j$ or $j \less k$, and $i \more k$ implies $i \more j$ or $j \more k$, for every~${1 \le i < j < k \le n}$. \end{prop} \begin{proof}[Proof of Proposition~\ref{prop:latticePropertiesGraphicalZonotopes}] As just explained, we only prove here the characterization of the interval property. Assume first that $G$ is half-filled. Consider a poset~$\preccurlyeq_O$ corresponding to an acyclic orientation $O$ of $G$ and let ${1 \le i < j < k \le n}$ be such that~$i \preccurlyeq_O k$. By definition, there is a sequence $i = j_0, j_1,\,\dots,\,j_p = k$ such that~$(j_{q-1}, j_q)$ is an oriented arc of $O$ for all $q \!\in\! [p]$. Moreover, since $1 \!\le\! i \!<\! j \!<\! k \!\le\! n$, there is $q \in [p]$ such that ${j_{q-1} \!<\! j \!\le\! j_q}$. If $j \!=\! j_q$, then we obtain that $i \!\preccurlyeq_O\! j$ and $j \!\preccurlyeq\! k$. Otherwise, since~$(j_{q-1}, j_q) \!\in\! E(G)$ and $G$ is half-filled, we also have $(j_{q-1}, j) \!\in\! E(G)$ or~$(j, j_q) \!\in\! E(G)$. Assume for instance that $(j, j_q) \in E(G)$ (the other case is symmetric). If the edge~$(j, j_q)$ is oriented from $j$ to $j_q$ in $O$, then we obtain that $j \preccurlyeq_O j_q \preccurlyeq_O k$, so that $j \preccurlyeq_O k$. Otherwise, we have $i \preccurlyeq_O j_q \preccurlyeq j$ so that $i \preccurlyeq j$. Therefore, $i \preccurlyeq_O k$ implies $i \preccurlyeq_O j$ or $j \preccurlyeq_O k$. By symmetry, we conclude from~Proposition~\ref{prop:characterizationWOIP} that~$\Zono$ has the interval property. Conversely, if $G$ is not half-filled, it is immediate to construct an acyclic orientation $O$ of $G$ whose corresponding poset $\preccurlyeq_O$ fails to satisfy the conditions of Proposition~\ref{prop:characterizationWOIP}. \end{proof} \begin{coro}\label{coro:latticePropertiesBipartiteGraphicalZonotope} The graphical zonotope $\polytope{Z}_{m,n} \eqdef \Zono[K_{m,n}]$ has the interval (resp.~lattice, resp.~congruence) property if and only if $m,n \ge 1$ (resp. $m = 1$ or~$n = 1$, resp. $m = n = 1$). \end{coro} \begin{proof} It follows immediately from Definition~\ref{def:filledEdges} that the complete bipartite graph $K_{m,n}$ is always half-filled, vertebrate only when $m = 1$ or $n = 1$, and filled only when $m = n = 1$. \end{proof} We finally want to underline which of the properties of Definition~\ref{def:intervalLatticeProperty} are preserved by the Cartesian product and the Minkowski sum of Definition~\ref{def:CartesianProductMinkowskiSum}. The proofs are immediate for the Cartesian product, and rely on the fact that the congruence $\equiv_{\polytope{P} + \polytope{Q}}$ is the intersection of the congruences $\equiv_\polytope{P}$ and $\equiv_\polytope{Q}$ for the Minkowski sum. \begin{prop}\label{prop:CartesianProductMinkowskiSumLatticeProperties} The Cartesian product preserves the interval, lattice, and congruence properties. The Minkowski sum preserve the interval and congruence properties, but not the lattice property. \end{prop} \section{Shuffles of deformed permutahedra}\label{sec:shuffles} In this section, we introduce the shuffle operation on deformed permutahedra (Section~\ref{subsec:shuffle}), provide a combinatorial description of the resulting polytopes (Section~\ref{subsec:combinatorialDescription}), and discuss the shuffle with a point (Section~\ref{subsec:shufflePoint}) and the shuffle of graphical zonotopes (Section~\ref{subsec:shuffleGraphicalZonotopes}). \subsection{Shuffle operation}\label{subsec:shuffle} This paper focuses on the following operation on the deformed permutahedra of Section~\ref{subsec:deformedPermutahedra}. \begin{defi}\label{def:shuffleDeformedPermutahedra} The \emph{shuffle} of two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and $\polytope{Q} \in \DefoPerms[n]$ is \[ \polytope{P} \shuffleDP \polytope{Q} \eqdef (\polytope{P} \times \polytope{Q}) + \polytope{Z}_{m,n} = (\polytope{P} \times \polytope{Q}) + \sum_{\substack{i\,\in\,[m] \\ j\,\in\,[n]}} \left[\b{e}_i, \b{e}_{m+j}\right], \] where $\times$ denotes the Cartesian product, and $+$ and $\sum$ the Minkowski sum (see Definition~\ref{def:CartesianProductMinkowskiSum}). \end{defi} For instance, we have $\Perm[m] \shuffleDP \Perm[n] = \Perm[m+n]$. We will study in more details certain particular shuffles: the shuffle with a point in Section~\ref{subsec:shufflePoint}, shuffles of graphical zonotopes in Section~\ref{subsec:shuffleGraphicalZonotopes}, and shuffles of permutahedra and associahedra in Sections~\ref{sec:multiplihedra}, \ref{sec:constrainahedra} and~\ref{sec:biassociahedra}. At the moment, we observe that the shuffle operation $\shuffleDP$ preserves the family of deformed permutahedra, which directly follows from Definition~\ref{def:shuffleDeformedPermutahedra} and Proposition~\ref{prop:CartesianProductMinkowskiSumDeformedPermutahedra}. \begin{prop}\label{prop:shuffleDeformedPermutahedra} For all deformed permutahedra $\polytope{P} \!\in\! \DefoPerms[m]$ and ${\polytope{Q} \!\in\! \DefoPerms[n]}$, the shuffle $\polytope{P} \shuffleDP \polytope{Q}$ is a deformed permutahedron in $\DefoPerms[m+n]$. \end{prop} We now gather in Remarks~\ref{rem:shuffleAssociative}, \ref{rem:simpleShuffle} and~\ref{rem:latticeShuffle} some elementary observations on the shuffle operation $\shuffleDP$. \begin{rema}\label{rem:shuffleAssociative} The shuffle is an associative operation on deformed permutahedra. Indeed, for any $k$ deformed permutahedra $\polytope{P}_1 \in \DefoPerms[n_1],\, \dots,\, \polytope{P}_k \in \DefoPerms[n_k]$, we have \[ \polytope{P}_1 \shuffleDP \cdots \shuffleDP \polytope{P}_k = (\polytope{P}_1 \times \cdots \times \polytope{P}_k) + \polytope{Z}_{(n_1,\,\dots,\,n_k)}. \] The shuffle is also commutative up to permutation of coordinates. Indeed, for any deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and $\polytope{Q} \in \DefoPerms[n]$, we have $\polytope{P} \shuffleDP \polytope{Q} = s(\polytope{Q} \shuffleDP \polytope{P})$ where $s : \R^{n+m} \to \R^{m+n}$ denotes the swap $s(x,y) = (y, x)$. \end{rema} \begin{rema}\label{rem:simpleShuffle} The shuffle operation $\shuffleDP$ does not preserve simple polytopes. For instance, while the permutahedron $\Perm$ of Section~\ref{subsec:permutahedra} and the associahedron~$\Asso$ of Section~\ref{subsec:associahedra} are simple, the multiplihedron $\Multiplihedron \!\eqdef\! \Perm[m] \shuffleDP \Asso[n]$ of Section~\ref{sec:multiplihedra}, the constrainahedron ${\Constrainahedron \eqdef \Asso[m] \shuffleDP \Asso[n]}$ of Section~\ref{sec:constrainahedra}, and the biassociahedron $\Biassociahedron \eqdef \Asso[m] \shuffleDP \Asso[n]$ of Section~\ref{sec:biassociahedra} are not simple in general (see Remarks~\ref{rem:simpleMultiplihedron}, \ref{rem:simpleConstrainahedron} and~\ref{rem:simpleBiassociahedron}). \end{rema} \subsection{Combinatorial description}\label{subsec:combinatorialDescription} We now aim at describing the behavior of the shuffle operation $\shuffleDP$ of Definition~\ref{def:shuffleDeformedPermutahedra} in terms of the face preposets of Definition~\ref{def:facePreposet}. Such a description immediately follows from Propositions~\ref{prop:CartesianProductMinkowskiSumFacePreposets} and~\ref{prop:facesGraphicalZonotope}. A more convenient description arises by combining as well with the description of the face preposets of $\polytope{Z}_{m,n}$ provided in Proposition~\ref{prop:completeMultipartiteGraphicalZonotopeFaces}. Recall that for an ordered partition $\mu$ on $[m+n]$, we denote by~$\preccurlyeq_\mu^{m,n}$ the preposet obtained from $\preccurlyeq_\mu$ by deleting all relations inside each part of $\mu$ completely contained in $[m]$ or in $[n]^{+m}$. \begin{prop}\label{prop:shuffleFacePreposets} Consider two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ \linebreak and $\polytope{Q} \in \DefoPerms[n]$, two faces $\polytope{F}$ of $\polytope{P}$ and $\polytope{G}$ of $\polytope{Q}$, and an ordered partition $\mu$ of~$[m+n]$ such that \begin{itemize} \item $\preccurlyeq_\mu$ extends both $\preccurlyeq_\polytope{F}$ and ${\preccurlyeq_\polytope{G}}^{+m}$, \item no two consecutive parts of $\mu$ are both contained in $[m]$ or both contained in~$[n]^{+m}$, \item if $\mu_k \cap [m] \ne \varnothing \ne \mu_k \cap [n]^{+m}$, then any two elements of $\mu_k \cap [m]$ are equal or incomparable in $\preccurlyeq_\polytope{F}$ and any two elements of $\mu_k \cap [n]^{+m}$ are equal or incomparable~in ${\preccurlyeq_\polytope{G}}^{+m}$. \end{itemize} Then the preposet $\preccurlyeq_{\polytope{F}, \polytope{G}, \mu} \eqdef (\preccurlyeq_\polytope{F} \sqcup \; {\preccurlyeq_\polytope{G}}^{+m}) \; \cup \preccurlyeq_\mu^{m,n}$ is a face preposet of $\polytope{P} \shuffleDP \polytope{Q}$, and any face preposet of $\polytope{P} \shuffleDP \polytope{Q}$ is uniquely obtained this way. \end{prop} \begin{proof} Combine Propositions~\ref{prop:CartesianProductMinkowskiSumFacePreposets} and~\ref{prop:completeMultipartiteGraphicalZonotopeFaces}. \end{proof} \begin{rema}\label{rem:shuffleFaces} The deformed permutahedron $\polytope{P}$ (resp. $\polytope{Q}$) itself appear as a face of $\polytope{P} \shuffleDP \polytope{Q}$. The corresponding face preposets are given by $\preccurlyeq_{\polytope{P}, \b{w}, \mu}$ (resp. $\preccurlyeq_{\b{v}, \polytope{Q}, \mu}$) where~$\b{w}$ (resp. $\b{v}$) is an arbitrary vertex of $\polytope{Q}$ (resp.~of $\polytope{P}$) and $\mu$ is one of the two ordered partitions with parts $[m]$ and $[n]^{+m}$. \end{rema} \begin{rema}\label{rem:biPreposets} The face preposet $\preccurlyeq_{\polytope{F}, \polytope{G}, \mu}$ of Proposition~\ref{prop:shuffleFacePreposets} can be represented visually by drawing the Hasse diagrams of the face preposets $\preccurlyeq_\polytope{F}$ and ${\preccurlyeq_\polytope{G}}^{+m}$ side by side, with their vertices separated in blocks organized from bottom to top according to $\mu$. Then $i \preccurlyeq_{\polytope{F}, \polytope{G}, \mu} j$ if \begin{itemize} \item either there is an oriented path from $i$ to $j$ in $\preccurlyeq_\polytope{F}$ or in ${\preccurlyeq_\polytope{G}}^{+m}$, \item or $i$ is in a block lower than $j$, \item or $i$ and $j$ belong to the same block which is not contained in $[m]$ or in $[n]^{+m}$. \end{itemize} We call such pictures \emph{$(\polytope{P}, \polytope{Q})$-bipreposets}. Examples of bipreposets where the preposets are trees are illustrated in Figures~\ref{fig:cotrees} and~\ref{fig:bitrees}. \end{rema} \begin{rema}\label{rem:biPosets} The preposet $\preccurlyeq_{\polytope{F}, \polytope{G}, \mu}$ is a poset if and only if $\polytope{F}$ and $\polytope{G}$ are vertices, and the parts of $\mu$ are alternatively contained in $[m]$ and $[n]^{+m}$. In other words, the vertex posets of $\polytope{P} \shuffleDP \polytope{Q}$ are obtained by interspersing the vertex posets of $\polytope{P}$ with the vertex posets of $\polytope{Q}$ as explained in Remark~\ref{rem:biPreposets}. We call such pictures \emph{$(\polytope{P}, \polytope{Q})$-biposets}. \end{rema} Remark~\ref{rem:biPosets} yields the following statement. \begin{defi}\label{def:partitionedPoset} A \emph{partitioned poset} is a pair $(\trianglelefteq, \mu)$ where $\trianglelefteq$ is a poset on~$[n]$ and $\mu$ is an ordered partition of $[n]$ such that $i \trianglelefteq j$ implies $i \preccurlyeq_\mu j$. \end{defi} \begin{coro}\label{coro:numberVertices} The number of vertices of $\polytope{P} \shuffleDP \polytope{Q}$ is given by the summation formula \[ \sum_\ell \pp{\ell}{\polytope{P}} \, \big(\pp{\ell-1}{\polytope{Q}} + 2 \, \pp{\ell}{\polytope{Q}} + \pp{\ell+1}{\polytope{Q}} \big), \] where $\pp{\ell}{\polytope{P}}$ denotes the number of partitioned posets $(\trianglelefteq, \mu)$ where $\trianglelefteq$ is a vertex poset of $\polytope{P}$ and $\mu$ has $\ell$ parts. In particular, it only depends on the repartition of partitioned vertex posets of $\polytope{P}$ and $\polytope{Q}$. \end{coro} \begin{rema}\label{rem:noSymmetry} Corollary~\ref{coro:numberVertices} impliesx $\Constrainahedron \eqdef \Asso[m] \shuffleDP \Asso[n]$ of Section~\ref{sec:constrainahedra} and the biassociahedron ${\Biassociahedron \eqdef\Ossa[m]\!\! \shuffleDP\! \!\Asso[n]}$ of Section~\ref{sec:biassociahedra}~have~the same~number~of~vertices~for~any~$\!m,\!n\!\ge\!1$. This symmetry property is lost beyond vertices: for instance, $\Constrainahedron[3,3]$ has $1550$ edges, while $\Biassociahedron[3,3]$ has $1549$ edges. Corollary~\ref{coro:numberVertices} also implies that ${\Perm[m] \shuffleDP \Para[n]}$ and ${\Perm[m+1] \shuffleDP \Point[n-1]}$ have the same number of vertices while their number of facets differ for $n \ge 4$, see Remark~\ref{rem:numberVerticesGraphicalZonotopes}. \end{rema} We now describe the behavior of the shuffle operation $\shuffleDP$ of Definition~\ref{def:shuffleDeformedPermutahedra} at the level of the equivalence relations on ordered partitions and permutations of~Definition~\ref{def:equivalenceRelationDeformedPermutahedron}. It immediately follows from Definition~\ref{def:graphicalRelation} and Proposition~\ref{prop:CartesianProductMinkowskiSumEquivalenceRelations}. \begin{prop}\label{prop:shuffleEquivalenceRelations} For any two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and $\polytope{Q} \in \DefoPerms[n]$, the equivalence relation $\equiv_{\polytope{P} \shuffleDP \polytope{Q}}$ on ordered partitions is given by $\mu \equiv_{\polytope{P} \shuffleDP \polytope{Q}} \nu$ if and only if $\mu_{[m]} \equiv_{\polytope{P}} \nu_{[m]}$ while ${\mu^{-m}}_{[n]} \equiv_{\polytope{Q}} {\nu^{-m}}_{[n]}$ and $i \preccurlyeq_\mu m+j \iff i \preccurlyeq_\nu m+j$ for all $i \in [m]$ and $j \in [n]$. \end{prop} Finally, we describe the behavior of the shuffle operation $\shuffleDP$ of Definition~\ref{def:shuffleDeformedPermutahedra} on rotation posets of Definition~\ref{def:rotationPoset}. It immediately follows from Propositions~\ref{prop:completeMultipartiteGraphicalZonotopeRotationPosets} and~\ref{prop:CartesianProductMinkowskiSumRotationPosets}. \begin{prop}\label{prop:shuffleRotationPosets} For any two deformed permutahedra $\polytope{P} \in \DefoPerms[m]$ and ${\polytope{Q} \in \DefoPerms[n]}$, the rotation poset $\le_{\polytope{P} \shuffleDP \polytope{Q}}$ on the vertex posets of $\polytope{P} \shuffleDP \polytope{Q}$ is given by~${\preccurlyeq_{\b{v}, \b{w}, \mu}} \linebreak\le_{\polytope{P} \shuffleDP \polytope{Q}} {\preccurlyeq_{\b{v}', \b{w}', \mu'}}$ if and only if ${\preccurlyeq_{\b{v}}} \le_{\polytope{P}} {\preccurlyeq_{\b{v}'}}$ and ${\preccurlyeq_{\b{w}}} \le_{\polytope{Q}} {\preccurlyeq_{\b{w}'}}$ and $p \preccurlyeq_\mu q$ implies~$p \preccurlyeq_{\mu'} q$ for all $p \in [m]$ and $q \in [n]^{+m}$. \end{prop} \begin{rema}\label{rem:latticeShuffle} It follows from Corollary~\ref{coro:latticePropertiesBipartiteGraphicalZonotope} and Proposition~\ref{prop:CartesianProductMinkowskiSumLatticeProperties} that the shuffle operation $\shuffleDP$ preserves the interval property. In contrast, Remarks~\ref{rem:noCoTamari} and~\ref{rem:noBiTamari} show that neither the \mbox{$(3,3)$-constrainahe}\-dron ${\Constrainahedron[3][3] \eqdef \Asso[3] \shuffleDP \Asso[3]}$ nor the $(3,3)$-biassociahedron ${\Biassociahedron[3][3] \eqdef \Ossa[3] \shuffleDP \Asso[3]}$ have the lattice and congruence properties, while $\Ossa[3]$ and $\Asso[3]$ both do. However, we will see in Corollary~\ref{coro:latticeShufflePermutahedron} that the shuffle with a permutahedron $\Perm$ preserves the lattice property (but not the congruence property). \end{rema} \subsection{Shuffle with a point}\label{subsec:shufflePoint} We mark a little pause to specialize the observations of Section~\ref{subsec:combinatorialDescription} to the case where $\polytope{Q}$ is reduced to a point $\b{0}$. The bipreposets (and biposets) where the second poset is a singleton can then be encoded as painted preposets (and posets) defined below. We first define antichains, upper sets and lower sets in preposets, generalizing the classical notions for posets. \begin{defi}\label{def:antichainsLowerUpperSetsPreposets} Consider a preposet $\preccurlyeq$ on $[n]$. An \emph{antichain} of $\preccurlyeq$ is a subset~$A$ of $[n]$ such that $i \in A \iff j \preccurlyeq i$ for any $i \preccurlyeq j$ with $j \in A$. An \emph{upper} (resp.~ \emph{lower}) \emph{set} of $\preccurlyeq$ is a subset $U$ (resp. $L$) of $[n]$ such that $i \in U$ implies $j \in U$ (resp. $j \in L$ implies $i \in L$) for any $i \preccurlyeq j$. In other words, an antichain (resp.~an upper set, resp.~a lower set) of a preposet $\preccurlyeq$ is the union of the classes of an antichain (resp.~an upper set, resp.~a lower set) in the quotient poset $\preccurlyeq/{\equiv}$ on the classes of the equivalence relation $\equiv$ defined by $i \equiv j \iff i \preccurlyeq j$ and $j \preccurlyeq i$. \end{defi} \begin{defi}\label{def:paintedPreposet} A \emph{painted preposet} is a preposet $\preccurlyeq$ on $[n]$ together with a partition $[n] = L \sqcup A \sqcup U$ where $L$ is a lower set, $A$ is an antichain, and $U$ is an upper set (all possibly empty) of $\preccurlyeq$. \end{defi} \begin{prop}\label{prop:paintedPreposets} For any deformed permutahedron $\polytope{P} \in \DefoPerms[n]$, the faces of the shuffle $\polytope{P} \shuffleDP \b{0}$ are in bijection with the painted $\polytope{P}$-preposets. \end{prop} \begin{proof} Each face preposet $\preccurlyeq_{\polytope{F}, \b{0}, \mu}$ of Proposition~\ref{prop:shuffleFacePreposets} corresponds to a painted poset $(\preccurlyeq_\polytope{F}, L \sqcup A \sqcup U)$ where $L$ (resp. $A$, resp. $U$) is the subset of elements of~$[n]$ that appear in a part of $\mu$ before (resp.~equal to, resp.~after) the part of $\mu$ containing~${n\!+\!1}$. \end{proof} \begin{defi}\label{def:paintedPoset} A \emph{painted poset} is a poset $\preccurlyeq$ together with a partition \linebreak $[n] = L \sqcup U$ where $L$ is a lower set and $U$ is an upper set (both possibly empty) of $\preccurlyeq$. Two painted posets $(\preccurlyeq, L \sqcup U)$ and $(\preccurlyeq', L' \sqcup U')$ are connected by a \emph{right rotation} if \begin{itemize} \item either $\preccurlyeq$ and $\preccurlyeq$ are related by a right flip, while $L = L'$ and $U = U'$, \item or ${\preccurlyeq} = {\preccurlyeq}$ and $L = L' \cup \{i\}$ and $U = U' \ssm \{i\}$ for some $i \in [n]$. \end{itemize} \end{defi} \begin{prop}\label{prop:paintedPoset} The rotation graph of the shuffle $\polytope{P} \shuffleDP \b{0}$ is isomorphic to the rotation graph on painted $\polytope{P}$-posets. For any two painted $\polytope{P}$-posets $\poset \eqdef (\preccurlyeq, L \sqcup U)$ and $\poset' \eqdef (\preccurlyeq', L' \sqcup U')$, there is a path from $\poset$ to $\poset'$ in this graph if and only if~${\preccurlyeq} \le_\polytope{P} {\preccurlyeq'}$ and $L \subseteq L'$. \end{prop} \begin{proof} This is a specialization of Proposition~\ref{prop:shuffleRotationPosets} to $\polytope{P} \shuffleDP \b{0}$. \end{proof} This description of the rotation graph enables us to show the following statement. \begin{prop}\label{prop:latticeShufflePoint} A deformed permutahedron $\polytope{P}$ has the lattice property if and only if the shuffle ${\polytope{P} \shuffleDP \b{0}}$ has the lattice property. \end{prop} \begin{proof} Observe first that the rotation poset $\le_\polytope{P}$ is isomorphic to the interval of the rotation poset $\le_{\polytope{P} \shuffleDP \b{0}}$ given by the painted $\polytope{P}$-posets $(\preccurlyeq, L \sqcup U)$ where $L = \varnothing$. This proves that $\le_{\polytope{P} \shuffleDP \b{0}}$ is a lattice implies that $\le_\polytope{P}$ is a lattice, since any interval of a lattice is a lattice. Conversely, assume that $\le_\polytope{P}$ is a lattice. Consider $k$ painted $\polytope{P}$-posets $\poset_1 \eqdef (\preccurlyeq_1,\linebreak L_1 \sqcup U_1), \dots, \poset_k \eqdef (\preccurlyeq_k, L_k \sqcup U_k).$ Then it is immediate from Proposition~\ref{prop:paintedPoset} that the join of $\poset_1,\,\dots, \,\poset_k$ in $\le_{\polytope{P} \shuffleDP \b{0}}$ is the painted $\polytope{P}$-poset $\poset_\join \eqdef (\preccurlyeq_\join, L_\join \sqcup U_\join)$, where $\preccurlyeq_\join$ is the join of the $\polytope{P}$-posets $\preccurlyeq_1, \dots, \preccurlyeq_k$ in $\le_\polytope{P}$, and $L_\join$ is the lower set of $\preccurlyeq_\join$ generated by the union $L_1 \cup \dots \cup L_k$. A symmetric expression obviously holds for the meet using $U$ instead of $L$. \end{proof} \begin{coro}\label{coro:latticeShufflePermutahedron} If a deformed permutahedron $\polytope{P}$ has the lattice property, then the shuffle $\polytope{P} \shuffleDP \Perm$ has the lattice property for any integer $n \ge 1$. \end{coro} \subsection{Shuffle of graphical zonotopes}\label{subsec:shuffleGraphicalZonotopes} As it turns out, the family of graphical zonotopes is stable by the shuffle operation~$\shuffleDP$ on deformed permutahedra. The corresponding operation on graphs is well-known in graph theory. \begin{defi}\label{def:joinGraphs} The \emph{join} of two graphs $G$ and $H$ with disjoint vertex sets is the graph $G \joinGraph H$ obtained by taking the disjoint union of $G$ and $H$ and connecting all vertices of $G$ to all vertices of $H$. In other words, $V(G \joinGraph H) = V(G) \sqcup V(H)$ and $E(G \joinGraph H) = E(G) \sqcup E(H) \sqcup \big(V(G) \times V(H) \big)$. If $V(G) = [m]$ and $V(H) = [n]$, we write $G \joinGraph H$ for the graph $G \joinGraph H^{+m} = (G \otimes H) \oplus K_{m,n}$. \end{defi} \begin{exam}\label{exm:joinGraphs} The following families provide some relevant examples: \begin{itemize} \item the join of two empty graphs $E_m$ and $E_n$ is the complete bipartite graph $K_{m,n}$ (more generally, the join of $k$ empty graphs $E_{n_1},\,\dots,\, E_{n_k}$ is the complete $k$-partite graph $K_{n_1,\, \dots,\,n_k}$), \item the join of a path $P_m$ by an empty graph $E_n$ is a fan graph $F_{m,n}$, \item the join of two complete graphs $K_m$ and $K_n$ is the complete graph $K_{m+n}$. \end{itemize} \end{exam} The next statement immediately follows from Definitions\ref{def:shuffleDeformedPermutahedra} and~\ref{def:joinGraphs} and Proposition~\ref{prop:operationsGraphsZonotopes}. \begin{prop}\label{prop:shuffleGraphicalZonotopes} For all integer graphs $G$ and $H$, we have \[ \Zono[G] \shuffleDP \Zono[H] = \Zono[G \joinGraph H]. \] \end{prop} \begin{exam}\label{exm:shufflePermutahedra} For instance, the permutahedra are stable by $\shuffleDP$ since \begin{align*} \Perm[m] \shuffleDP \Perm[n] & = \Zono[K_m] \shuffleDP \Zono[K_n] = \Zono[K_m \joinGraph K_n] \\ & = \Zono[K_{m+n}] = \Perm[m+n]. \end{align*} \end{exam} In view of Proposition~\ref{prop:shuffleGraphicalZonotopes}, it was tempting to call $\polytope{P} \shuffleDP \polytope{Q}$ the join of the deformed permutahedra $\polytope{P}$ and $\polytope{Q}$. Recall however that there is a classical join operation on polytopes with the property that the graph of a join of polytopes is the join of the graphs of the polytopes (see~\cite[Ex.~9.9, p.~323]{Ziegler-polytopes}). The number of vertices and facets of the graphical zonotopes arising from shuffles of graphical zonotopes are interesting. See Tables~\ref{table:verticesPermCube}, \ref{table:facetsPermCube}, \ref{table:verticesPermPoint}, \ref{table:facetsPermPoint}, \ref{table:verticesPointPoint} and~\ref{table:facetsPointPoint} in Section~\ref{subsec:tablesZonotopes} for tables of particularly relevant families. We just mention here some relevant facts. \begin{prop}\label{prop:numberVerticesShuffleGraphicalZonotopes} For all graphs $G$ and $H$, the number of vertices of \linebreak $\Zono[G] \shuffleDP \Zono[H]$ is the number of acyclic orientations of the join $G \joinGraph H$. In particular, \begin{itemize} \item $f_0 (\Perm[m] \shuffleDP \Para[n] ) = (m+1)! \, (m+2)^{n-1}$, \item $f_0 (\Perm[m] \shuffleDP \Point[n] ) = m! \, (m+1)^n $, \item $f_0 (\Point[m] \shuffleDP \Point[n] ) = B(-m,n) \eqdef \sum_{\ell\,\ge\,0} \frac{\surjections{m+1}{\ell+1} \, \surjections{n+1}{\ell+1}}{(\ell+1)^2}$, where \linebreak$\surjections{n}{k}$ denotes the number of surjections from $[n]$ to $[k]$ (see~\OEIS{A019538} in \cite{OEIS}), \item $f_0 (\Point[n_1] \shuffleDP \cdots \shuffleDP \Point[n_k] ) = \sum_{w\,\in\,W_k} \prod_{i\,\in\,[k]} \surjections{n_i}{|w|_i}$, where $W_k$ is the set of words on the alphabet $[k]$ containing at least one copy of each letter and no consecutive identical letters, $|w|_i$ denotes the number of letters $i$ in the word $w$, and $\surjections{n}{k}$ denotes the number of surjections from $[n]$ to $[k]$ (see~\cite[\OEIS{A019538}]{OEIS}). \end{itemize} \end{prop} \begin{proof} The first sentence of the statement is a direct consequence of Propo\-sitions~\ref{prop:shuffleGraphicalZonotopes} and~\ref{prop:facesGraphicalZonotope}. The numbers of vertices of $\Perm[m] \shuffleDP \Para[n]$ and \linebreak $\Perm[m] \shuffleDP \Point[n]$ are easily computed by induction. Finally, the numbers of vertices of $\Point[m] \shuffleDP \Point[n]$ and $\Point[n_1] \shuffleDP \cdots \shuffleDP \Point[n_k]$ follow from Proposition~\ref{prop:completeMultipartiteGraphicalZonotopeNumberVertices}. \end{proof} \break \begin{prop}\label{prop:numberFacetsShuffleGraphicalZonotopes} For all graphs $G_1,\, \dots,\, G_k$ on $[n_1],\, \dots,\, [n_k]$ respectively, such that $k > 2$ or at least one of $G_1$ and $G_2$ is connected, the number of facets of $\Zono[G_1] \shuffleDP \cdots \shuffleDP \Zono[G_k]$ is given~by \[ f_{n_1 + \dots + n_k - 2} \big(\Zono[G_1] \shuffleDP \cdots \shuffleDP \Zono[G_k] \big) = 2^{\sum\limits_{i \,\in\,[k]} n_i} - 2 \sum_{i\,\in\,[k]} \nc{G_i} - 2, \] where $\nc{G}$ denotes the number of disconnected subsets of $G$. For two disconnected graphs $G_1$ and $G_2$ on $[n_1]$ and $[n_2]$ respectively, the number of facets of \linebreak $\Zono[G_1] \shuffleDP \Zono[G_2]$ is \[ {f_{n_1+n_2-2} \big(\Zono[G_1] \shuffleDP \Zono[G_2] \big) = 2^{n_1 + n_2} - 2 \, \nc{G_1} - 2 \, \nc{G_2}}. \] In particular, \begin{itemize} \item $f_{m+n-2} (\Perm[m] \shuffleDP \Para[n] ) = 2^{m+n} - 2^{n+1} + n(n+1)$, \item $f_{m+n-2} (\Perm[m] \shuffleDP \Point[n] ) = 2^{m+n} - 2^{n+1} + 2n$, \item $f_{m+n-2} (\Point[m] \shuffleDP \Point[n]) = 2^{m+n} - 2^{m+1} - 2^{n+1} + 2m + 2n + 4$, \item $f_{m+n-2} (\Point[n_1] \shuffleDP \cdots \shuffleDP \Point[n_k]) = 2^{\sum_{i\,\in\,[k]} n_i} - 2 \sum_{i\,\in\,[k]} (2^{n_i} - n_i -2) - 2$ for $k > 2$. \end{itemize} \end{prop} \begin{proof} By Propositions~\ref{prop:shuffleGraphicalZonotopes} and~\ref{prop:facesGraphicalZonotope}, the number of facets of $\Zono[G_1] \shuffleDP \cdots \shuffleDP\linebreak \Zono[G_k]$ is the number of biconnected subsets of $G \eqdef G_1 \joinGraph \cdots \joinGraph G_k$. Consider a subset $U$ of the vertex set of $G$. If $U$ meets the vertex sets of $\ell > 1$ of the graphs $G_i$, then the subgraph of $G$ induced by $U$ contains a complete $\ell$-partite graph and is thus connected. Therefore, the subsets of vertices of $G$ that are not biconnected are precisely the disconnected subsets of the graphs $G_i$ and their complements. When $k > 2$ or at least one of $G_1$ and $G_2$ is connected, there is no ambiguity between these sets. It follows that the number of biconnected subsets of $G$ is ${2^{\sum_{i\,\in\,[k]} n_i} - 2 - 2\sum_{i\,\in \,[k]} \nc{G_i}}$. If $k = 2$ and both $G_1$ and $G_2$ are disconnected, we are counting $G_1$ (resp. $G_2$) both as a disconnected subset of $G_1$ (resp. $G_2$) and as the complement of $G_2$ (resp. $G_1$), which yield the correction ${2^{n_1 + n_2} - 2 \, \nc{G_1} - 2 \, \nc{G_2}}$. The specific formulas then follow from the immediate observation that $\nc{K_n} = 0$ for the complete graph $K_n$, $\nc{P_n} = 2^n - \binom{n+1}{2} - 1$ for the path graph $P_n$, and $\nc{E_n} = 2^n - n - 1$ for the empty graph $E_n$. \end{proof} \begin{rema}\label{rem:numberVerticesGraphicalZonotopes} Note that $\Perm[m] \shuffleDP \Para[n]$ and $\Perm[m+1] \shuffleDP \Point[n-1]$ have the same number of vertices by Proposition~\ref{prop:numberVerticesShuffleGraphicalZonotopes}, but not the same number of facets when $n \ge 4$ by Proposition~\ref{prop:numberFacetsShuffleGraphicalZonotopes}. The equality for the number of vertices can be seen from Corollary~\ref{coro:numberVertices}. \end{rema} \begin{rema} Note that the results of this section extend to all hypergraphic polytopes. A \emph{hypergraphic polytope} is the Minkowski sum of the faces of the standard simplex corresponding to the hyperedges of an arbitrary hypergraph. See for instance~\cite{AguiarArdila, BenedettiBergeronMachacek}. Hypergraphic polytopes contain in particular graphical zonotopes (when the hypergraph is a graph) and nestohedra (when the hypergraph is a building set~\cite{FeichtnerSturmfels,Postnikov}). It immediately follows from Definition~\ref{def:shuffleDeformedPermutahedra} that the shuffle of two hypergraphic polytopes is a hypergraphic polytope (and the hypergraph of the shuffle is the join of the hypergraphs of the factors in the sense of Definition~\ref{def:joinGraphs}). \end{rema} \section{Multiplihedra}\label{sec:multiplihedra} In this section, we study the family of $(m,n)$-multiplihedra, obtained as the shuffle of an $m$-permutahedron $\Perm[m]$ with an $n$-associahedron $\Asso[n]$. It extends the classical multiplihedron studied in~\cite{ArdilaDoker,Forcey-multiplihedra, ForceyLauveSottile, MauWoodward,Stasheff-HSpaces, SaneblidzeUmble-diagonals}, which corresponds to the case $m = 1$. We generalize the classical model of painted trees to $(m,n)$-multiplihedron (Section~\ref{subsec:paintedTrees}), describe the face lattice, fan and oriented skeleton of the $(m,n)$-multiplihedron in terms of these trees (Section~\ref{subsec:multiplihedra}), provide explicit vertex, facet and Minkowski sum descriptions of the $(m,n)$-multiplihedron (Section~\ref{subsec:vertexFacetMinkowskiDescriptionsMultiplihedra}), and present enumerative results on the number of vertices, faces and facets of the $(m,n)$-multiplihedron (Section~\ref{subsec:numerologyMultiplihedra}). One relevant byproduct of this section is a lattice structure on binary $m$-painted $n$-trees, containing simultaneously the weak order on permutations of $\f{S}_m$ and the Tamari lattice on binary trees of $\f{B}_n$. We are not aware that this lattice structure was noticed in the literature, even for the classical painted trees (with $m = 1$). \subsection{Painted trees}\label{subsec:paintedTrees} We start by defining $m$-painted $n$-trees, see Figure~\ref{fig:paintedTrees}. Intuitively, an \mbox{$m$-painted} $n$-tree is just a Schr\"oder $n$-tree with some disjoint cuts that can pass through vertices or through edges and are labeled by a partition of $[m]$. To make our definitions precise, it is convenient to introduce unary nodes when a cut passes through an edge. Recall from Definitions~\ref{def:tree}, \ref{def:inorder} and~\ref{def:treeDeletion} our conventions for rooted plane trees, inorder labelings, and node deletions. \begin{defi}\label{def:stumpCut} For a tree $T$, we call \begin{itemize} \item \emph{cut} of $T$ a subset $C$ of nodes of $T$ containing precisely one node along the path from the root to any leaf of $T$, \item \emph{stump} of $T$ a subset $S$ of nodes of $T$ containing the root of $T$ and such that the parent of a node in $S$ also belongs to $S$, and conversely either none or all children of a node in $S$ also belong to $S$. \end{itemize} Clearly, to a cut $C$ of $T$ corresponds the stump $\stump{C}$ of all nodes located along a path from the root of $T$ to a node of $C$. Conversely, to a stump $S$ of $T$ corresponds the cut $\cut{S}$ of nodes of $S$ with no child in $S$. \end{defi} \begin{defi}\label{def:paintedTree} A \emph{$m$-painted $n$-tree} $\PT \eqdef (T, C, \mu)$ consists of an $n$-tree $T$, a sequence $C \eqdef (C_1,\, \cdots,\,C_k)$ of $k \le m$ cuts of $T$, and an ordered partition $\mu$ of $[m]$ into $k$ parts, such~that \begin{itemize} \item $C_{i+1} \subseteq \stump{C_i} \ssm C_i$ for all $i \in [k-1]$, and \item any unary node of $T$ belongs to one of the cuts $C_1,\,\dots,\, C_k$. \end{itemize} We denote by $\f{PT}_{m,n}$ the set of $m$-painted $n$-trees. \end{defi} In other words, an $m$-painted $n$-tree is an $n$-tree with at most $m$ cuts, where each cut is disjoint and below the previous one, the union of the cuts covers all unary nodes, and the cuts are labeled by an ordered partition of $[m]$. In the sequel, we write~$|C|$ for $k$ and $|\bigcup C|$ for $|\bigcup_{i\,\in\,[k]} C_i|$. To represent an $m$-painted $n$-tree $\PT \eqdef (T, C, \mu)$, we draw the tree $T$ in such a way that all nodes in the cut $C_i$ belong to the same (red) horizontal line labeled by $\mu_i$ (which is abbreviated as a word rather than a set). Examples are illustrated in Figure~\ref{fig:paintedTrees}. Note that when $k = 1$, the $1$-painted $n$-trees are precisely the painted posets of Definitions~\ref{def:paintedPreposet} and~\ref{def:paintedPoset} for the associahedron~$\Asso$, since it is equivalent to remember the cut and to remember which vertices are below, on, or above the cut. \begin{figure} \centerline{ \includegraphics[scale=.9]{paintedTree1} \hspace{.5cm} \includegraphics[scale=.9]{paintedTree2} \hspace{.5cm} \includegraphics[scale=.9]{paintedTree3} \hspace{.5cm} \includegraphics[scale=.9]{paintedTree4} } \caption{Some $2$-painted trees.}\label{fig:paintedTrees} \end{figure} We now define the painted tree deletion poset. Definition~\ref{def:paintedTreeDeletion} provides a direct description in terms of painted trees, while Definition~\ref{def:paintedTreePreposet} provides an alternative simpler but indirect description in terms of preposets. To illustrate the following definition, Figure~\ref{fig:paintedTreeDeletions} represents a sequence of deletions in $2$-painted $5$-trees. \begin{defi}\label{def:paintedTreeDeletion} Let $\PT \eqdef (T, C, \mu)$ and $\PT' \eqdef (T', C', \mu')$ be two $m$-painted $n$-trees. We say that $\PT'$ is obtained by a \emph{deletion} in $\PT$ in either of the following three cases: \begin{enumerate}\romanenumi \item\label{defi3.3.1} \textbf{Free child:} A node $\node{n}$ of $T$ distinct from the root is in none of the cuts of $C$, and $T'$ is obtained by deleting $\node{n}$ in $T$, while $C' = C$ and $\mu' = \mu$. \item\label{defi3.3.2} \textbf{Free parent:} A node $\node{p}$ is in none of the cuts of $C$ while all its children $\children(\node{p})$ belong to the same cut $C_i$, and $T'$ is obtained by deleting all $\children(\node{p})$ in $T$, $C'$ is obtained from $C$ by replacing $C_i$ by $C'_i \eqdef (C_i \ssm \children(\node{p}) ) \cup \{\node{p}\}$, and $\mu' = \mu$. \item\label{defi3.3.3} \textbf{Twin cuts:} There is $i$ such that a node belongs to $C_{i+1}$ if and only if its children belong to $C_i$, and $T'$ is obtained by deleting simultaneously all nodes in $C_i$, $C'$ is obtained from $C$ by deleting $C_i$, and $\mu'$ is obtained from $\mu$ by merging $\mu_i$ and $\mu_{i+1}$. \end{enumerate} \end{defi} \begin{figure} \centerline{ \includegraphics[scale=.9]{paintedTree5} \hspace{.1cm}\raisebox{.3cm}{$\xrightarrow{\text{ (i) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree6} \hspace{.1cm}\raisebox{.3cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree7} \hspace{.1cm}\raisebox{.3cm}{$\xrightarrow{\text{ (iii) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree8} \hspace{.1cm}\raisebox{.3cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree9} } \caption{Deletions in $2$-painted $5$-trees.}\label{fig:paintedTreeDeletions} \end{figure} \begin{prop}\label{prop:paintedTreeDeletion} For all integers $m, n \ge 0$, the set $\f{PT}_{m,n}$ is stable by deletion, and the deletion graph is the Hasse diagram of a poset ranked by \[ \rank(T, C, \mu) = m + n - |T| - |C| + |\bigcup C|. \] In particular an $m$-painted $n$-tree $\PT \eqdef (T, C, \mu)$ has \begin{itemize} \item rank $0$ if and only $|C| = m$, and all nodes in $\bigcup C$ (resp.~not in $\bigcup C$) have degree $1$ (resp. $2$), \item rank $m+n-2$ if and only if either $|C| = 1$ and all but one node are contained in $C_1$, or $|C| = 2$ and all nodes are contained in $C_1 \cup C_2$, \item rank $m+n-1$ if and only if it has a single node. \end{itemize} \end{prop} \begin{proof} Consider a deletion transforming $\PT \eqdef (T, C, \mu)$ to $\PT' \eqdef (T', C', \mu')$.\linebreak Then~$\PT'$ is clearly an $m$-painted $n$-tree since the cuts of $C'$ are still disjoint and one below the other, and $|C'| = |\mu'|$. For the rank, we distinguish three cases corresponding to that of Definition~\ref{def:paintedTreeDeletion}: \begin{itemize} \item[\eqref{defi3.3.1}] \textbf{Free child:} $|T'| = |T|-1$ while $C' = C$ so that $|C'| = |C|$ and $|\bigcup C'| = |\bigcup C|$. \item[\eqref{defi3.3.2}] \textbf{Free parent:} $|T'| = |T| - |\children(\node{p})|$, $|C'| = |C|$ and $|\bigcup C'| = |\bigcup C| - |\children(\node{p})| + 1$. \item[\eqref{defi3.3.3}] \textbf{Twin cuts:} $|T'| = |T| - |C_i|$, $|C'| = |C|-1$ and $|\bigcup C'| = |\bigcup C| - |C_i|$. \end{itemize} In all three situations, we get $\rank(\PT') = \rank(\PT)+1$. The end of the statement immediately follows. \end{proof} \begin{defi}\label{def:paintedTreeDeletionPoset} The \emph{$m$-painted $n$-tree deletion poset} is the poset on $\f{PT}_{m,n}$ where an $m$-painted $n$-tree is covered by all $m$-painted $n$-trees that can be obtained by a deletion. \end{defi} The $m$-painted $n$-tree deletion poset can alternatively be defined using preposets. \begin{defi}\label{def:paintedTreePreposet} A $m$-painted $n$-tree $\PT \eqdef (T, C, \mu)$ defines a preposet $\preccurlyeq_{\PT}$ on~$[m+n]$ that can be read as follows. Label each node $\node{n}$ of $T$ by the union of the part $\mu_i$ if $\node{n} \in C_i$ (empty set if $\node{n} \notin \bigcup C$) and the inorder label of $\node{n}$ in $T$ shifted by $m$ (empty set if $\node{n}$ has degree $1$). Then merge together all nodes contained in each cut. Then, for any $i,j \in [m+n]$, we have $i \preccurlyeq_{\PT} j$ if there is a (possibly empty) oriented path from the node containing $i$ to the node containing $j$ in the resulting oriented graph. \end{defi} \begin{prop}\label{prop:characterizationPaintedTreePreposets} The preposets $\preccurlyeq_{\PT}$ for $\PT \in \f{PT}_{m,n}$ are precisely the preposets~$\preccurlyeq$ on $[m+n]$ in which any $1 \le i < k \le m+n$ are comparable (\ie $i \preccurlyeq k$ or~$i \succcurlyeq k$ or both) if and only if \begin{itemize} \item either $i \le m$, \item or $m < i$ and at least one of the following holds: \begin{itemize} \item there exists no $i < j < k$ such that $i \prec j \succ k$, \item there exists $j \in [m]$ such that $i \preccurlyeq j \preccurlyeq k$ or $i \succcurlyeq j \succcurlyeq k$. \end{itemize} \end{itemize} \end{prop} \begin{proof} Any preposet $\preccurlyeq_{\PT}$ clearly satisfies these conditions. Conversely, given a preposet $\preccurlyeq$ on ${[m+n]}$ satisfying these conditions, consider the preposet $\preccurlyeq'$ on $[n]$ defined by $i \preccurlyeq' k$ if and only if ${i + m \preccurlyeq k+m}$ and there is no $i < j < k$ such that~$i + m \prec j + m \succ k + m$. The preposet $\preccurlyeq'$ is clearly the preposet $\preccurlyeq_T$ of a Schr\"oder $n$-tree $T$. We then obtain the cuts $C$ and the partition $\mu$ by considering the relations~$i \preccurlyeq k$ with $i \le m < k$. Details are left to the reader. \end{proof} \begin{prop}\label{prop:paintedTreeDeletionPosetOnPreposets} In the $m$-painted $n$-tree deletion poset, $\PT$ is smaller than~$\PT'$ if and only if $\preccurlyeq_{\PT}$ refines $\preccurlyeq_{\PT'}$. \end{prop} \begin{proof} An immediate case analysis shows that deletions in a painted tree $\PT$ defined in Definition~\ref{def:paintedTreeDeletion} precisely translate all possible refinements in the corresponding preposet $\preccurlyeq_{\PT}$. \end{proof} Finally, we define the rotations in painted trees, which correspond to rank $1$ painted trees. To illustrate the following definition, Figure~\ref{fig:paintedTreeRotations} represents a sequence of right rotations in binary $2$-painted $3$-trees. \begin{figure} \centerline{ \includegraphics[scale=.9]{paintedTree10} \hspace{.1cm}\raisebox{.5cm}{$\xrightarrow{\text{ (iii) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree11} \hspace{.1cm}\raisebox{.5cm}{$\xrightarrow{\text{ (i) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree12} \hspace{.1cm}\raisebox{.5cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \includegraphics[scale=.9]{paintedTree13} } \caption{Right rotations in binary $2$-painted $3$-trees.}\label{fig:paintedTreeRotations} \end{figure} \begin{defi}\label{def:rotationsPaintedTrees} We call \emph{binary $m$-painted $n$-trees} the rank $0$ $m$-painted $n$-trees, \ie where all nodes in $\bigcup C$ have degree $1$ while all nodes not in $\bigcup C$ have degree~$2$. We say that two binary $m$-painted $n$-trees $\PT \eqdef (T, C, \mu)$ and $\PT' \eqdef (T', C', \mu')$ are connected by a \emph{right rotation} if: \begin{enumerate}\romanenumi \item\label{defi3.9.1} \textbf{Edge rotation:} $T'$ is obtained from $T$ by the right rotation of an edge connecting two binary nodes, $C' = C$ and $\mu' = \mu$, \item\label{defi3.9.2} \textbf{Node--cut sweep:} $T'$ is obtained from $T$ by replacing a binary node $\node{n}_1$ with two unary children $\node{n}_2, \node{n}_3$ by a unary node $\node{n}'_1$ with a binary child $\node{n}'_2$, $C'$ is obtained by replacing $\node{n}_2$ and $\node{n}_3$ by $\node{n}'_1$, and $\mu' = \mu$, \item\label{defi3.9.3} \textbf{Twin cuts:} There is $i$ such that $\mu_i < \mu_{i+1}$ and a node belongs to $C_i$ if and only if its children belong to $C_{i+1}$, and $T' = T$, $C' = C$ and $\mu'$ is obtained from $\mu$ by exchanging the values $\mu_i$ and $\mu_{i+1}$. \end{enumerate} \end{defi} \begin{rema}\label{rem:algebraicInterpretationMultiplihedra} The binary $m$-painted $n$-trees can be interpreted algebraically as follows. We consider a non-associative magma $(X, \ast)$ and $m$ functions $f_1,\, \dots,\, f_m$ from $X$ to $X$ which are not magma homomorphisms. We then consider the terms than can be produced by starting from a sequence of $n$ elements of $X$ and iteratively applying either $\ast$ to two consecutive terms in the sequence or one function $f_i$ (each one used exactly once) to all terms in the sequence. For instance, the terms corresponding to the $4$ trees of Figure~\ref{fig:paintedTreeRotations} are \begin{gather*} \big(f_2 \circ f_1(x) \ast f_2 \circ f_1(y) \big) \ast f_2 \circ f_1(z), \\ \big(f_1 \circ f_2(x) \ast f_1 \circ f_2(y) \big) \ast f_1 \circ f_2(z), \\ f_1 \circ f_2(x) \ast \big(f_1 \circ f_2(y) \ast f_1 \circ f_2(z) \big), \\ f_1 \circ f_2(x) \ast f_1 \big(f_2(y) \ast f_2(z) \big). \end{gather*} \end{rema} \subsection{Permutahedra \texorpdfstring{$\shuffleDP$}{shuffleDP} Associahedra}\label{subsec:multiplihedra} We now consider shuffles of permutahedra with associahedra. \begin{defi}\label{def:multiplihedron} The \emph{$(m,n)$-multiplihedron} is the polytope \[ \Multiplihedron = \Perm[m] \shuffleDP \Asso[n]. \] \end{defi} \begin{rema}\label{rem:multipliheadra} When $n = 1$, we obtain the multiplihedron studied in~\cite{ArdilaDoker,Forcey-multiplihedra, ForceyLauveSottile, MauWoodward, Stasheff-HSpaces, SaneblidzeUmble-diagonals}. Our geometric realization is different from that of~\cite{Forcey-multiplihedra}. For instance, the two facets corresponding to associahedra are translated copies in our realizations of the $(1,n)$-multiplihedron, while they are dilated copies in the realization of~\cite{Forcey-multiplihedra}. \end{rema} This family of polytopes is illustrated in Figures~\ref{fig:multiplihedra2}, \ref{fig:multiplihedra3} and~\ref{fig:multiplihedra4}. We have labeled with $m$-painted $n$-trees all faces in Figure~\ref{fig:multiplihedra2}, and all vertices in Figure~\ref{fig:multiplihedra3} (see also Figure~\ref{fig:multiplihedron23}). We let the reader complete the pictures in Figures~\ref{fig:multiplihedra3} and~\ref{fig:multiplihedra4}. \begin{figure} \centerline{ \begin{tabular}{c@{\hspace{.5cm}}c} \scalebox{1.8}{\includegraphics[scale=.9]{multiplihedron03}} & \scalebox{1.8}{\includegraphics[scale=.9]{multiplihedron12}} \\ $(1, 5, 5, 1)$ & $(1, 6, 6,1)$ \\ \scalebox{1.8}{\includegraphics[scale=.9]{multiplihedron21}} & \scalebox{1.8}{\includegraphics[scale=.9]{multiplihedron30}} \\ $(1, 6, 6,1)$ & $(1, 6, 6,1)$ \end{tabular} } \caption{The $(m,n)$-multiplihedra $\Multiplihedron$ and their $f$-vectors for ${(m,n) = (0,3)}$, $(1,2)$, $(2,1)$ and $(3,0)$. The top left is the $2$-dimensional associahedron $\Asso[3]$ while the other three are all relabelings of the $2$-dimensional permutahedron $\Perm[3]$.}\label{fig:multiplihedra2} \end{figure} \begin{figure} \centerline{ \begin{tabular}{c@{\hspace{.5cm}}c} \scalebox{.55}{\includegraphics[scale=.85]{multiplihedron04}} & \scalebox{.55}{\includegraphics[scale=.85]{multiplihedron13}} \\ $(1, 14, 21, 9, 1)$ & $(1, 21, 32, 13, 1)$ \end{tabular} } \vspace{.2cm} \centerline{ \begin{tabular}{c@{\hspace{.5cm}}c} \scalebox{.55}{\includegraphics[scale=.85]{multiplihedron22}} & \scalebox{.55}{\includegraphics[scale=.85]{multiplihedron31}} \\ $(1, 24, 36, 14, 1)$ & $(1, 24, 36, 14, 1)$ \end{tabular} } \vspace{-.2cm} \centerline{ \begin{tabular}{c} \scalebox{.55}{\includegraphics[scale=.85]{multiplihedron40}} \\ $(1, 24, 36, 14, 1)$ \end{tabular} } \caption{The $(m,n)$-multiplihedra $\Multiplihedron$ and their $f$-vectors for \linebreak $(m,n) = (0,4)$, $(1,3)$, $(2,2)$, $(3,1)$ and $(4,0)$. The top two are the $3$-dimensional associahedron $\Asso[4]$ and multiplihedron, while the bottom three are all relabelings of the $3$-dimensional permutahedron $\Perm[4]$.}\label{fig:multiplihedra3} \end{figure} \begin{figure} \centerline{ \begin{tabular}{c@{\qquad}c} \includegraphics[scale=1]{multiplihedron05} & \includegraphics[scale=1]{multiplihedron14} \\[.2cm] $(1, 42, 84, 56, 14, 1)$ & $(1, 80, 165, 110, 25, 1)$ \\[.5cm] \includegraphics[scale=1]{multiplihedron23} & \includegraphics[scale=1]{multiplihedron32} \\[.2cm] $(1, 108, 219, 140, 29, 1)$ & $(1, 120, 240, 150, 30, 1)$ \end{tabular} } \caption{Schlegel diagrams and $f$-vectors of the $(m,n)$-multiplihedra $\Multiplihedron$ for $(m,n) = (0,5)$, $(1,4)$, $(2,3)$ and $(3,2) \sim (4,1) \sim (5,0)$. The top left, top right, and bottom right polytopes are the $4$-dimensional associahedron $\Asso[5]$, multiplihedron, and permutahedron $\Perm[5]$. The bottom left polytope is the $(2,3)$-multiplihedron, labeled in Figure~\ref{fig:multiplihedron23}.}\label{fig:multiplihedra4} \end{figure} \begin{prop}\label{prop:faceLatticeMultiplihedron} The face lattice of the $(m,n)$-multiplihedron $\Multiplihedron$ is isomorphic to the $m$-painted $n$-tree deletion poset (augmented with a minimal element). \end{prop} %\pagebreak \begin{proof} This follows from Proposition~\ref{prop:shuffleFacePreposets} (see also Remark~\ref{rem:biPreposets}). Indeed, associate to an $m$-painted $n$-tree $\PT \eqdef (T, C, \mu)$ the face preposet $\preccurlyeq_{\polytope{F}, \polytope{G}, \lambda}$ where \begin{itemize} \item $\polytope{F}$ is the face of the permutahedron $\Perm[m]$ corresponding to the partition~$\mu$, \item $\polytope{G}$ is the face of the associahedron $\Asso[n]$ corresponding to the Schr\"oder tree obtained by deleting all unary nodes in $T$, and \item $\lambda$ is the partition of $[m+n]$ with \begin{itemize} \item a part formed by $\mu_i$ and the inorder labels of the nodes of $C_i$ for each cut $C_i$ containing a non-unary node, \item a part formed by $\mu_i \cup \dots \cup \mu_j$ for each maximal sequence of cuts $C_i,\,\dots,\,C_j$ containing only unary nodes and such that $\stump{C_{k+1}} = \stump{C_k} \ssm C_k$ for\linebreak all~$i < k \le j$, and \item a part formed by the inorder labels of the nodes in between the cuts $C_i$ and $C_{i+1}$ (\ie the nodes of $\stump{C_i} \ssm (C_i \cup \stump{C_{i+1}})$) for each $i \in [|C|-1]$. \end{itemize} \end{itemize} We leave to the reader the immediate verification that this yields a poset isomorphism from the deletion poset on $m$-painted $n$-trees to the refinement poset on the face preposets of the $(m,n)$-multiplihedron $\Multiplihedron = \Perm[m] \shuffleDP \Asso[n]$. \end{proof} \begin{rema}\label{rem:simpleMultiplihedron} In contrast to the permutahedron $\Perm[m]$ and the associahedron $\Asso[n]$, the multiplihedron $\Multiplihedron$ is simple if and only if $m = 0$ or~$n \le 2$. \end{rema} \begin{prop}\label{prop:fanMultiplihedron} The normal fan of the $(m,n)$-multiplihedron $\Multiplihedron$ is the fan containing one cone $\polytope{C}(\PT) \eqdef \{\b{x} \in \R^{m+n}\,|\,x_i \le x_j \text{ if } i \preccurlyeq_{\PT} j\}$ for\linebreak each~${\PT \in \f{PT}_{m,n}}$. \end{prop} \begin{proof} Immediate from Proposition~\ref{prop:faceLatticeMultiplihedron} and Definition~\ref{def:paintedTreePreposet}. \end{proof} \begin{prop}\label{prop:graphMultiplihedron} When oriented in the direction \[ {\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\dots,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}, \] the graph of the $(m,n)$-multiplihedron $\Multiplihedron$ is isomorphic to the right rotation graph on binary $m$-painted $n$-trees, and is the Hasse diagram of a lattice. \end{prop} \begin{proof} It follows from Proposition~\ref{prop:faceLatticeMultiplihedron} that the vertices of $\Multiplihedron$ correspond to the binary $m$-painted $n$-trees. It is easy to check that the edges of $\Multiplihedron$ oriented by $\b{\omega}$ correspond to right rotations on binary $m$-painted $n$-trees. Finally, the lattice property is a special case of Corollary~\ref{coro:latticeShufflePermutahedron}. \end{proof} \begin{rema}\label{rem:notSemidistributive} In contrast to the weak order on $\f{S}_m$ and the Tamari lattice on~$\f{B}_n$, the lattice of Proposition~\ref{prop:graphMultiplihedron} is not a lattice quotient of the weak order and is not even semidistributive when $m \ge 1$ and $n \ge 3$. \end{rema} \begin{rema}\label{rem:graphMultiplihedra} Similarly, the shuffle of an $m$-permutahedron with a graph associahedron is a generalization of the graph multiplihedron of~\cite{DevadossForcey}. It follows from Corollary~\ref{coro:latticeShufflePermutahedron} that the resulting rotation graph is a lattice as soon as the graph associahedron is a lattice (necessary and sufficient conditions for the latter are discussed in~\cite{BarnardMcConville}). \end{rema} \subsection{Vertex, facet, and Minkowski sum descriptions}\label{subsec:vertexFacetMinkowskiDescriptionsMultiplihedra} Our next three statements, illustrated in Figures~\ref{fig:coordinatesPaintedTrees} and~\ref{fig:inequalitiesPaintedTrees}, provide the vertex, facet, and Minkowski sum descriptions of the $(m,n)$-multi\-plihedron $\Multiplihedron$. The proofs are elementary computations from Definitions~\ref{def:permutahedron}, \ref{def:associahedron}, \ref{def:graphicalZonotope} and~\ref{def:multiplihedron}. \begin{prop}\label{prop:verticesMultiplihedron} For any $i \in [m+n]$, the $i^{\rm th}$ coordinate of the vertex of the $(m,n)$-multiplihedron $\Multiplihedron$ corresponding to a binary $m$-painted $n$-tree is given by \begin{itemize} \item if $i \le m$, the number of binary nodes and cuts weakly below the cut labeled by $i$, \item if $i \ge m+1$, the number of cuts below $\node{n}$ plus the product of the numbers of leaves in the left and right subtrees of $\node{n}$, where $\node{n}$ is the node labeled by $i-m$ in inorder. \end{itemize} In particular, the sum of the coordinates is always $(\begin{smallmatrix} m+1\\2 \end{smallmatrix}) + (\begin{smallmatrix} n+1\\ 2\end{smallmatrix}) + mn = (\begin{smallmatrix}m+n+1\\ 2\end{smallmatrix})$. \end{prop} \begin{prop}\label{prop:facetsMultiplihedron} Let $\PT \eqdef (T, C, \mu)$ be an $m$-painted $n$-tree of rank\linebreak${m+n -2}$. Let $A$ be the elements of $[m]$ which label a cut not containing the root of $T$ (${A = \varnothing}$ if $C$ has only one cut, which contains the root of $T$), and $B \eqdef B_1 \cup \dots \cup B_k$ where $B_1, \dots, B_k$ are the inorder labels shifted by $m$ of the non-unary nodes of $T$ distinct from the root of $T$. Then the facet of the $(m,n)$-multiplihedron $\Multiplihedron$ corresponding to $\PT$ is defined by the inequality \[ \textstyle{\dotprod{\b{x}}{\one_{A\,\cup\,B}} \ge \binom{|A|+1}{2} + \binom{|B_1|+1}{2} + \dots + \binom{|B_k|+1}{2} + |A| \cdot |B|.} \] Moreover, this inequality is a facet defining inequality of the permutahedron\linebreak${\Perm[m+n]}$ if and only if $k \le 1$, that is, if $T$ has at most two non-unary nodes. \end{prop} \begin{prop}\label{prop:MinkowskiMultiplihedron} The $(m,n)$-multiplihedron $\Multiplihedron$ is the Minkowski sum of the faces $\simplex_I \eqdef \conv \{\b{e}_i\,|\,i \in I\}$ of the standard simplex $\simplex_{[m+n]}$ corresponding to all subsets $I \subseteq [m+n]$ such that $|I| \le 2$ and $|I \cap [n]^{+m}| \le 1$, or $I$ is a subinterval of $[n]^{+m}$. \end{prop} \begin{figure}[!h] \centerline{ \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} $\PT_1$ & $\PT_2$ & $\PT_3$ & $\PT_4$ & $\PT_5$ \\[.2cm] \includegraphics[scale=.9]{paintedTree14} & \includegraphics[scale=.9]{paintedTree15} & \includegraphics[scale=.9]{paintedTree16} & \includegraphics[scale=.9]{paintedTree17} & \includegraphics[scale=.9]{paintedTree18} \\[.1cm] $(4, 3, 6, 1, 2, 5)$ & $(1, 3, 5, 4, 2, 6)$ & $(3, 1, 5, 2, 4, 6)$ & $(4, 1, 6, 2, 6, 2)$ & $(4, 1, 5, 2, 7, 2)$ \end{tabular} } \vspace*{-7pt} \caption{Vertices of $\Multiplihedron[3][3]$ corresponding to five binary $3$-painted $3$-trees.}\label{fig:coordinatesPaintedTrees} \end{figure} \begin{figure}[!h] \centerline{ \begin{tabular}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} $\PT[S]_1$ & $\PT[S]_2$ & $\PT[S]_3$ & $\PT[S]_4$ & $\PT[S]_5$ \\[.2cm] \includegraphics[scale=.9]{paintedTree19} & \includegraphics[scale=.9]{paintedTree20} & \includegraphics[scale=.9]{paintedTree21} & \includegraphics[scale=.9]{paintedTree22} & \includegraphics[scale=.9]{paintedTree23} \\[.1cm] $x_4 + x_5 \ge 3$ & $x_1 + x_2 + x_4$ & $x_1 + x_2 + x_3$ & $x_2 + x_4 + x_6 \ge 5$ & $x_1 + x_2 + x_3$ \\ & $+ x_5 \ge 10$ & $+ x_4 + x_5 \ge 15$ & & $+ x_4 + x_6 \ge 14$ \end{tabular} } \vspace*{-7pt} \caption{Facet defining inequalities of $\Multiplihedron[3][3]$ corresponding to five rank $4$ $3$-painted $3$-trees.}\label{fig:inequalitiesPaintedTrees} \end{figure} \begin{exam} Figure~\ref{fig:coordinatesPaintedTrees} illustrates some vertex coordinates of $\Multiplihedron[3][3]$ computed by Proposition~\ref{prop:verticesMultiplihedron} and Figure~\ref{fig:inequalitiesPaintedTrees} illustrates some facet inequalities of $\Multiplihedron[3][3]$ computed by Proposition~\ref{prop:facetsMultiplihedron}. Note that all vertices of $\Multiplihedron[3][3]$ have coordinate sum $21$. Note that for any pair $(i, j) \in \{(1, 1), (1, 2), (2, 2), (2, 3), (3, 2),$ $(3, 3), (4, 4), (5, 4), (5, 5)\}$, we have $\PT_i$ smaller than $\PT[S]_j$ in deletion order, so that the vertex corresponding to $\PT_i$ is contained in the facet corresponding to $\PT[S]_j$. \end{exam} \subsection{Numerology}\label{subsec:numerologyMultiplihedra} We now present enumerative results on the number of vertices, faces and facets of the $(m,n)$-multiplihedron $\Multiplihedron$, using standard techniques from generating functionology~\cite{FlajoletSedgewick}. The first few values of these numbers are collected in Tables~\ref{table:verticesMultiplihedra}, \ref{table:facetsMultiplihedra} and~\ref{table:facesMultiplihedra} in Section~\ref{subsec:tablesMultiplihedra}. We start with vertices, which appear as~\cite[\OEIS{A158825}]{OEIS} up to a factorial factor, generalizing the formula of~\cite[Thm.~3.1]{Forcey-multiplihedra}. See~Table~\ref{table:verticesMultiplihedra}. \begin{prop}\label{prop:numberVerticesMultiplihedra} The number of vertices of the $(m,n)$-multiplihedron\linebreak $\polytope{M}\mathrm{ul}(m, n)$ %$\Multiplihedron$ (equivalently, of binary $m$-painted $n$-trees) is \[ m! \, \left[y^{n+1}\right] \, \CGF^{(m+1)}(y), \] where $[y^{n+1}]$ selects the coefficient of $y^{n+1}$, and $\CGF^{(i)}(y)$ is defined for $i \ge 1$ by \[ \CGF^{(1)}(y) \eqdef \CGF(y) \qquad\text{and}\qquad \CGF^{(i+1)}(y) \eqdef \CGF \big(\CGF^{(i)}(y) \big), \] where \[ \CGF(y) = \frac{1-\sqrt{1-4y}}{2} \] is the Catalan generating function (see Proposition~\ref{prop:CatalanSchroderGF}). \end{prop} \begin{proof} According to Propositions~\ref{prop:paintedTreeDeletion} and~\ref{prop:faceLatticeMultiplihedron}, we need to count the binary $m$-painted $n$-trees. We construct a binary $m$-painted tree by \begin{itemize} \item choosing a binary tree $T$ above the topmost cut (thus the apparition of $\CGF$), \item grafting at each leaf of $T$ a binary tree with $m-1$ cuts (thus the substitution of the $y$ variable in $\CGF$), \item choosing the permutation of $[m]$ that will label the $m$ cuts (thus the factor $m!$). \qedhere \end{itemize} \end{proof} We now consider the number of facets of the $(m,n)$-multiplihedron $\Multiplihedron$, generalizing the formula of~\cite[Thm.~2.4]{Forcey-multiplihedra}. See~Table~\ref{table:facetsMultiplihedra}. \begin{prop}\label{prop:numberFacetsMultiplihedra} The number of facets of the $(m,n)$-multiplihedron \linebreak $\Multiplihedron$ is \[ \textstyle{ \binom{n+1}{2} - 1 + 2^{m+n} - 2^n.} \] \end{prop} \begin{proof} According to Propositions~\ref{prop:paintedTreeDeletion} and~\ref{prop:faceLatticeMultiplihedron}, there are two types of $m$-painted $n$-trees corresponding to facets of the $(m,n)$-multiplihedron $\Multiplihedron$: \begin{itemize} \item those where the bottommost cut contains the root: this amounts to choose a corolla with $n+1$ leaves, thus $(\begin{smallmatrix} n+1\\ 2 \end{smallmatrix})-1$ choices, \item those where the bottommost cut contains all children of the root: this amounts to choose a non-empty subset of $[m]$ to label this bottommost cut (the complement, if non-empty, will label the topmost cut containing the root), and a subset of $[n]$ for the inorder label of the root, thus $(2^m-1) 2^n$ choices. \qedhere \end{itemize} \end{proof} Finally, adapting the approach of Proposition~\ref{prop:numberVerticesMultiplihedra}, we can count all faces of the $(m,n)$-multipli\-hedron $\Multiplihedron$ according to their dimension. \begin{prop}\label{prop:numberFacesMultiplihedra} Let $PT(m,n,p)$ denote the number of $p$-dimensional faces of the $(m,n)$-multipli\-hedron $\Multiplihedron$, or equivalently the number of $m$-painted $n$-trees of rank $p$. Then the generating function \begin{align*} \PTGF(x,y,z) &\eqdef \sum_{m,n,p} PT(m,n,p) \, x^m \, y^n \, z^p \\ \intertext{is given by} \PTGF(x,y,z) &= \sum_m x^m \sum_{k = 0}^m \SGF \big(\tSGF^{(k)}(y,z), z \big) \, \surjections{m}{k} \, z^{m-k}, \end{align*} where $\surjections{m}{k}$ is the number of surjections from $[m]$ to $[k]$, \[ \SGF(y,z) = \frac{1+yz-\sqrt{1-4y-2yz+y^2z^2}}{2(z+1)} \] is the Schr\"oder generating function (see Proposition~\ref{prop:CatalanSchroderGF}), and $\tSGF^{(i)}(y,z)$ is defined for $i \ge 0$~by \[ \tSGF^{(0)}(y,z) \eqdef y, \;\; \tSGF^{(1)}(y,z) \eqdef (1+z) \, \SGF(y,z) - yz \;\;\text{and}\;\; \tSGF^{(i+1)}(y,z) \eqdef \tSGF^{(i)} \big(\tSGF^{(1)}(y,z), z \big). \] \end{prop} \begin{proof} According to Propositions~\ref{prop:paintedTreeDeletion} and~\ref{prop:faceLatticeMultiplihedron}, we need to count the $m$-painted $n$-trees of rank $p$. We count them according to their number $k$ of cuts. For $k = 0$, we just obtain the Schr\"oder generating function $\SGF(y,z)$ multiplied by $z^m$ to take the rank shift into account. For $k \ge 1$, we construct an $m$-painted tree with $k$ cuts by \begin{itemize} \item choosing a Schr\"oder tree $S$ above the topmost cut (thus the apparition of $\SGF$), \item grafting at each leaf of $S$ a Schr\"oder tree with $k-1$ cuts (thus the substitution of the $y$ variable in $\SGF$), whose root may or may not lie on the topmost cut (explaining the twist from $\SGF(y,z)$ to $(1+z) \, \SGF(y,z) - yz$), \item choosing the ordered partition of $[m]$ that will label the $k$ cuts (thus the factor~$\surjections{m}{k}$). \end{itemize} Finally, since an $m$-painted $n$-tree $(T,C,\mu)$ yields a monomial $y^n z^{n - |T| + |\bigcup C|}$ in the generating function $\SGF (\tSGF^{(k)}(y,z), z)$, we multiply by the factor $z^{m-k}$ to take into account $m - |C|$ in the definition of the rank $\rank(T,C) \eqdef m + n - |T| - |C| + |\bigcup C|$. \end{proof} We derive from Proposition~\ref{prop:numberFacesMultiplihedra} the total number of faces of the $(m,n)$-multipli\-hedron $\Multiplihedron$. See~Table~\ref{table:facesMultiplihedra}. \begin{prop}\label{prop:numberFacesMultiplihedra2} The number of faces of the $(m,n)$-multiplihedron\linebreak ${\Multiplihedron}$ (equivalently, of $m$-painted $n$-trees) is \[ \sum_{k = 0}^m \surjections{m}{k} \, \left[y^{n+1}\right] \SGF \big(\tSGF^{(k)}(y) \big) \] where $\surjections{m}{k}$ is the number of surjections from $[m]$ to $[k]$, \[ \SGF(y) = \frac{1+y-\sqrt{1-6y+y^2}}{4} \] is the Schr\"oder generating function (see Proposition~\ref{prop:CatalanSchroderGF}), and $\tSGF^{(i)}(y)$ is defined for~$i \ge 0$~by \[ \tSGF^{(0)}(y) \eqdef y, \;\; \tSGF^{(1)}(y) \eqdef 2 \, \SGF(y) - y \;\;\text{and}\;\; \tSGF^{(i+1)}(y) \eqdef \tSGF^{(i)} \big(\tSGF^{(1)}(y) \big). \] \end{prop} For instance, the $f$-vectors of all multiplihedra $\Multiplihedron$ with $m + n \le 5$ are displayed in Figures~\ref{fig:multiplihedra2}, \ref{fig:multiplihedra3} and~\ref{fig:multiplihedra4}. The $f$-vector of the $(3,3)$-multiplihedron~$\Multiplihedron[3][3]$ is \[ f(\Multiplihedron[3][3]) = (1, 660, 1668, 1467, 518, 61, 1). \] \section{Constrainahedra}\label{sec:constrainahedra} In this section, we study the family of $(m,n)$-constrainahedra, obtained as the shuffle of an $m$-associahedron $\Asso[m]$ with an $n$-associahedron $\Asso[n]$. A first description of the constrainahedra appeared in~\cite{Tierney}, based on a private communication from N.~Bottman. The rigorous description in terms of good rectangular preorders was worked out in~\cite{BottmanPoliakova,Poliakova}, where the constrainahedra are also realized as convex polytopes. We provide the alternative combinatorial model of cotrees (Section~\ref{subsec:cotrees}), describe the face lattice, fan and oriented skeleton of the $(m,n)$-constrainahedron in terms of these cotrees (Section~\ref{subsec:constrainahedra}), provide explicit vertex, facet and Minkowski sum descriptions of the $(m,n)$-constrainahedron (Section~\ref{subsec:vertexFacetDescriptionsConstrainahedra}), and present enumerative results on the number of vertices, faces and facets of the $(m,n)$-constrainahedron (Section~\ref{subsec:numerologyConstrainahedra}). \subsection{Cotrees}\label{subsec:cotrees} We start by defining cotrees, illustrated in Figure~\ref{fig:cotrees}. Intuitively, a cotree is a pair of Schr\"oder trees both growing in the same direction (say down), drawn side to side, together with the information of the relative positions of their nodes. Examples are illustrated in Figure~\ref{fig:cotrees}. \begin{defi}\label{def:cotree} A \emph{$(m,n)$-cotree} is a triple $\BT \!\eqdef\! (L, R, \mu)$, where $L$ is a Schr\"oder $m$-tree, $R$ is a Schr\"oder $n$-tree, and $\mu$ is an ordered partition of the nodes of $L$ and~$R$~such~that \begin{itemize} \item the part of $\mu$ containing a node $\node{n}$ of $L$ (resp. $R$) distinct from the root is before or equal to the part of $\mu$ containing the parent of $\node{n}$, \item no two consecutive parts of $\mu$ are both contained in $L$ or both contained in~$R$, \item there is no oriented path in $L$ (resp.~in $R$) joining two nodes in a part of $\mu$ which meets both $L$ and $R$. \end{itemize} We say that a part of $\mu$ is of type $\ell$, $r$ or $b$ when it contains nodes from $L$, $R$ or both~$L$ and $R$, and we call \emph{type} of the cotree the word given by the sequence of types of the parts of $\mu$. We denote by $\f{CT}_{m,n}$ the set of $(m,n)$-cotrees. \end{defi} To represent a $(m,n)$-cotree $\CT \eqdef (L, R, \mu)$, we draw the two trees $L$ and $R$ side by side, and we mark the separations between the parts of $\mu$ by (red) horizontal lines. Note that $\mu$ is read from bottom to top. Examples are illustrated in Figure~\ref{fig:cotrees}. \begin{figure}[!h] \centerline{ \includegraphics[scale=.9]{cotree1} \hspace*{.5cm} \includegraphics[scale=.9]{cotree2} } \caption{A $(10,7)$-cotree of type $r\ell r\ell b\ell r$ (left), a binary $(8,6)$-cotree of type $r\ell r\ell r\ell$ (right).}\label{fig:cotrees} \end{figure} We now define the cotree deletion poset. Definition~\ref{def:cotreeDeletion} provides a direct description in terms of cotrees, while Definition~\ref{def:cotreePreposet} provides an alternative simpler but indirect description in terms of preposets. To illustrate the following definition, Figure~\ref{fig:cotreeDeletions} represents a sequence of deletions in $(7,5)$-cotrees. \begin{figure} \centerline{ \begin{tabular}{c} \includegraphics[scale=.9]{cotree3} \\ $\big\downarrow$ {\scriptsize (i)(a)} \\[.2cm] \includegraphics[scale=.9]{cotree4} \\ $\big\downarrow$ {\scriptsize (i)(b)} \\[.2cm] \includegraphics[scale=.9]{cotree5} \\ \end{tabular} \hspace{.1cm}\raisebox{-4.5cm}{$\xrightarrow{\text{ (i)(c) }}$}\hspace{.1cm} \begin{tabular}{c} \includegraphics[scale=.9]{cotree6} \\ $\big\uparrow$ {\scriptsize (iii)} \\[.2cm] \includegraphics[scale=.9]{cotree7} \\ $\big\uparrow$ {\scriptsize (ii)(b)} \\[.2cm] \includegraphics[scale=.9]{cotree8} \\ $\big\uparrow$ {\scriptsize (ii)(a)} \\[.2cm] \includegraphics[scale=.9]{cotree9} \\ \end{tabular} } \caption{Deletions in $(7,5)$-cotrees.}\label{fig:cotreeDeletions} \end{figure} \begin{defi}\label{def:cotreeDeletion} Let $\CT \eqdef (L, R, \mu)$ and $\CT' \eqdef (L', R', \mu')$ be two $(m,n)$-cotrees. We say that $\CT'$ is obtained by a \emph{deletion} in $\CT$ in either of the following three cases: \begin{enumerate}\romanenumi \item\label{defi4.2.1} \textbf{Node deletion:} $L'$ (resp. $R'$) is obtained by deleting a node $\node{n}$ with parent $\node{p}$ in $L$ (resp. $R$) in the following situations: \begin{enumerate}\alphenumi \item\label{defi4.2.1.a} $\node{n}$ and $\node{p}$ belong to the same part of $\mu$, then $\mu'$ is obtained by deleting $\node{n}$ from $\mu$, \item\label{defi4.2.1.b} the part of $\node{n}$ is of type $\ell$ (resp. $r$), the part of $\node{p}$ is of type $b$, and the parts of $\node{n}$ and $\node{p}$ are consecutive, then $\mu'$ is obtained by deleting $\node{n}$ from~$\mu$, \item\label{defi4.2.1.c} the part of $\node{n}$ is of type $b$, the part of $\node{p}$ is of type $\ell$ (resp. $r$), and the parts of $\node{n}$ and $\node{p}$ are consecutive, then $\mu'$ is obtained from $\mu$ by moving $\node{p}$ to the part of $\node{n}$ and deleting $\node{n}$. \end{enumerate} \item\label{defi4.2.2} \textbf{Nodes move:} $L' = L$, $R' = R$, and $\mu'$ is obtained from $\mu$ by \begin{enumerate}\alphenumi \item \label{defi4.2.2.a}either creating, in between two consecutive parts $\mu_i$ of type $\ell$ (resp. $r$) and $\mu_{i+1}$ of type $r$ (resp. $\ell$), a new part containing a node of $\mu_i$ whose children are not in $\mu_i$ and a node of $\mu_{i+1}$ whose parent is not in $\mu_{i+1}$ (and removing these nodes from their original parts~in $\mu$), \item \label{defi4.2.2.b}or moving a node $\node{n}$ from its part $\mu_i$ to the previous (or next) part $\mu_{i \pm 1}$ in~$\mu$, provided that the part $\mu_i$ is not of type $b$, that the part $\mu_{i \pm 1}$ is of type~$b$, and that the parent (or children) of $\node{n}$ does not belong to $\mu_i \cup \mu_{i \pm 1}$, \end{enumerate} \item\label{defi4.2.3}\textbf{Twin parts merge:} $\mu'$ is obtained by merging two consecutive parts of $\mu$ of type $b$, and $L'$ (resp. $R'$) is obtained by deleting any node $\node{n}$ in $L$ (resp. $R$) such that both $\node{n}$ and its parent belong to these parts. \end{enumerate} \end{defi} \begin{prop}\label{prop:cotreeDeletion} For all integers $m, n \ge 0$, the set $\f{CT}_{m,n}$ is stable by deletion, and the deletion graph is the Hasse diagram of a poset ranked by \[ \rank(L, R, \mu) = m + n - |L| - |R| + \beta(\mu), \] where $\beta(\mu)$ is the sum of $|\mu_i|-1$ over all parts $\mu_i$ of $\mu$ with $\mu_i \cap L \ne \varnothing \ne \mu_i \cap R$. In particular a $(m,n)$-cotree $\BT \eqdef (L, R, \mu)$ has \begin{itemize} \item rank $0$ if and only if both $L$ and $R$ are binary trees, and no part of $\mu$ meets both $L$ and $R$, \item rank $m+n-2$ if and only if $\mu$ has two parts, and each part of $\mu$ either meets both $L$ and $R$ or contains a single node, \item rank $m+n-1$ if and only if $\mu$ has a single part (hence, both $L$ and $R$ have a single node). \end{itemize} \end{prop} \begin{proof} Consider a deletion transforming $\CT \eqdef (L, R, \mu)$ to $\CT' \eqdef (L', R', \mu')$.\linebreak Then~$\BT'$ is clearly a $(m,n)$-cotree since $L'$ and $R'$ are still Schr\"oder trees, and the partition~$\mu'$ fulfills the conditions of Definition~\ref{def:cotree}. For the rank, we distinguish three cases corresponding to that of Definition~\ref{def:cotreeDeletion}: \begin{itemize} \item[\eqref{defi4.2.1}] \textbf{Node deletion:} $|L'| + |R'| = |L| + |R| - 1$ while $\beta(\mu') = \beta(\mu')$. \item[\eqref{defi4.2.2}] \textbf{Nodes move:} $|L'| = |L|$, $|R'| = |R|$, while $\beta(\mu') = \beta(\mu) + 1$. \item[\eqref{defi4.2.3}] \textbf{Twin parts merge:} if $\delta$ denotes the number of nodes $\node{n}$ of $L$ and $R$ such that both $\node{n}$ and its parent belong to the merged parts of $\mu$, then $|L'| + |R'| = |L| + |R| - \delta$ and $\beta(\mu') = \beta(\mu) - \delta + 1$. \end{itemize} In all three situations, we get $\rank(\CT') = \rank(\CT)+1$. The end of the statement immediately follows. \end{proof} \begin{defi}\label{def:cotreeDeletionPoset} The \emph{$(m,n)$-cotree deletion poset} is the poset on $\f{CT}_{m,n}$ where a $(m,n)$-cotree is covered by all $(m,n)$-cotrees that can be obtained by a deletion. \end{defi} The $(m,n)$-cotree deletion poset can alternatively be defined using preposets. \begin{defi}\label{def:cotreePreposet} A $(m,n)$-cotree $\CT \eqdef (L, R, \mu)$ defines a preposet $\preccurlyeq_{\CT}$ on $[m+n]$ that can be read as follows. Label $L$ by $[m]$ in inorder and $R$ by $[n]^{+m}$ in inorder (shifted by $m$). Then, for any $i,j \in [m+n]$, we have $i \preccurlyeq_{\CT} j$ if the part of $\mu$ containing~$i$ is before the part of $\mu$ containing $j$, or if there is a (possibly empty) path from the node containing $i$ to the node containing $j$ in the tree $L$ or in the tree $D$ oriented towards their roots. \end{defi} \begin{prop}\label{prop:characterizationCotreePreposets} The preposets $\preccurlyeq_{\CT}$ for $\CT \in \f{CT}_{m,n}$ are precisely the preposets~$\preccurlyeq$ on $[m+n]$ in which any $1 \le i < k \le m+n$ are comparable (\ie $i \preccurlyeq k$ or~$i \succcurlyeq k$ or both) if and only if \begin{itemize} \item either $i \le m < k$, \item or $m < i$ (resp. $k \le m$) and at least one of the following holds: \begin{itemize} \item there exists no $i < j < k$ such that $i \prec j \succ k$, \item there exists $j \in [m]$ (resp. $j \in [n]^{+m}$) such that $i \preccurlyeq j \preccurlyeq k$ or $i \succcurlyeq j \succcurlyeq k$. \end{itemize} \end{itemize} \end{prop} \begin{proof} Any preposet $\preccurlyeq_{\CT}$ clearly satisfies these conditions. Conversely, given a preposet $\preccurlyeq$ on ${[m+n]}$ satisfying these conditions, consider \begin{itemize} \item the preposet $\preccurlyeq_\ell$ on $[m]$ defined by $i \preccurlyeq_\ell k$ if and only if $i \preccurlyeq k$ and there is\linebreak no~$i < j < k$ such that $i \prec j \succ k$, \item the preposet $\preccurlyeq_r$ on $[n]$ defined by $i \preccurlyeq_r k$ if and only if ${i + m \preccurlyeq k+m}$ and there is no ${i < j < k}$ such that $i + m \prec j + m \succ k + m$. \end{itemize} The preposet $\preccurlyeq_\ell$ (resp. $\preccurlyeq_r$) is clearly the preposet $\preccurlyeq_L$ (resp. $\preccurlyeq_R$) of a Schr\"oder $m$-tree $L$ (resp.~a Schr\"oder $n$-tree $R$). We then obtain the partition $\mu$ by considering the relations $i \preccurlyeq k$ with ${i \le m < k}$. Details are left to the reader. \end{proof} \begin{prop}\label{prop:cotreeDeletionPosetOnPreposets} In the cotree deletion poset, $\CT$ is smaller than $\CT'$ if and only if $\preccurlyeq_{\CT}$ refines $\preccurlyeq_{\CT'}$. \end{prop} \begin{proof} An immediate case analysis shows that deletions in a cotree $\CT$ defined in Definition~\ref{def:cotreeDeletion} precisely translate all possible refinements in the corresponding preposet $\preccurlyeq_{\CT}$. \end{proof} Finally, we define the rotations in cotrees, which correspond to rank $1$ cotrees. To illustrate the following definition, Figure~\ref{fig:cotreeRotations} represents a sequence of right rotations in binary $(3,2)$-cotrees. \begin{figure} \centerline{ \includegraphics[scale=.9]{cotree10} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (i) }}$}\hspace{.1cm} \includegraphics[scale=.9]{cotree11} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \raisebox{-.3cm}{\includegraphics[scale=.9]{cotree12}} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \raisebox{.15cm}{\includegraphics[scale=.9]{cotree13}} } \caption{Right rotations in binary $(3,2)$-cotrees.}\label{fig:cotreeRotations} \end{figure} \begin{defi}\label{def:rotationsCotrees} We call \emph{binary $(m,n)$-cotrees} the rank $0$ $(m,n)$-cotrees, \ie \linebreak where both $L$ and $R$ are binary trees, and no part of $\mu$ meets both $L$ and $R$. We say that two binary $(m,n)$-cotrees $\CT \eqdef (L, R, \mu)$ and $\CT' \eqdef (L', R', \mu')$ are connected by a \emph{right rotation} if: \begin{enumerate}\romanenumi \item\label{defi4.8.1} \textbf{Edge rotation:} $L'$ (resp. $R'$) is obtained from $L$ (resp. $R$) by the right rotation of an edge whose endpoints belong to the same part of $\mu$, \item\label{defi4.8.2} \textbf{Twin parts:} $L' = L$, $R' = R$, and $\mu'$ is obtained from $\mu$ by creating, in between two consecutive parts $\mu_i$ of type $\ell$ and $\mu_{i+1}$ of type $r$, first a new part containing a node of $\mu_{i+1}$ whose children are not in $\mu_{i+1}$, and second a new part containing a node of $\mu_i$ whose children are not in $\mu_i$ (and removing these nodes from their original parts in $\mu$, and merging consecutive parts of the same type $\ell$ or $r$ if any). \end{enumerate} \end{defi} \begin{rema}\label{rem:algebraicInterpretationConstrainahedra} The $(m,n)$-cotrees are algebraically motivated by the $(m,n)$-constrainahedron defined in~\cite{BottmanPoliakova,Poliakova,Tierney} as a constrained version of the $2$-associahedra of~\cite{Bottman}. This structure was already studied in details in particular in~\cite[Sect.~5]{Poliakova}, where \begin{itemize} \item the preposets of Proposition~\ref{prop:characterizationCotreePreposets} are already described under the name ``good rectangular preorders'' in~\cite[Sect.~5.1.3]{Poliakova} and~\cite[Sect.~2.1]{BottmanPoliakova}, \item an alternative combinatorial model is given by ``rectangular bracketings'' in~\cite[Sect.~5.1.3]{Poliakova} and~\cite[Sect.~2.3]{BottmanPoliakova} (see Figure~\ref{fig:rectangularTubingsRotations} which illustrates the immediate bijection between binary $(m,n)$-cotrees and maximal $(m,n)$-bracketings), \item the contraction poset on good rectangular preorders is proved to be a lattice in~\cite[Sect.~5.2]{Poliakova} and~\cite[Sect.~3]{BottmanPoliakova} (here, this property is a direct consequence of Proposition~\ref{prop:faceLatticeConstrainahedron}), \item a polytopal realization of this contraction poset is constructed in~\cite[Sect.~5.3]{Poliakova} and~\cite[Sect.~4]{BottmanPoliakova} (which differs from our construction of Section~\ref{subsec:constrainahedra} as discussed in~\cite[Sect.~5]{BottmanPoliakova}). \end{itemize} Note that these realizations even extend to higher dimension: bracketings of a ${n_1 \times n_2 \times \dots \times n_d}$ grid are naturally encoded by the shuffle of associahedra \newline ${\Asso[n_1] \shuffleDP \Asso[n_2] \shuffleDP \dots \shuffleDP \Asso[n_d]}. $ \begin{figure}[h] \centerline{ \includegraphics[scale=1.1]{rectangularTubings1} \raisebox{1cm}{$\longrightarrow$} \includegraphics[scale=1.1]{rectangularTubings2} \raisebox{1cm}{$\longrightarrow$} \includegraphics[scale=1.1]{rectangularTubings3} \raisebox{1cm}{$\longrightarrow$} \includegraphics[scale=1.1]{rectangularTubings4} } \caption{$(3,2)$-rectangular bracketings, corresponding to the binary $(3,2)$-cotrees of Figure~\ref{fig:cotreeRotations}.}\label{fig:rectangularTubingsRotations} \end{figure} \end{rema} \begin{rema}\label{rem:algebraicInterpretationConstrainahedraBis} A simple-minded algebraic interpretation of the binary $(m,n)$-cotrees involves two magmatic products $\bullet$ and $\circ$ on a set $X$. The nodes in the left part of a cotree are associated with the product $\bullet$, those in the right part with the product $\circ$. One starts at the bottom with a $(m+1) \times (n+1)$-matrix of elements of $X$ (with $m+1$ columns and $n+1$ rows). Intermediate steps will go through rectangular $p \times q$-matrices of elements of $X$ with decreasing $1 \le p \le m+1$ and $1 \le q \le n+1$, until one reaches a $1 \times 1$-matrix of elements of $X$ at the top. Going up through a node in the left part of the cotree means applying $\bullet$ to corresponding elements in two consecutive columns of the matrix, replacing these two columns by a single column and decreasing $p$ by $1$. Similarly, going up through a node in the right part of the cotree means applying $\circ$ to corresponding elements in two consecutive rows of the matrix, replacing these two rows by a single row and decreasing $q$ by $1$. In short, a left node stands for $\bullet$ merging two consecutive columns, and a right node for $\circ$ merging two consecutive rows. \end{rema} \subsection{Associahedra \texorpdfstring{$\shuffleDP$}{shuffleDP} Associahedra}\label{subsec:constrainahedra} We now consider shuffles of associahedra with associahedra. \begin{defi}\label{def:constrainahedron} The \emph{$(m,n)$-constrainahedron} is the polytope \[ \Constrainahedron = \Asso[m] \shuffleDP \Asso[n]. \] \end{defi} Note that since $\Perm[1] = \Asso[1]$ and $\Perm[2] = \Asso[2]$, the first $(m,n)$-constrainahedron which is neither an associahedron, nor a $(m,n)$-multiplihedron, is the $(3,3)$-constrainahedron $\Constrainahedron[3][3]$, which is a $5$-dimensional polytope. There is thus no reasonable example to be drawn in this section. \begin{prop}\label{prop:faceLatticeConstrainahedron} The face lattice of the $(m,n)$-constrainahedron\linebreak $\Constrainahedron$ is isomorphic to the $(m,n)$-cotree deletion poset (augmented with a minimal element). \end{prop} \begin{proof} This follows from Proposition~\ref{prop:shuffleFacePreposets} (see also Remark~\ref{rem:biPreposets}), since $(m,n)$-cotrees are just a specialization of bipreposets. \end{proof} \begin{rema}\label{rem:simpleConstrainahedron} In contrast to the associahedron $\Asso$, the constrainahedron $\Constrainahedron$ is simple if and only if $m = 0$, or $n = 0$, or $\max(m,n) \le 2$. \end{rema} \begin{prop}\label{prop:fanConstrainahedron} The normal fan of the $(m,n)$-constrainahedron\linebreak ${\Constrainahedron}$ is the fan containing one cone $\polytope{C}(\BT) \eqdef \{\b{x} \in \R^{m+n}\,|\,x_i \le x_j \text{ if } i \preccurlyeq_{\BT} j\}$ for each ${\CT \in \f{CT}_{m,n}}$. \end{prop} \begin{proof} Immediate from Proposition~\ref{prop:faceLatticeConstrainahedron} and Definition~\ref{def:cotreePreposet}. \end{proof} \begin{prop}\label{prop:graphConstrainahedron} When oriented in the direction \[ {\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}, \] the graph of the $(m,n)$-constrainahedron ${\Constrainahedron}$ is isomorphic to the right rotation graph on binary $(m,n)$-cotrees. \end{prop} \begin{proof} It follows from Proposition~\ref{prop:faceLatticeConstrainahedron} that the vertices of $\Constrainahedron$ correspond to the binary $(m,n)$-cotrees. It is easy to check that the edges of $\Constrainahedron$ oriented by $\b{\omega}$ correspond to right rotations on binary $(m,n)$-cotrees. \end{proof} \begin{figure}[!h] \centerline{ \begin{tikzpicture}[yscale=1.2] \node[label=west:{$\CT_1 =$}] (a) at (-4,4.3) {\includegraphics[scale=.9]{cotree14}}; \node[label=east:{$= \CT_2$}] (b) at (4,4.3) {\includegraphics[scale=.9]{cotree15}}; \node (c) at (-6,0) {\includegraphics[scale=.9]{cotree16}}; \node (d) at (2,0) {\includegraphics[scale=.9]{cotree17}}; \node (e) at (-2,0) {\includegraphics[scale=.9]{cotree18}}; \node (f) at (6,0) {\includegraphics[scale=.9]{cotree19}}; \node[label=west:{$\CT[S]_1 =$}] (g) at (-4,-4.6) {\includegraphics[scale=.9]{cotree20}}; \node[label=east:{$= \CT[S]_2$}] (h) at (4,-4.6) {\includegraphics[scale=.9]{cotree21}}; \draw[thick,gray] (a.south) -- (c.north); \draw[thick,gray] (a.south) -- (e.north); \draw[thick,gray] (b.south) -- (d.north); \draw[thick,gray] (b.south) -- (f.north); \draw[thick,gray] (c.south) -- (g.north); \draw[thick,gray] (d.south) -- (g.north); \draw[thick,gray] (e.south) -- (h.north); \draw[thick,gray] (f.south) -- (h.north); \end{tikzpicture}} \caption{Rotations on all $(3,3)$-cotrees larger than $\CT[S]_1$ or $\CT[S]_2$ and smaller than~$\CT_1$ or $\CT_2$. This shows that $\CT[S]_1$ and $\CT[S]_2$ have no join, and $\CT_1$ and $\CT_2$ have no meet, so that the rotation graph on binary $(3,3)$-cotrees does not define a lattice.}\label{fig:constrainahedronNotLattice} \end{figure} \begin{rema}\label{rem:noCoTamari} In contrast to Proposition~\ref{prop:graphMultiplihedron}, note that the right rotation graph on binary $(m,n)$-cotrees is not the Hasse diagram of a lattice when $m \ge 3$ and $n \ge 3$. See Figure~\ref{fig:constrainahedronNotLattice} for examples of a pair of binary $(3,3)$-cotrees with no join and a pair of binary $(3,3)$-cotrees with no meet. \end{rema} \subsection{Vertex, facet, and Minkowski sum descriptions}\label{subsec:vertexFacetDescriptionsConstrainahedra} Our next three statements, illustrated in Figures~\ref{fig:coordinatesCotrees} and~\ref{fig:inequalitiesCotrees}, provide the vertex, facet, and Minkowski sum descriptions of the $(m,n)$-constrai\-nahedron $\Constrainahedron$. The proofs are elementary computations from Definitions~\ref{def:associahedron}, \ref{def:graphicalZonotope} and~\ref{def:constrainahedron}. \begin{prop}\label{prop:verticesConstrainahedron} For any $i \in [m+n]$, the $i^{\rm th}$ coordinate of the vertex of the $(m,n)$-constrainahedron $\Constrainahedron$ corresponding to a binary $(m,n)$-cotree $(L, R, \mu)$ is given by \begin{itemize} \item if $i \le m$, the product of the numbers of leaves in the left and right subtrees of $\node{n}$, plus the number of nodes of $R$ below $\node{n}$, where $\node{n}$ is the node of $L$ labeled by $i$ in inorder. \item if $i \ge m+1$, the product of the numbers of leaves in the left and right subtrees of $\node{n}$, plus the number of nodes of $L$ below $\node{n}$, where $\node{n}$ is the node of $R$ labeled by $i-m$ in inorder. \end{itemize} In particular, the sum of the coordinates is always $(\begin{smallmatrix} m+1\\2\end{smallmatrix}) + (\begin{smallmatrix}n+1\\2\end{smallmatrix}) + mn = (\begin{smallmatrix} m+n+1\\2\end{smallmatrix})$. \end{prop} \begin{prop}\label{prop:facetsConstrainahedron} Let $\CT \eqdef (L, R, \mu)$ be a $(m,n)$-cotree of rank $m+n-2$. Let~${A \eqdef A_1 \cup \dots \cup A_k}$ where $A_1,\,\dots A_k$ are the inorder labels of the nodes of $L$ located in the bottom part $\mu_1$, and let ${B \eqdef B_1 \cup \dots \cup B_\ell}$ where $B_1,\,\dots,\, B_\ell$ are the inorder labels shifted by $m$ of the nodes of $R$ located in the bottom part $\mu_1$. Then the facet of the $(m,n)$-constrainahedron $\Constrainahedron$ corresponding to $\CT$ is defined by the inequality \[ \dotprod{\b{x}}{\one_{A \cup B}} \ge \sum_{i\,\in\,[k]} {\textstyle{\binom{|A_i|+1}{2}}} + \sum_{j\,\in\,[\ell]} {\textstyle{\binom{|B_j|+1}{2}}} + |A| \cdot |B|. \] Moreover, this inequality is a facet defining inequality of the permutahedron\linebreak ${\Perm[m+n]}$ if and only if $k \le 1$ and $\ell \le 1$, \ie if both $L$ and $R$ have at most two nodes. \end{prop} \begin{prop}\label{prop:MinkowskiConstrainahedron} The $(m,n)$-constrainahedron $\Constrainahedron$ is the Min\-kowski sum of the faces $\simplex_I \eqdef \conv\{\b{e}_i\,|\,i \in I\}$ of the standard simplex $\simplex_{[m+n]}$ corresponding to all subsets $I \subseteq [m+n]$ such that $|I \cap [m]| \le 1$ and $|I \cap [n]^{+m}| \le 1$, or $I$ is a subinterval of $[m]$ or of $[n]^{+m}$. \end{prop} \begin{exam} Figure~\ref{fig:coordinatesCotrees} illustrates some vertex coordinates of $\Constrainahedron[3][3]$ computed by Proposition~\ref{prop:verticesConstrainahedron} and Figure~\ref{fig:inequalitiesCotrees} illustrates some facet inequalities of $\Constrainahedron[3][3]$ computed by Proposition~\ref{prop:facetsConstrainahedron}. Note that all vertices of $\Constrainahedron[3][3]$ have coordinate sum $21$. Note that for any pair $(i, j) \in \{(1, 2), (1, 3), (2, 2), (2, 3), (2, 4),$ $(3, 2), (3, 4), (4, 4)\}$, we have $\CT_i$ smaller than $\CT[S]_j$ in deletion order, so that the vertex corresponding to $\CT_i$ is contained in the facet corresponding to $\CT[S]_j$. \begin{figure}[h] \centerline{ \begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c} $\CT_1$ & $\CT_2$ & $\CT_3$ & $\CT_4$ \\[.2cm] \includegraphics[scale=.9]{cotree22} & \includegraphics[scale=.9]{cotree23} & \includegraphics[scale=.9]{cotree24} & \includegraphics[scale=.9]{cotree25} \\[.1cm] $(1, 5, 6, 2, 5, 2)$ & $(1, 7, 4, 2, 5, 2)$ & $(1, 7, 3, 2, 6, 2)$ & $(1, 7, 1, 3, 6, 3)$ \end{tabular} } \caption{Vertices of $\Constrainahedron[3][3]$ corresponding to four binary $(3,3)$-cotrees.}\label{fig:coordinatesCotrees} \end{figure} \begin{figure}[h] \centerline{ \begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c} $\CT[S]_1$ & $\CT[S]_2$ & $\CT[S]_3$ & $\CT[S]_4$ \\[.2cm] \includegraphics[scale=.9]{cotree26} & \includegraphics[scale=.9]{cotree27} & \includegraphics[scale=.9]{cotree28} & \includegraphics[scale=.9]{cotree29} \\[.1cm] $x_3 + x_4 + x_5 \ge 6$ & $x_1 + x_4 + x_6 \ge 5$ & $x_1 + x_4 + x_5$ & $x_1 + x_3 + x_4$ \\ & & $+ x_6 \ge 10$ & $+ x_5 + x_6 \ge 14$ \end{tabular} } \caption{Facet defining inequalities of $\Constrainahedron[3][3]$ corresponding to four rank~$4$ $(3,3)$-cotrees.}\label{fig:inequalitiesCotrees} \end{figure} \end{exam} \subsection{Numerology}\label{subsec:numerologyConstrainahedra} We now present enumerative results on the number of vertices, faces and facets of the $(m,n)$-constrainahedron $\Constrainahedron$. The first few values of these numbers are collected in Tables~\ref{table:verticesConstrainahedraBiassociahedra}, \ref{table:facetsConstrainahedraBiassociahedra} and~\ref{table:facesConstrainahedra} in Section~\ref{subsec:tablesConstrainahedraBiassociahedra}. We start with vertices. See~Table~\ref{table:verticesConstrainahedraBiassociahedra}. \begin{prop}\label{prop:numberVerticesConstrainahedra} The number of vertices of the $(m,n)$-constrainahedron \linebreak $\Constrainahedron$ (equivalently of binary $(m,n)$-cotrees) is given by \[ \left[x^{m+1} \, y^{n+1}\right] \, \sum_{i = 0}^{\min(m,n)} 2 \, \tCGF^{(i)}(x) \, \tCGF^{(i)}(y) + \tCGF^{(i)}(x) \, \tCGF^{(i+1)}(y) + \tCGF^{(i+1)}(x) \, \tCGF^{(i)}(y), \] where $\tCGF^{(i)}(x)$ is defined for $i \ge 0$ by \[ \tCGF^{(0)}(x) = x \qquad\text{and}\qquad \tCGF^{(i)}(x) = \tCGF^{(i-1)}(\CGF(x)) - \tCGF^{(i-1)}(x), \] where \[ \CGF(x) = \frac{1-\sqrt{1-4x}}{2} \] is the Catalan generating function (see Proposition~\ref{prop:CatalanSchroderGF}). \end{prop} \begin{proof} According to Propositions~\ref{prop:cotreeDeletion} and~\ref{prop:faceLatticeConstrainahedron}, we need to count the binary $(m,n)$-cotrees. We group them according to their type, which can be of the form $(\ell r)^i$, $(r\ell)^i$, $(\ell r)^i\ell$ or $(r\ell)^ir$. We then need to construct the two binary trees $L$ and~$R$ with compatible partitions of their nodes into $i$ (or $i+1$) parts. We construct a partitioned binary tree with $i+1$ parts by \begin{itemize} \item choosing a binary tree $T$ for the first part (thus the apparition of $\CGF$), \item grafting at each leaf of $T$ a partitioned binary tree with $i-1$ parts (thus the substitution of the $y$ variable in $\tCGF^{(i)}$), such that not all leaves of $T$ are replaced by an empty binary tree (thus the subtraction of $\tCGF^{(i-1)}$ in the definition of~$\tCGF^{(i)}$).\qedhere \end{itemize} \end{proof} We now consider the number of facets of the $(m,n)$-constrainahedron $\Constrainahedron$. See~Table~\ref{table:facetsConstrainahedraBiassociahedra}. \begin{prop}\label{prop:numberFacetsConstrainahedra} The number of facets of the $(m,n)$-constrainahedron \linebreak $\Constrainahedron$ is \[ \textstyle{ \left(2^m-1\right)\left(2^n-1\right) + \binom{m+1}{2} + \binom{n+1}{2} - 1.} \] \end{prop} \begin{proof} According to Propositions~\ref{prop:cotreeDeletion} and~\ref{prop:faceLatticeConstrainahedron}, the possible types for the $(m,n)$-cotrees corresponding to facets of the $(m,n)$-constrainahedron $\Constrainahedron$ are: \begin{itemize} \item type $\ell r$ (resp.~type $r\ell$): then both $L$ and $R$ have a single node, thus a single choice, \item type $b\ell$ (resp.~type $rb$): then $L$ (resp. $R$) is a non-trivial corolla while $R$ (resp.~$L$) has a single node, thus $(\begin{smallmatrix}m+1\\2\end{smallmatrix})-1$ choices (resp. $(\begin{smallmatrix}n+1\\2\end{smallmatrix})-1$ choices), \item type $\ell b$ (resp.~type $br$): then $L$ (resp. $R$) is any Schr\"oder tree of height $2$ while~$R$ (resp. $L$) has a single node, thus $2^m-2$ choices (resp. $2^n-2$ choices), \item type $bb$: then both $L$ and $R$ are Schr\"oder trees of height $2$, thus $(2^m-2)(2^n-2)$ choices. \qedhere \end{itemize} \end{proof} Finally, adapting the approach of Proposition~\ref{prop:numberVerticesConstrainahedra}, we can count all faces of the $(m,n)$-constraina\-hedron $\Constrainahedron$ according to their dimension. \begin{prop}\label{prop:numberFacesConstrainahedra} Let $CT(m,n,p)$ denote the number of $p$-dimensional faces of the $(m,n)$-constraina\-hedron $\Constrainahedron$, or equivalently the number of $(m,n)$-cotrees of rank $p$. Then the generating function \begin{align*} \CTGF(x,y,z) \eqdef \sum_{m,n,p} CT(m,n,p) \, x^m \, y^n \, z^p \\ \intertext{is given by} \CTGF(x,y,z) = \sum_w \SGF^w_u(x,z) \, \SGF^w_d(y,z) \end{align*} where \begin{itemize} \item $w$ runs over all words on the alphabet $\{\ell,r,b\}$ with no two consecutive $\ell$ nor two consecutive $r$ and such that $1 \le |w|_\ell + |w|_b \le m$ and $1 \le |w|_r + |w|_b \le n$, \item for a letter $s \in \{\ell,r\}$, the generating function $\SGF^w_s(y,z)$ is defined by\linebreak $\SGF^\varepsilon_s(y,z) \eqdef y$ and \[ \SGF^{w}_s(y,z) \eqdef \begin{cases} \SGF^{w'}_s(\SGF(y,z), z) - \SGF^{w'}_s(y,z) & \text{if } w = sw', \\ \SGF^{w'}_s \left(\frac{y}{1-yz}, z \right) - \SGF^{w'}_s(y,z) & \text{if } w = bw', \\ \SGF^{w'}_s(y,z) & \text{if } w = tw' \text{ with } t \notin \{s,b\}, \\ \end{cases} \] where \[ \SGF(y,z) = \frac{1+yz-\sqrt{1-4y-2yz+y^2z^2}}{2(z+1)} \] is the Schr\"oder generating function (see Proposition~\ref{prop:CatalanSchroderGF}). \end{itemize} \end{prop} \begin{proof} According to Propositions~\ref{prop:cotreeDeletion} and~\ref{prop:faceLatticeConstrainahedron}, we need to count the $(m,n)$-cotrees of rank $p$. We group them according to their type, which can be any word $w$ on the alphabet $\{\ell,r,b\}$ with no two consecutive $\ell$ nor two consecutive $r$ and such that $1 \le |w|_\ell + |w|_b \le m$ and $1 \le |w|_r + |w|_b \le n$. We then need to construct the two trees $L$ and $R$ with compatible partitions of their nodes. If $w = \varepsilon$ is the empty word, then both $L$ and $R$ are empty trees with a single leaf. Otherwise, $w = tw'$ with $t \in \{\ell,r,b\}$, and we construct $L$ (resp. $R$) by considering a tree $L'$ (resp. $R'$) for $w'$~and \begin{itemize} \item if $t = \ell$ (resp. $t = r$), grafting at each leaf of $L'$ (resp. $R'$) a Schr\"oder tree (thus the substitution of the $y$ variable in $\SGF^{w'}_s$ by $\SGF(y,z)$), such that not all leaves of $L'$ (resp. $R'$) are replaced by an empty trees (thus the subtraction of $\SGF^{w'}_s$), \item if $t = b$, grafting at each leaf of $L'$ (resp. $R'$) either an empty tree or a tree with a single node (thus the substitution of the $y$ variable in $\SGF^{w'}_s$ by $\smash{\frac{y}{1-yz}}$), such that not all leaves of $L'$ (resp. $R'$) are replaced by an empty tree (thus the subtraction of $\SGF^{w'}_s$). \qedhere \end{itemize} \end{proof} For instance, the $f$-vectors of all constrainahedra $\Constrainahedron$ with $m + n \le 5$ are displayed in Figures~\ref{fig:multiplihedra2}, \ref{fig:multiplihedra3} and~\ref{fig:multiplihedra4} (all these constrainahedra are multiplihedra since ${\Perm[1] = \Asso[1]}$ and ${\Perm[2] = \Asso[2]}$). The $f$-vector of the $(3,3)$-constrainahedron $\Constrainahedron[3][3]$ is \[ f(\Constrainahedron[3][3]) = (1, 606, 1550, 1384, 498, 60, 1). \] \section{Biassociahedra}\label{sec:biassociahedra} In this section, we study the family of $(m,n)$-biassociahedra, obtained as the shuffle of an $m$-anti-associahedron $\Ossa[m]$ with an $n$-associahedron $\Asso[n]$. The combinatorics of the biassociahedron was already studied in~\cite{Markl,MerkulovWillwacher,SaneblidzeUmble-matrads}. We recall the combinatorial model of bitrees (Section~\ref{subsec:bitrees}), describe the face lattice, fan and oriented skeleton of the $(m,n)$-biassociahedron in terms of these bitrees (Section~\ref{subsec:biassociahedra}), provide explicit vertex and facet descriptions of the $(m,n)$-biassociahedron (Section~\ref{subsec:vertexFacetDescriptionsBiassociahedra}), and present enumerative results on the number of vertices, faces and facets of the $(m,n)$-biassociahedron (Section~\ref{subsec:numerologyBiassociahedra}). \subsection{Bitrees}\label{subsec:bitrees} We start by recalling the bitrees of~\cite{Markl}, illustrated in Figure~\ref{fig:bitrees}. Intuitively, a bitree is a pair of Schr\"oder trees, the first growing up and the second growing down, drawn side to side, together with the information of the relative positions of their nodes. Examples are illustrated in Figure~\ref{fig:bitrees}. We say that a tree is (growing) \emph{up} (resp.~ \emph{down}) when we see it as a poset oriented from its root to its leaves (resp.~from its leaves to its roots), and we draw it accordingly so that the orientation goes from bottom to top. \begin{defi}[\cite{Markl}]\label{def:bitree} A \emph{$(m,n)$-bitree} is a triple $\BT \eqdef (U, D, \mu)$, where $U$ is an up Schr\"oder $m$-tree, $D$ is a down Schr\"oder $n$-tree, and $\mu$ is an ordered partition of the nodes of $U$ and $D$~such~that \begin{itemize} \item the part of $\mu$ containing a node $\node{n}$ of $U$ (resp. $D$) distinct from the root is before (resp.~after) or equal to the part of $\mu$ containing the parent of $\node{n}$, \item no two consecutive parts of $\mu$ are both contained in $U$ or both contained in~$D$, \item there is no oriented path in $U$ (resp.~in $D$) joining two nodes in a part of $\mu$ which meets both $U$ and $D$. \end{itemize} We say that a part of $\mu$ is of type $u$, $d$ or $b$ when it contains nodes from $U$, $D$ or both $U$ and $D$, and we call \emph{type} of the bitree the word given by the sequence of types of the parts of $\mu$. We denote by $\f{BT}_{m,n}$ the set of $(m,n)$-bitrees. \end{defi} To represent a $(m,n)$-bitree $\BT \eqdef (U, D, \mu)$, we draw the two trees $U$ and $D$ side by side in opposite directions~($U$ grows up while $D$ grows down), and we mark the separations between the parts of $\mu$ by (red) horizontal lines. Note that $\mu$ is read from bottom to top. Examples are illustrated in Figure~\ref{fig:bitrees}. \begin{figure}[!h] \centerline{ \includegraphics[scale=.9]{bitree1} \hspace*{.5cm} \includegraphics[scale=.9]{bitree2} } \caption{A $(10,7)$-bitree of type $dubudbu$ (left), a binary $(8,6)$-bitree of type $dududu$ (right).}\label{fig:bitrees} \end{figure} We now define the bitree deletion poset. Definition~\ref{def:bitreeDeletion} provides a direct description in terms of bitrees, while Definition~\ref{def:bitreePreposet} provides an alternative simpler but indirect description in terms of preposets. To illustrate the following definition, Figure~\ref{fig:bitreeDeletions} represents a sequence of deletions in $(6,5)$-bitrees. \begin{figure}[!hb] \centerline{ \begin{tabular}{c} \includegraphics[scale=.9]{bitree3} \\ $\big\downarrow$ {\scriptsize (i)(a)} \\[.2cm] \includegraphics[scale=.9]{bitree4} \\ $\big\downarrow$ {\scriptsize (i)(b)} \\[.2cm] \includegraphics[scale=.9]{bitree5} \\ \end{tabular} \hspace{.1cm}\raisebox{-4.5cm}{$\xrightarrow{\text{ (i)(c) }}$}\hspace{.1cm} \begin{tabular}{c} \includegraphics[scale=.9]{bitree6} \\ $\big\uparrow$ {\scriptsize (iii)} \\[.2cm] \includegraphics[scale=.9]{bitree7} \\ $\big\uparrow$ {\scriptsize (ii)(b)} \\[.2cm] \includegraphics[scale=.9]{bitree8} \\ $\big\uparrow$ {\scriptsize (ii)(a)} \\[.2cm] \includegraphics[scale=.9]{bitree9} \\ \end{tabular} } \caption{Deletions in $(6,5)$-bitrees.}\label{fig:bitreeDeletions} \end{figure} \begin{defi}\label{def:bitreeDeletion} Let $\BT \eqdef (U, D, \mu)$ and $\BT' \eqdef (U', D', \mu')$ be two $(m,n)$-bitrees. We say that $\BT'$ is obtained by a \emph{deletion} in $\BT$ in either of the following three cases: \begin{enumerate}\romanenumi \item\label{defi5.2.1} \textbf{Node deletion:} $U'$ (resp. $D'$) is obtained by deleting a node $\node{n}$ with parent $\node{p}$ in $U$ (resp. $D$) in the following situations: \begin{enumerate}\alphenumi \item \label{defi5.2.1.a}$\node{n}$ and $\node{p}$ belong to the same part of $\mu$, then $\mu'$ is obtained by deleting $\node{n}$ from $\mu$, \item\label{defi5.2.1.b} the part of $\node{n}$ is of type $u$ (resp. $d$), the part of $\node{p}$ is of type $b$, and the parts of $\node{n}$ and $\node{p}$ are consecutive, then $\mu'$ is obtained by deleting $\node{n}$ from~$\mu$, \item\label{defi5.2.1.c} the part of $\node{n}$ is of type $b$, the part of $\node{p}$ is of type $u$ (resp. $d$), and the parts of $\node{n}$ and $\node{p}$ are consecutive, then $\mu'$ is obtained from $\mu$ by moving $\node{p}$ to the part of $\node{n}$ and deleting $\node{n}$. \end{enumerate} \item\label{defi5.2.2} \textbf{Nodes move:} $U' = U$, $D' = D$, and $\mu'$ is obtained from $\mu$ by \begin{enumerate}\alphenumi \item\label{defi5.2.2.a} either creating, in between two consecutive parts $\mu_i$ of type $u$ (resp. $d$) and $\mu_{i+1}$ of type $d$ (resp. $u$), a new part containing a node of $\mu_i$ whose children (resp.~parent) are not in $\mu_i$ and a node of $\mu_{i+1}$ whose children (resp.~parent) are not in $\mu_{i+1}$ (and removing these nodes from their original parts in $\mu$), \item\label{defi5.2.2.b} or moving a node $\node{n}$ of $U$ from its part $\mu_i$ to the previous (or next) part~$\mu_{i \pm 1}$ in $\mu$, provided that the part $\mu_i$ is of type $u$, that the part $\mu_{i \pm 1}$ is of type $b$, and that the parent (or children) of $\node{n}$ does not belong to $\mu_i \cup \mu_{i \pm 1}$ (and same for $D$ exchanging $u$/$d$, previous/next and parent/children), \end{enumerate} \item\label{defi5.2.3} \textbf{Twin parts merge:} $\mu'$ is obtained by merging two consecutive parts of $\mu$ of type $b$, and $U'$ (resp. $D'$) is obtained by deleting any node $\node{n}$ in $U$ (resp. $D$) such that both $\node{n}$ and its parent belong to these parts. \end{enumerate} \end{defi} \begin{prop}\label{prop:bitreeDeletion} For all integers $m, n \ge 0$, the set $\f{BT}_{m,n}$ is stable by deletion, and the deletion graph is the Hasse diagram of a poset ranked by \[ \rank(U, D, \mu) = m + n - |U| - |D| + \beta(\mu), \] where $\beta(\mu)$ is the sum of $|\mu_i|-1$ over all parts $\mu_i$ of $\mu$ with $\mu_i \cap U \ne \varnothing \ne \mu_i \cap D$. In particular a $(m,n)$-bitree $\BT \eqdef (U, D, \mu)$ has \begin{itemize} \item rank $0$ if and only if both $U$ and $D$ are binary trees, and no part of $\mu$ meets both $U$ and $D$, \item rank $m+n-2$ if and only if $\mu$ has two parts, and each part of $\mu$ either meets both $U$ and $D$ or contains a single node, \item rank $m+n-1$ if and only if $\mu$ has a single part (hence, both $U$ and $D$ have a single node). \end{itemize} \end{prop} \begin{proof} Consider a deletion transforming ${\BT \eqdef (U, D, \mu)}$ to ${\BT' \eqdef (L', R', \mu')}$.\linebreak Then~$\BT'$ is clearly a $(m,n)$-bitree since $U'$ and $D'$ are still Schr\"oder trees, and the partition~$\mu'$ fulfills the conditions of Definition~\ref{def:bitree}. For the rank, we distinguish three cases corresponding to that of Definition~\ref{def:bitreeDeletion}: \begin{itemize} \item[\eqref{defi5.2.1}] \textbf{Node deletion:} $|U'| + |D'| = |U| + |D| - 1$ while $\beta(\mu') = \beta(\mu')$. \item[\eqref{defi5.2.2}] \textbf{Nodes move:} $|U'| = |U|$, $|D'| = |D|$, while $\beta(\mu') = \beta(\mu) + 1$. \item[\eqref{defi5.2.3}] \textbf{Twin parts merge:} if $\delta$ denotes the number of nodes $\node{n}$ of $U$ and $D$ such that both $\node{n}$ and its parent belong to the merged parts of $\mu$, then $|U'| + |D'| = |U| + |D| - \delta$ and $\beta(\mu') = \beta(\mu) - \delta + 1$. \end{itemize} In all three situations, we get $\rank(\BT') = \rank(\BT)+1$. The end of the statement immediately follows. \end{proof} \begin{defi}\label{def:bitreeDeletionPoset} The \emph{$(m,n)$-bitree deletion poset} is the poset on $\f{BT}_{m,n}$ where a $(m,n)$-bitree is covered by all $(m,n)$-bitrees that can be obtained by a deletion. \end{defi} The $(m,n)$-bitree deletion poset can alternatively be defined using preposets. \begin{defi}\label{def:bitreePreposet} A $(m,n)$-bitree $\BT \eqdef (U, D, \mu)$ defines a preposet $\preccurlyeq_{\BT}$ on $[m+n]$ that can be read as follows. Label $U$ by $[m]$ in inorder and $D$ by $[n]^{+m}$ in inorder (shifted by $m$). Then, for any $i,j \in [m+n]$, we have $i \preccurlyeq_{\BT} j$ if the part of $\mu$ containing~$i$ is before the part of $\mu$ containing $j$, or if there is a (possibly empty) path from the node containing $i$ to the node containing $j$ in the tree $U$ oriented towards its leaves or in the tree $D$ oriented towards its root. \end{defi} \begin{prop}\label{prop:characterizationBitreePreposets} The preposets $\preccurlyeq_{\BT}$ for $\BT \in \f{BT}_{m,n}$ are precisely the preposets~$\preccurlyeq$ on $[m+n]$ in which any $1 \le i < k \le m+n$ are comparable (\ie $i \preccurlyeq k$ or~$i \succcurlyeq k$ or both) if and only if \begin{itemize} \item either $i \le m < k$, \item or $m < i$ (resp. $k \le m$) and at least one of the following holds: \begin{itemize} \item there exists no $i < j < k$ such that $i \prec j \succ k$ (resp. $i \succ j \prec k$), \item there exists $j \in [m]$ (resp. $j \in [n]^{+m}$) such that $i \preccurlyeq j \preccurlyeq k$ or $i \succcurlyeq j \succcurlyeq k$. \end{itemize} \end{itemize} \end{prop} \begin{proof} Any preposet $\preccurlyeq_{\BT}$ clearly satisfies these conditions. Conversely, given a preposet $\preccurlyeq$ on ${[m+n]}$ satisfying these conditions, consider \begin{itemize} \item the preposet $\preccurlyeq_u$ on $[m]$ defined by $i \preccurlyeq_u k$ if and only if $i \preccurlyeq k$ and there is no~$i < j < k$ such that $i \succ j \prec k$, \item the preposet $\preccurlyeq_d$ on $[n]$ defined by $i \preccurlyeq_d k$ if and only if ${i + m \preccurlyeq k+m}$ and there is no ${i < j < k}$ such that $i + m \prec j + m \succ k + m$. \end{itemize} The preposet $\preccurlyeq_u$ (resp. $\preccurlyeq_d$) is clearly the preposet $\preccurlyeq_U$ (resp. $\preccurlyeq_D$) of an up Schr\"oder $m$-tree $U$ (resp.~a down Schr\"oder $n$-tree $D$). We then obtain the partition $\mu$ by considering the relations $i \preccurlyeq k$ with $i \le m < k$. Details are left to the reader. \end{proof} \begin{prop}\label{prop:bitreeDeletionPosetOnPreposets} In the bitree deletion poset, $\BT$ is smaller than $\BT'$ if and only if $\preccurlyeq_{\BT}$ refines $\preccurlyeq_{\BT'}$. \end{prop} \begin{proof} An immediate case analysis shows that deletions in a bitree $\BT$ defined in Definition~\ref{def:bitreeDeletion} precisely translate all possible refinements in the corresponding preposet $\preccurlyeq_{\BT}$. \end{proof} Finally, we define the rotations in bitrees, which correspond to rank $1$ bitrees. To illustrate the following definition, Figure~\ref{fig:bitreeRotations} represents a sequence of right rotations in binary $(3,2)$-bitrees. \begin{figure} \centerline{ \includegraphics[scale=.9]{bitree10} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (i) }}$}\hspace{.1cm} \includegraphics[scale=.9]{bitree11} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \raisebox{-.3cm}{\includegraphics[scale=.9]{bitree12}} \hspace{.1cm}\raisebox{1cm}{$\xrightarrow{\text{ (ii) }}$}\hspace{.1cm} \raisebox{.15cm}{\includegraphics[scale=.9]{bitree13}} } \caption{Right rotations in binary $(3,2)$-bitrees.}\label{fig:bitreeRotations} \end{figure} \begin{defi}\label{def:rotationsBitrees} We call \emph{binary $(m,n)$-bitrees} the rank $0$ $(m,n)$-bitrees, \ie \linebreak where both $U$ and $D$ are binary trees, and no part of $\mu$ meets both $U$ and $D$. We say that two binary $(m,n)$-bitrees $\BT \eqdef (U, D, \mu)$ and $\BT' \eqdef (U', D', \mu')$ are connected by a \emph{right rotation} if: \begin{enumerate}\romanenumi \item\label{defi5.8.1} \textbf{Edge rotation:} $U'$ (resp. $D'$) is obtained from $U$ (resp. $D$) by the right rotation of an edge whose endpoints belong to the same part of $\mu$, \item\label{defi5.8.2} \textbf{Twin parts:} $U' = U$, $D' = D$, and $\mu'$ is obtained from $\mu$ by creating, in between two consecutive parts $\mu_i$ of type $u$ and $\mu_{i+1}$ of type $d$, first a new part containing a node of $\mu_{i+1}$ whose children are not in $\mu_{i+1}$, and second a new part containing a node of $\mu_i$ whose children are not in $\mu_i$ (and removing these nodes from their original parts in $\mu$, and merging consecutive parts of the same type $u$ or $d$ if any). \end{enumerate} \end{defi} \begin{rema}\label{rem:algebraicInterpretationBiassociahedra} The algebraic interpretation of the binary $(m,n)$-bitrees involves both a magmatic product $\ast$ and a magmatic coproduct $\Delta$ on a set $X$. The nodes in the left part of a bitree are associated with the coproduct $\Delta$, while the nodes in the right part are associated with the product $\ast$. One starts at the bottom with a $1 \times (n+1)$-matrix of elements of $X$ (with $1$ column and $n+1$ rows). Intermediate steps will go through rectangular $p \times q$-matrices of elements of $X$ with increasing~$1 \leq p \leq m+1$ and decreasing $1 \leq q \leq n+1$, until one reaches a $(m+1) \times 1$-matrix of elements of~$X$ at the top. Going up through a node in the left part of the bitree means applying $\Delta$ to each element in a column of the matrix, replacing this column by two columns and increasing $p$ by $1$. Similarly, going up through a node in the right part of the bitree means applying $\ast$ to corresponding elements in two consecutive rows of the matrix, replacing these two rows by a single row and decreasing $q$ by~$1$. In short, a left node stands for $\Delta$ duplicating a column, and a right node for $\ast$ merging two consecutive rows. \end{rema} \subsection{Anti-associahedra \texorpdfstring{$\shuffleDP$}{shuffleDP} Associahedra}\label{subsec:biassociahedra} We now consider shuffles of anti-associahedra with asso\-ciahedra. We call \emph{anti-associahedron} the polytope $\Ossa \eqdef (n+1) \, \one - \Asso$. It has the same combinatorics (but a different embedding) as the associahedron $\Asso$. \begin{defi}\label{def:biassociahedron} The \emph{$(m,n)$-biassociahedron} is the polytope \[ \Biassociahedron = \Ossa[m] \shuffleDP \Asso[n]. \] \end{defi} Note that since $\Perm[1] = \Asso[1]$ and $\Perm[2] = \Asso[2]$, the first $(m,n)$-biassociahedron which is neither an associahedron, nor a $(m,n)$-multiplihedron, is the $(3,3)$-biassociahedron $\Biassociahedron[3][3]$, which is a $5$-dimensional polytope. There is thus no reasonable example to be drawn in this section. \begin{prop}\label{prop:faceLatticeBiassociahedron} The face lattice of the $(m,n)$-biassociahedron $\Biassociahedron$ is isomorphic to the $(m,n)$-bitree deletion poset (augmented with a minimal element). \end{prop} \begin{proof} This follows from Proposition~\ref{prop:shuffleFacePreposets} (see also Remark~\ref{rem:biPreposets}), since $(m,n)$-bitrees are just a specialization of bipreposets. \end{proof} \begin{rema}\label{rem:simpleBiassociahedron} In contrast to the associahedron $\Asso$, the biassociahedron $\Biassociahedron$ is simple if and only if $m = 0$, or $n = 0$, or $\max(m,n) \le 2$. \end{rema} \begin{prop}\label{prop:fanBiassociahedron} The normal fan of the $(m,n)$-biassociahedron $\Biassociahedron$ is the fan containing one cone $\polytope{C}(\BT) \eqdef \{\b{x} \in \R^{m+n}\,|\,x_i \le x_j \text{ if } i \preccurlyeq_{\BT} j\}$ for each ${\BT \in \f{BT}_{m,n}}$. \end{prop} \begin{proof} Immediate from Proposition~\ref{prop:faceLatticeBiassociahedron} and Definition~\ref{def:bitreePreposet}. \end{proof} \begin{prop}\label{prop:graphBiassociahedron} When oriented in the direction \[ {\b{\omega} \eqdef (n,\,\dots,\,1) - (1,\,\dots,\,n) = \sum_{i\,\in\,[n]} (n+1-2i) \, \b{e}_i}, \] the graph of the $(m,n)$-biassociahedron $\Biassociahedron$ is isomorphic to the right rotation graph on binary $(m,n)$-bitrees. \end{prop} \begin{proof} It follows from Proposition~\ref{prop:faceLatticeBiassociahedron} that the vertices of $\Biassociahedron$ correspond to the binary $(m,n)$-bitrees. It is easy to check that the edges of $\Biassociahedron$ oriented by $\b{\omega}$ correspond to right rotations on binary $(m,n)$-bitrees. \end{proof} \begin{rema}\label{rem:noBiTamari} In contrast to Proposition~\ref{prop:graphMultiplihedron}, note that the right rotation graph on binary $(m,n)$-bitrees is not the Hasse diagram of a lattice when $m \ge 3$ and $n \ge 3$. See Figure~\ref{fig:biassociahedronNotLattice} for examples of a pair of binary $(3,3)$-bitrees with no join and a pair of binary $(3,3)$-bitrees with no meet. \end{rema} \begin{figure} \centerline{ \begin{tikzpicture}[yscale=1.2] \node[label=west:{$\BT_1 =$}] (a) at (-4,4.3) {\includegraphics[scale=.9]{bitree14}}; \node[label=east:{$= \BT_2$}] (b) at (4,4.3) {\includegraphics[scale=.9]{bitree15}}; \node (c) at (-6,0) {\includegraphics[scale=.9]{bitree16}}; \node (d) at (2,0) {\includegraphics[scale=.9]{bitree17}}; \node (e) at (-2,0) {\includegraphics[scale=.9]{bitree18}}; \node (f) at (6,0) {\includegraphics[scale=.9]{bitree19}}; \node[label=west:{$\BT[S]_1 =$}] (g) at (-4,-4.6) {\includegraphics[scale=.9]{bitree20}}; \node[label=east:{$= \BT[S]_2$}] (h) at (4,-4.6) {\includegraphics[scale=.9]{bitree21}}; \draw[thick,gray] (a.south) -- (c.north); \draw[thick,gray] (a.south) -- (e.north); \draw[thick,gray] (b.south) -- (d.north); \draw[thick,gray] (b.south) -- (f.north); \draw[thick,gray] (c.south) -- (g.north); \draw[thick,gray] (d.south) -- (g.north); \draw[thick,gray] (e.south) -- (h.north); \draw[thick,gray] (f.south) -- (h.north); \end{tikzpicture} } \caption{Rotations on all $(3,3)$-bitrees larger than $\BT[S]_1$ or $\BT[S]_2$ and smaller than~$\BT_1$ or $\BT_2$. This shows that $\BT[S]_1$ and $\BT[S]_2$ have no join, and $\BT_1$ and $\BT_2$ have no meet, so that the rotation graph on binary $(3,3)$-bitrees does not define a lattice.}\label{fig:biassociahedronNotLattice} \end{figure} \subsection{Vertex and facet descriptions}\label{subsec:vertexFacetDescriptionsBiassociahedra} Our next two statements, illustrated in Figures~\ref{fig:coordinatesBitrees} and~\ref{fig:inequalitiesBitrees}, provide the vertex and facet descriptions of the $(m,n)$-biasso\-ciahedron $\Biassociahedron$. The proofs are elementary computations from Definitions~\ref{def:associahedron}, \ref{def:graphicalZonotope} and~\ref{def:biassociahedron}. \begin{prop}\label{prop:verticesBiassociahedron} For any $i \in [m+n]$, the $i^{\rm th}$coordinate of the vertex of the $(m,n)$-biassociahedron $\Biassociahedron$ corresponding to a binary $(m,n)$-bitree $(U, D, \mu)$ is given by \begin{itemize} \item if $i \le m$, then $m+1$ minus the product of the numbers of leaves in the left and right subtrees of $\node{n}$, plus the number of nodes of $D$ below $\node{n}$, where $\node{n}$ is the node of $U$ labeled by $i$ in inorder. \item if $i \ge m+1$, the product of the numbers of leaves in the left and right subtrees of $\node{n}$, plus the number of nodes of $U$ below $\node{n}$, where $\node{n}$ is the node of $D$ labeled by $i-m$ in inorder. \end{itemize} In particular, the sum of the coordinates is always $(\begin{smallmatrix} m+1\\2\end{smallmatrix}) + (\begin{smallmatrix} n+1\\2\end{smallmatrix}) + mn = (\begin{smallmatrix} m+n+1\\2\end{smallmatrix})$. \end{prop} \begin{prop}\label{prop:facetsBiassociahedron} Let $\BT \eqdef (U, D, \mu)$ be a $(m,n)$-bitree of rank $m+n-2$. Let~${A \eqdef A_1 \cup \dots \cup A_k}$ where $A_1, \dots A_k$ are the inorder labels of the nodes of $U$ located in the top part $\mu_2$, and let ${B \eqdef B_1 \cup \dots \cup B_\ell}$ where $B_1, \dots, B_\ell$ are the inorder labels shifted by $m$ of the nodes of $D$ located in the bottom part $\mu_1$. Then the facet of the $(m,n)$-biassociahedron $\Biassociahedron$ corresponding to $\BT$ is defined by the inequality \[ \dotprod{\b{x}}{\one_{([m] \ssm A) \cup B}} \ge \textstyle{\binom{m+1}{2}} - |A| \cdot (m+1) + \sum\limits_{i \,\in\,[k]} \textstyle{\binom{|A_i|+1}{2}} + (m-|A|) \cdot |B| + \sum\limits_{j\,\in\,[\ell]} \textstyle{\binom{|B_j|+1}{2}}. \] Moreover, this inequality is a facet defining inequality of the permutahedron \linebreak $\Perm[m+n]$ if and only if $k \le 1$ and $\ell \le 1$, \ie if both $U$ and $D$ have at most two nodes. \end{prop} Note that, in contrast to Propositions~\ref{prop:MinkowskiMultiplihedron} and~\ref{prop:MinkowskiConstrainahedron}, we do not provide an expression of the $(m,n)$-biassociahedron $\Biassociahedron$ as a signed Minkowski sum of faces of the standard simplex $\simplex_{[m+n]}$. Such an expression is possible (since $\Biassociahedron$ is a deformed permutahedron by Proposition~\ref{prop:shuffleDeformedPermutahedra}), but combinatorially less attractive than that of $\Multiplihedron$ or $\Constrainahedron$ (as it requires to express the faces of the opposite standard simplex as signed Minkowski sums of faces of the standard simplex). See~\cite{Lange} for further discussion. \begin{exam} Figure~\ref{fig:coordinatesBitrees} illustrates some vertex coordinates of $\Biassociahedron[3][3]$ computed by Proposition~\ref{prop:verticesBiassociahedron} and Figure~\ref{fig:inequalitiesBitrees} illustrates some facet inequalities of $\Biassociahedron[3][3]$ computed by Proposition~\ref{prop:facetsBiassociahedron}. Note that all vertices of $\Biassociahedron[3][3]$ have coordinate sum $21$. Note that for any pair $(i, j) \in \{(1, 2), (1, 3), (2, 2), (2, 3), (2, 4),$ $(3, 2), (3, 3), (3, 4), (4, 3), (4, 4)\}$, we have $\BT_i$ smaller than $\BT[S]_j$ in deletion order, so that the vertex corresponding to $\BT_i$ is contained in the facet corresponding to $\BT[S]_j$. \begin{figure} \centerline{ \begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c} $\BT_1$ & $\BT_2$ & $\BT_3$ & $\BT_4$ \\[.2cm] \includegraphics[scale=.9]{bitree22} & \includegraphics[scale=.9]{bitree23} & \includegraphics[scale=.9]{bitree24} & \includegraphics[scale=.9]{bitree25} \\[.1cm] $(6, 2, 1, 3, 6, 3)$ & $(6, 0, 3, 3, 6, 3)$ & $(6, 0, 5, 2, 6, 2)$ & $(6, 0, 6, 2, 5, 2)$ \end{tabular} } \caption{Vertices of $\Biassociahedron[3][3]$ corresponding to four binary $(3,3)$-bitrees.}\label{fig:coordinatesBitrees} \end{figure} \begin{figure} \centerline{ \begin{tabular}{c@{\qquad}c@{\qquad}c@{\qquad}c} $\BT[S]_1$ & $\BT[S]_2$ & $\BT[S]_3$ & $\BT[S]_4$ \\[.2cm] \includegraphics[scale=.9]{bitree26} & \includegraphics[scale=.9]{bitree27} & \includegraphics[scale=.9]{bitree28} & \includegraphics[scale=.9]{bitree29} \\[.1cm] $x_1 + x_2 + x_3 \ge 6$ & $x_2 + x_3 + x_4$ & $x_2 + x_3 + x_4$ & $x_2 \ge 0$ \\ & $+ x_6 \ge 9$ & $+ x_5 + x_6 \ge 15$ & \end{tabular} } \caption{Facet defining inequalities of $\Biassociahedron[3][3]$ corresponding to four rank $4$ $(3,3)$-bitrees.}\label{fig:inequalitiesBitrees} \end{figure} \end{exam} \subsection{Numerology}\label{subsec:numerologyBiassociahedra} We now present enumerative results on the number of vertices, faces and facets of the $(m,n)$-biassociahedron $\Biassociahedron$. The first few values of these numbers are collected in Tables~\ref{table:verticesConstrainahedraBiassociahedra}, \ref{table:facetsConstrainahedraBiassociahedra} and~\ref{table:facesBiassociahedra} in Section~\ref{subsec:tablesConstrainahedraBiassociahedra}. We start with vertices. See~Table~\ref{table:verticesConstrainahedraBiassociahedra}. \begin{prop}\label{prop:numberVerticesBiassociahedra} The number of vertices of the $(m,n)$-biassociahedron \linebreak $\Biassociahedron$ (equivalently of binary $(m,n)$-bitrees) is given by \[ \left[x^{m+1} \, y^{n+1}\right] \, \sum_{i = 0}^{\min(m,n)} 2 \, \tCGF^{(i)}(x) \, \tCGF^{(i)}(y) + \tCGF^{(i)}(x) \, \tCGF^{(i+1)}(y) + \tCGF^{(i+1)}(x) \, \tCGF^{(i)}(y), \] where $\tCGF^{(i)}(x)$ is defined for $i \ge 0$ by \[ \tCGF^{(0)}(x) = x \qquad\text{and}\qquad \tCGF^{(i)}(x) = \tCGF^{(i-1)}(\CGF(x)) - \tCGF^{(i-1)}(x), \] where \[ \CGF(x) = \frac{1-\sqrt{1-4x}}{2} \] is the Catalan generating function (see Proposition~\ref{prop:CatalanSchroderGF}). \end{prop} \begin{proof} According to Propositions~\ref{prop:bitreeDeletion} and~\ref{prop:faceLatticeBiassociahedron}, we need to count the binary $(m,n)$-bitrees. We group them according to their type, which can be of the form $(ud)^i\!$, $(du)^i$, $(ud)^iu$ or $(du)^id$. We then need to construct the two binary trees $U$ and~$D$ with compatible partitions of their nodes into $i$ (or $i+1$) parts. We construct a partitioned binary tree with $i+1$ parts by \begin{itemize} \item choosing a binary tree $T$ for the first part (thus the apparition of $\CGF$), \item grafting at each leaf of $T$ a partitioned binary tree with $i-1$ parts (thus the substitution of the $y$ variable in $\tCGF^{(i)}$), such that not all leaves of $T$ are replaced by an empty binary tree (thus the subtraction of $\tCGF^{(i-1)}$ in the definition of~$\tCGF^{(i)}$). \qedhere \end{itemize} \end{proof} We now consider the number of facets of the $(m,n)$-biassociahedron $\Biassociahedron$. See~Table~\ref{table:facetsConstrainahedraBiassociahedra}. \begin{prop}\label{prop:numberFacetsBiassociahedra} The number of facets of the $(m,n)$-biassociahedron \linebreak $\Biassociahedron$ is \[ \textstyle{ (2^m-1)(2^n-1) + \binom{m+1}{2} + \binom{n+1}{2} - 1.} \] \end{prop} \begin{proof} According to Propositions~\ref{prop:bitreeDeletion} and~\ref{prop:faceLatticeBiassociahedron}, the possible types for the \linebreak $(m,n)$-bitrees corresponding to facets of the $(m,n)$-biassociahedron $\Biassociahedron$ are: \begin{itemize} \item type $ud$ (resp.~type $du$): then both $U$ and $D$ have a single node, thus a single choice, \item type $bu$ (resp.~type $db$): then $U$ (resp. $D$) is a non-trivial corolla while $D$ (resp.~$U$) has a single node, thus $(\begin{smallmatrix}m+1\\2\end{smallmatrix})-1$ choices (resp. $(\begin{smallmatrix}n+1\\2\end{smallmatrix})-1$ choices), \item type $ub$ (resp.~type $bd$): then $U$ (resp. $D$) is any Schr\"oder tree of height $2$ while $D$ (resp. $U$) has a single node, thus $2^m-2$ choices (resp. $2^n-2$ choices), \item type $bb$: then both $U$ and $D$ are Schr\"oder trees of height $2$, thus $(2^m-2)(2^n-2)$ choices. \qedhere \end{itemize} \end{proof} Finally, adapting the approach of Proposition~\ref{prop:numberVerticesBiassociahedra}, we can count all faces of the $(m,n)$-biassocia\-hedron $\Biassociahedron$ according to their dimension. \begin{prop}\label{prop:numberFacesBiassociahedra} Let $BT(m,n,p)$ denote the number of $p$-dimensional faces of the $(m,n)$-biassocia\-hedron $\Biassociahedron$, or equivalently the number of $(m,n)$-bitrees of rank $p$. Then the generating function \begin{align*} \BTGF(x,y,z) &\eqdef \sum_{m,n,p} BT(m,n,p) \, x^m \, y^n \, z^p \\ \intertext{is given by} \BTGF(x,y,z) &= \sum_w \SGF^{\rev(w)}_u(x,z) \, \SGF^w_d(y,z) \end{align*} where \begin{itemize} \item $w$ runs over all words on the alphabet $\{u,d,b\}$ with no two consecutive $u$ nor two consecutive $d$ and such that $1 \le |w|_u + |w|_b \le m$ and $1 \le |w|_d + |w|_b \le n$, \item $\rev(w) \eqdef w_k \dots w_1$ denotes the reverse of the word $w = w_1 \dots w_k$, \item for a letter $s \in \{u,d\}$, the generating function $\SGF^w_s(y,z)$ is defined by\linebreak $\SGF^\varepsilon_s(y,z) \eqdef y$ and \[ \SGF^{w}_s(y,z) \eqdef \begin{cases} \SGF^{w'}_s(\SGF(y,z), z) - \SGF^{w'}_s(y,z) & \text{if } w = sw', \\ \SGF^{w'}_s \left(\frac{y}{1-yz}, z \right) - \SGF^{w'}_s(y,z) & \text{if } w = bw', \\ \SGF^{w'}_s(y,z) & \text{if } w = tw' \text{ with } t \notin \{s,b\}, \\ \end{cases} \] where \[ \SGF(y,z) = \frac{1+yz-\sqrt{1-4y-2yz+y^2z^2}}{2(z+1)} \] is the Schr\"oder generating function (see Proposition~\ref{prop:CatalanSchroderGF}). \end{itemize} \end{prop} \begin{proof} According to Propositions~\ref{prop:bitreeDeletion} and~\ref{prop:faceLatticeBiassociahedron}, we need to count the $(m,n)$-bitrees of rank $p$. We group them according to their type, which can be any word $w$ on the alphabet $\{u,d,b\}$ with no two consecutive $u$ nor two consecutive $d$ and such that $1 \le |w|_u + |w|_b \le m$ and $1 \le |w|_d + |w|_b \le n$. We then need to construct the two trees $U$ and $D$ with compatible partitions of their nodes. If $w = \varepsilon$ is the empty word, then both $U$ and $D$ are empty trees with a single leaf. Otherwise, $w = tw'$ with $t \in \{u,d,b\}$, and we construct $U$ (resp. $D$) by considering a tree $U'$ (resp. $D'$) for $w'$~and \begin{itemize} \item if $t = u$ (resp. $t = d$), grafting at each leaf of $U'$ (resp. $D'$) a Schr\"oder tree (thus the substitution of the $y$ variable in $\SGF^{w'}_s$ by $\SGF(y,z)$), such that not all leaves of $U'$ (resp. $D'$) are replaced by an empty trees (thus the subtraction of $\SGF^{w'}_s$), \item if $t = b$, grafting at each leaf of $U'$ (resp. $D'$) either an empty tree or a tree with a single node (thus the substitution of the $y$ variable in $\SGF^{w'}_s$ by $\smash{\frac{y}{1-yz}}$), such that not all leaves of $U'$ (resp. $D'$) are replaced by an empty tree (thus the subtraction of $\SGF^{w'}_s$). \qedhere \end{itemize} \end{proof} For instance, the $f$-vectors of all biassociahedra $\Biassociahedron$ with $m + n \le 5$ are displayed in Figures~\ref{fig:multiplihedra2}, \ref{fig:multiplihedra3} and~\ref{fig:multiplihedra4} (all these biassociahedra are multiplihedra since ${\Perm[1] = \Asso[1]}$ and ${\Perm[2] = \Asso[2]}$). The $f$-vector of the $(3,3)$-biassociahedron $\Biassociahedron[3][3]$ is \[ f(\Biassociahedron[3][3]) = (1, 606, 1549, 1382, 497, 60, 1). \] Note that it slightly differs from the $f$-vector of the $(3,3)$-constrainahedron\newline $\Constrainahedron[3][3]$ which is \[ f(\Constrainahedron[3][3]) = (1, 606, 1550, 1384, 498, 60, 1), \] given in Section~\ref{subsec:numerologyConstrainahedra}. \section*{Acknowledgements}\label{sec:acknowledgments} We are deeply grateful to Spencer Backman, Nathaniel Bottman and Daria Poliakova for pointing us to the constrainahedra~\cite{BottmanPoliakova,Poliakova} and asking for their connection to the biassociahedra of~\cite{Markl}. As explained in Sections~\ref{sec:constrainahedra} and~\ref{sec:biassociahedra}, the former are shuffles of associahedra with associahedra while the latter are shuffles of anti-associahedra with associahedra. This motivated us to include both in the present version (while the former was previously omitted due to our lack of \mbox{algebraic motivation}). We also thank two anonymous referees for corrections. \vspace*{30pt} \label{sec:biblio} \clearpage \pagebreak %\c\palearpage \appendix \section{Tables}\label{sec:tables} All references like~\OEIS{A000142} are entries of the Online Encyclopedia of Integer Sequences~\cite{OEIS}. \subsection{Zonotopes}\label{subsec:tablesZonotopes} \begin{table}[h] \caption{Number of vertices of $\Zono[K_m] \shuffleDP \Zono[P_n] = \Perm[m] \shuffleDP \Para[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & \OEIS{A000079} \\ 1 & 1 & 2 & 6 & 18 & 54 & 162 & 486 & 1458 & 4374 & & \OEIS{A025192} \\ 2 & 2 & 6 & 24 & 96 & 384 & 1536 & 6144 & 24576 & & & \OEIS{A002023} \\ 3 & 6 & 24 & 120 & 600 & 3000 & 15000 & 75000 & & & & \OEIS{A235702} \\ 4 & 24 & 120 & 720 & 4320 & 25920 & 155520 & & & & & ? \\ 5 & 120 & 720 & 5040 & 35280 & 246960 & & & & & & \\ 6 & 720 & 5040 & 40320 & 322560 & & & & & & & \\ 7 & 5040 & 40320 & 362880 & & & & & & & & \\ 8 & 40320 & 362880 & & & & & & & & & \\ 9 & 362880 & & & & & & & & & & \\ \hline & \OEIS{A000142} & \OEIS{A000142} & \OEIS{A000142} & \OEIS{A001563} & \OEIS{A002775} & \OEIS{A091363} & \OEIS{A091364} & ? & & & \end{tabular} } \vspace{.2cm} \label{table:verticesPermCube} \end{table} \begin{table}[h] \caption{Number of facets of $\Zono[K_m] \shuffleDP \Zono[P_n] = \Perm[m] \shuffleDP \Para[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & \OEIS{A000027} \\ 1 & 1 & 2 & 6 & 12 & 20 & 30 & 42 & 56 & 72 & & \OEIS{A002378} \\ 2 & 2 & 6 & 14 & 28 & 52 & 94 & 170 & 312 & & & \OEIS{A290699} \\ 3 & 6 & 14 & 30 & 60 & 116 & 222 & 426 & & & & \OEIS{A308580} \\ 4 & 14 & 30 & 62 & 124 & 244 & 478 & & & & & ? \\ 5 & 30 & 62 & 126 & 252 & 500 & & & & & & \\ 6 & 62 & 126 & 254 & 508 & & & & & & & \\ 7 & 126 & 254 & 510 & & & & & & & & \\ 8 & 254 & 510 & & & & & & & & & \\ 9 & 510 & & & & & & & & & & \\ \hline & \OEIS{A000918} & \OEIS{A000918} & \OEIS{A000918} & \OEIS{A028399} & \OEIS{A173034} & ? & & & & & \end{tabular} } \vspace{.2cm} \label{table:facetsPermCube} \end{table} \begin{table}[h] \caption{Number of vertices of $\Zono[K_m] \shuffleDP \Zono[E_n] = \Perm[m] \shuffleDP \Point[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \OEIS{A000012} \\ 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & & \OEIS{A000079} \\ 2 & 2 & 6 & 18 & 54 & 162 & 486 & 1458 & 4374 & & & \OEIS{A008776}, \OEIS{A025192} \\ 3 & 6 & 24 & 96 & 384 & 1536 & 6144 & 24576 & & & & \OEIS{A002023} \\ 4 & 24 & 120 & 600 & 3000 & 15000 & 75000 & & & & & \OEIS{A235702} \\ 5 & 120 & 720 & 4320 & 25920 & 155520 & & & & & & ? \\ 6 & 720 & 5040 & 35280 & 246960 & & & & & & & \\ 7 & 5040 & 40320 & 322560 & & & & & & & & \\ 8 & 40320 & 362880 & & & & & & & & \\ 9 & 362880 & & & & & & & & & & \\ \hline & \OEIS{A000142} & \OEIS{A000142} & \OEIS{A001563} & \OEIS{A002775} & \OEIS{A091363} & \OEIS{A091364} & ? & & & & \\ \end{tabular} } \vspace{.2cm} \label{table:verticesPermPoint} \end{table} \begin{table}[h] \caption{Number of facets of $\Zono[K_m] \shuffleDP \Zono[E_n] = \Perm[m] \shuffleDP \Point[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \OEIS{A000012} \\ 1 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & & \OEIS{A005843} \\ 2 & 2 & 6 & 12 & 22 & 40 & 74 & 140 & 270 & & & \OEIS{A131520} \\ 3 & 6 & 14 & 28 & 54 & 104 & 202 & 396 & & & & ? \\ 4 & 14 & 30 & 60 & 118 & 232 & 458 & & & & & \\ 5 & 30 & 62 & 124 & 246 & 488 & & & & & & \\ 6 & 62 & 126 & 252 & 502 & & & & & & & \\ 7 & 126 & 254 & 508 & & & & & & & & \\ 8 & 254 & 510 & & & & & & & & & \\ 9 & 510 & & & & & & & & & & \\ \hline & \OEIS{A000918} & \OEIS{A000918} & \OEIS{A028399} & \OEIS{A246168} & ? & & & & & & \\ \end{tabular} } \vspace{.2cm} \label{table:facetsPermPoint} \end{table} \begin{table}[h] \caption{Number of vertices of $\Zono[E_m] \shuffleDP \Zono[E_n] = \Point[m] \shuffleDP \Point[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \OEIS{A000012} \\ 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & & \OEIS{A000079} \\ 2 & 1 & 4 & 14 & 46 & 146 & 454 & 1394 & 4246 & & & \OEIS{A027649} \\ 3 & 1 & 8 & 46 & 230 & 1066 & 4718 & 20266 & & & & \OEIS{A027650} \\ 4 & 1 & 16 & 146 & 1066 & 6902 & 41506 & & & & & \OEIS{A027651} \\ 5 & 1 & 32 & 454 & 4718 & 41506 & & & & & & \OEIS{A283811} \\ 6 & 1 & 64 & 1394 & 20266 & & & & & & & \OEIS{A283812} \\ 7 & 1 & 128 & 4246 & & & & & & & & \OEIS{A283813} \\ 8 & 1 & 256 & & & & & & & & & \OEIS{A284032} \\ 9 & 1 & & & & & & & & & & \OEIS{A284033} \\ \hline & \OEIS{A000012} & \OEIS{A000079} & \OEIS{A027649} & \OEIS{A027650} & \OEIS{A027651} & \OEIS{A283811} & \OEIS{A283812} & \OEIS{A283813} & \OEIS{A284032} & \OEIS{A284033} & \\ \end{tabular} } \vspace{.2cm} \label{table:verticesPointPoint} \end{table} \begin{table}[h] \caption{Number of facets of $\Zono[E_m] \shuffleDP \Zono[E_n] = \Point[m] \shuffleDP \Point[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \OEIS{A000012} \\ 1 & 1 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & & \OEIS{A005843} \\ 2 & 2 & 4 & 12 & 22 & 40 & 74 & 140 & 270 & & & \OEIS{A131520} \\ 3 & 4 & 6 & 22 & 48 & 98 & 196 & 390 & & & & ? \\ 4 & 6 & 8 & 40 & 98 & 212 & 438 & & & & & \\ 5 & 8 & 10 & 74 & 196 & 438 & & & & & & \\ 6 & 10 & 12 & 140 & 390 & & & & & & & \\ 7 & 12 & 14 & 270 & & & & & & & & \\ 8 & 14 & 16 & & & & & & & & & \\ 9 & 16 & & & & & & & & & & \\ \hline & \OEIS{A005843} & \OEIS{A005843} & \OEIS{A131520} & ? & & & & & & & \\ \end{tabular} } \vspace{.2cm} \label{table:facetsPointPoint} \end{table} \vspace*{80pt} \pagebreak %\clearpage \subsection{Multiplihedra}\label{subsec:tablesMultiplihedra} \begin{table}[h] \caption{Number of vertices of the multiplihedra $\Multiplihedron \eqdef \Perm[m] \shuffleDP \Asso[n]$. See $\OEIS{A158825}$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & \OEIS{A000108} \\ 1 & 1 & 2 & 6 & 21 & 80 & 322 & 1348 & 5814 & 25674 & & \OEIS{A121988} \\ 2 & 2 & 6 & 24 & 108 & 520 & 2620 & 13648 & 72956 & & & $2 \cdot \OEIS{A158826}$ \\ 3 & 6 & 24 & 120 & 660 & 3840 & 23220 & 144504 & & & & ? \\ 4 & 24 & 120 & 720 & 4680 & 31920 & 225120 & & & & & \\ 5 & 120 & 720 & 5040 & 37800 & 295680 & & & & & & \\ 6 & 720 & 5040 & 40320 & 342720 & & & & & & & \\ 7 & 5040 & 40320 & 362880 & & & & & & & & \\ 8 & 40320 & 362880 & & & & & & & & & \\ 9 & 362880 & & & & & & & & & & \\ \hline & \OEIS{A000142} & \OEIS{A000142} & \OEIS{A000142} & \OEIS{A084253} & ? & & & & & & $m! \cdot \OEIS{A158825}$ \end{tabular} } \vspace{.2cm} \label{table:verticesMultiplihedra} \end{table} \begin{table}[h] \caption{Number of facets of the multiplihedra $\Multiplihedron \eqdef \Perm[m] \shuffleDP \Asso[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & \OEIS{A000096} \\ 1 & 1 & 2 & 6 & 13 & 25 & 46 & 84 & 155 & 291 & & \OEIS{A335439} \\ 2 & 2 & 6 & 14 & 29 & 57 & 110 & 212 & 411 & & & ? \\ 3 & 6 & 14 & 30 & 61 & 121 & 238 & 468 & & & & \\ 4 & 14 & 30 & 62 & 125 & 249 & 494 & & & & & \\ 5 & 30 & 62 & 126 & 253 & 505 & & & & & & \\ 6 & 62 & 126 & 254 & 509 & & & & & & & \\ 7 & 126 & 254 & 510 & & & & & & & & \\ 8 & 254 & 510 & & & & & & & & & \\ 9 & 510 & & & & & & & & & & \\ \hline & \OEIS{A000918} & \OEIS{A000918} & \OEIS{A000918} & \OEIS{A036563} & \OEIS{A048490} & ? & & & & & \end{tabular} } \vspace{.2cm} \label{table:facetsMultiplihedra} \end{table} \begin{table}[h] \caption{Total number of faces of the multiplihedra $\Multiplihedron \eqdef \Perm[m] \shuffleDP \Asso[n]$. The empty face is not counted, but the polytope itself is.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 3 & 11 & 45 & 197 & 903 & 4279 & 20793 & 103049 & \OEIS{A001003} \\ 1 & 1 & 3 & 13 & 67 & 381 & 2311 & 14681 & 96583 & 653049 & & ? \\ 2 & 3 & 13 & 75 & 497 & 3583 & 27393 & 218871 & 1810373 & & & \\ 3 & 13 & 75 & 541 & 4375 & 38073 & 349423 & 3341753 & & & & \\ 4 & 75 & 541 & 4683 & 44681 & 454855 & 4859697 & & & & & \\ 5 & 541 & 4683 & 47293 & 519847 & 6055401 & & & & & & \\ 6 & 4683 & 47293 & 545835 & 6790697 & & & & & & & \\ 7 & 47293 & 545835 & 7087261 & & & & & & & & \\ 8 & 545835 & 7087261 & & & & & & & & & \\ 9 & 7087261 & & & & & & & & & & \\ \hline & \OEIS{A000670} & \OEIS{A000670} & \OEIS{A000670} & ? & & & & & & & \end{tabular} } \vspace{.2cm} \label{table:facesMultiplihedra} \end{table} \pagebreak %\clearpage \subsection{Constrainahedra and biassociahedra}~\label{subsec:tablesConstrainahedraBiassociahedra} \begin{table}[h] \caption{Number of vertices of the constrainahedra $\Constrainahedron \eqdef \Asso[m] \shuffleDP \Asso[n]$ and of the biassociahedra $\Biassociahedron \eqdef \Ossa[m] \shuffleDP \Asso[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 2 & 5 & 14 & 42 & 132 & 429 & 1430 & 4862 & \OEIS{A000108} \\ 1 & 1 & 2 & 6 & 21 & 80 & 322 & 1348 & 5814 & 25674 & & \OEIS{A121988} \\ 2 & 2 & 6 & 24 & 108 & 520 & 2620 & 13648 & 72956 & & & $2\cdot$\OEIS{A158826} \\ 3 & 5 & 21 & 108 & 606 & 3580 & 21910 & 137680 & & & & ? \\ 4 & 14 & 80 & 520 & 3580 & 25520 & 186420 & & & & & \\ 5 & 42 & 322 & 2620 & 21910 & 186420 & & & & & & \\ 6 & 132 & 1348 & 13648 & 137680 & & & & & & & \\ 7 & 429 & 5814 & 72956 & & & & & & & & \\ 8 & 1430 & 25674 & & & & & & & & & \\ 9 & 4862 & & & & & & & & & & \\ \hline & \OEIS{A000108} & \OEIS{A121988} & $2\cdot$\OEIS{A158826} & ? & & & & & & & \end{tabular} } \vspace{.2cm} \vspace{-.3cm}\label{table:verticesConstrainahedraBiassociahedra} \end{table} \begin{table}[h] \caption{Number of facets of the constrainahedra $\Constrainahedron \eqdef \Asso[m] \shuffleDP \Asso[n]$ and of the biassociahedra $\Biassociahedron \eqdef \Ossa[m] \shuffleDP \Asso[n]$.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 0 & 2 & 5 & 9 & 14 & 20 & 27 & 35 & 44 & \OEIS{A000096} \\ 1 & 0 & 2 & 6 & 13 & 25 & 46 & 84 & 155 & 291 & & \OEIS{A335439} \\ 2 & 2 & 6 & 14 & 29 & 57 & 110 & 212 & 411 & & & ? \\ 3 & 5 & 13 & 29 & 60 & 120 & 237 & 467 & & & \\ 4 & 9 & 25 & 57 & 120 & 244 & 489 & & & & \\ 5 & 14 & 46 & 110 & 237 & 489 & & & & & \\ 6 & 20 & 84 & 212 & 467 & & & & & & \\ 7 & 27 & 155 & 411 & & & & & & & \\ 8 & 35 & 291 & & & & & & & & \\ 9 & 44 & & & & & & & & & \\ \hline & \OEIS{A000096} & \OEIS{A335439} & ? \end{tabular} } \vspace{.2cm} \vspace{-.3cm}\label{table:facetsConstrainahedraBiassociahedra} \end{table} \begin{table}[h] \caption{Total number of faces of the constrainahedra $\Constrainahedron \eqdef \Asso[m] \shuffleDP \Asso[n]$. The empty face is not counted, but the polytope itself is.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 3 & 11 & 45 & 197 & 903 & 4279 & 20793 & 103049 & \OEIS{A001003} \\ 1 & 1 & 3 & 13 & 67 & 381 & 2311 & 14681 & 96583 & 653049 & & ? \\ 2 & 3 & 13 & 75 & 497 & 3583 & 27393 & 218871 & 1810373 & & & \\ 3 & 11 & 67 & 497 & 4099 & 36205 & 336107 & 3243085 & & & & \\ 4 & 45 & 381 & 3583 & 36205 & 384819 & 4251605 & & & & & \\ 5 & 197 & 2311 & 27393 & 336107 & 4251605 & & & & & & \\ 6 & 903 & 14681 & 218871 & 3243085 & & & & & & & \\ 7 & 4279 & 96583 & 1810373 & & & & & & & & \\ 8 & 20793 & 653049 & & & & & & & & & \\ 9 & 103049 & & & & & & & & & & \\ \hline & \OEIS{A001003} & ? & & & & & & & & & \end{tabular} } \vspace{.2cm} \label{table:facesConstrainahedra} \end{table} %\clearpage \begin{table}[h] \caption{Total number of faces of the biassociahedra $\Biassociahedron \eqdef \Ossa[m] \shuffleDP \Asso[n]$. The empty face is not counted, but the polytope itself is.} \centerline{ \tiny \begin{tabular}{r|rrrrrrrrrr|l} $m \backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \\ \hline 0 &. & 1 & 3 & 11 & 45 & 197 & 903 & 4279 & 20793 & 103049 & \OEIS{A001003} \\ 1 & 1 & 3 & 13 & 67 & 381 & 2311 & 14681 & 96583 & 653049 & & ? \\ 2 & 3 & 13 & 75 & 497 & 3583 & 27393 & 218871 & 1810373 & & & \\ 3 & 11 & 67 & 497 & 4095 & 36137 & 335287 & 3234433 & & & & \\ 4 & 45 & 381 & 3583 & 36137 & 383375 & 4229985 & & & & & \\ 5 & 197 & 2311 & 27393 & 335287 & 4229985 & & & & & & \\ 6 & 903 & 14681 & 218871 & 3234433 & & & & & & & \\ 7 & 4279 & 96583 & 1810373 & & & & & & & & \\ 8 & 20793 & 653049 & & & & & & & & & \\ 9 & 103049 & & & & & & & & & & \\ \hline & \OEIS{A001003} & ? & & & & & & & & & \end{tabular} } \vspace{.2cm} \label{table:facesBiassociahedra} \end{table} \bibliography{20240702_chapoton} \end{document}