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

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

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

%% define your title in the usual way
\title{Hochschild polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@ub.edu}{vincent.pilaud@ub.edu}. Supported by the French ANR grant CHARMS (ANR-19-CE40-0017), by the French--Austrian projects PAGCAP (ANR-21-CE48-0020 \& FWF I 5788), and by the Spanish MICINN projects PID2019-106188GB-I00 and PID2022-137283NB-C21.}\addressmark{1}\addtocounter{footnote}{2}
	\and
	Daria Poliakova\thanks{\href{mailto:polydarya@gmail.com}{polydarya@gmail.com}. Supported by the Danish National Research Foundation grant~DNRF157.}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1} Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Spain \\ \addressmark{2} University of Southern Denmark, Odense, Denmark
}

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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{%
The $(m,n)$-multiplihedron is a polytope whose faces correspond to \mbox{$m$-pain}\-ted $n$-trees. %, and whose oriented skeleton is the Hasse diagram of the rotation lattice on binary $m$-painted $n$-trees.
Deleting certain inequalities from its facet description, we obtain the $(m,n)$-Hochschild polytope whose faces correspond to $m$-lighted $n$-shades. %, and whose oriented skeleton is the Hasse diagram of the rotation lattice on unary $m$-lighted \mbox{$n$-shades}.
Moreover, there is a natural shadow map from $m$-painted $n$-trees to $m$-lighted $n$-shades, which defines a meet semilattice morphism of rotation lattices.
In particular, when $m=1$, our Hochschild polytope is a deformed permutahedron realizing the Hochschild lattice.
}

%% put your French abstract here, or comment this out if you don't have one
\resume{%
Le $(m,n)$-multiplièdre est un polytope dont les faces correspondent aux \mbox{$n$-arbres} $m$-peints. %, et dont le squelette orienté est le diagramme de Hasse du treillis de rotation sur les $n$-arbres $m$-peints binaires.
En retirant certaines inégalités de sa description par facettes, nous obtenons le $(m,n)$-polytope de Hochschild dont les faces correspondent aux \mbox{$n$-ombres} $m$-illuminées. %, et dont le squelette orienté est le diagramme de Hasse du treillis de rotation sur les $n$-ombres $m$-illuminées unaires.
De plus, il existe une fonction d'ombre naturelle des $n$-arbres $m$-peints vers les $n$-ombres $m$-illuminées, qui définit un morphisme de semi-treillis supérieur entre les treillis de rotations correspondants.
En particulier, quand ${m = 1}$, notre polytope de Hochschild est un permutaèdre déformé qui réalise le treillis~de~Hochschild.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Multiplihedron, Freehedron, Hochschild lattice, Quotient}

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

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

% specific commands
\graphicspath{{figures/}}
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\left\langle \, #1 \; \middle| \; #2 \, \right\rangle} % dot product
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \; \big| \; #2 \, \big\rangle} % dot product
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures
% math letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\HH}{\mathbb{H}} % hyperplane
\newcommand{\one}{\b{1}} % the all one vector
\renewcommand{\b}[1]{{\boldsymbol{#1}}} % bold letters
% lattices
\newcommand{\meet}{\wedge} % meet
\newcommand{\join}{\vee} % join
\newcommand{\bigMeet}{\bigwedge} % meet
\newcommand{\bigJoin}{\bigvee} % join
% freehedra commands
\newcommandx{\PT}[1][1=T]{\mathbb{#1}} % painted tree
\newcommandx{\LS}[1][1=S]{\mathbb{#1}} % lighted shade
\DeclareMathOperator{\shadow}{Sh} % shadow
\newcommand{\polytope}[1]{\mathds{#1}} % font polytopes
\newcommandx{\Perm}[1][1=d]{\polytope{P}\mathrm{erm}(#1)} % permutahedron
\newcommandx{\Asso}[1][1=d]{\polytope{A}\mathrm{sso}(#1)} % associahedron
\newcommandx{\Multiplihedron}[2][1=m, 2=n]{\polytope{M}\mathrm{ul}(#1, #2)} % multiplihedron
\newcommandx{\HP}[2][1=m, 2=n]{\polytope{H}\mathrm{och}(#1, #2)} % Hochschild polytope
\newcommand{\simplex}{\b{\triangle}} % simplex
% marginal comments
\usepackage{todonotes}
\newcommand{\vincent}[1]{\todo[color=blue!30]{\rm #1 \\ \hfill --- V.}}
\newcommand{\daria}[1]{\todo[color=black!10!orange]{\rm #1 \\ \hfill --- D.}}

\begin{document}

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

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

\section*{Introduction}

We present a remake of the famous combinatorial, geometric, and algebraic interplay between permutations and binary trees.
In the original story, the central character is the surjective map from permutations to binary trees (given by successive binary search tree insertions~\cite{Tonks, HivertNovelliThibon-algebraBinarySearchTrees}).
This map enables us to construct the Tamari lattice~\cite{Tamari} as a lattice quotient of the weak order, the sylvester fan as a quotient fan of the braid fan, Loday's associahedron~\cite{Loday} as a removahedron of the permutahedron, and the Loday--Ronco Hopf algebra as a Hopf subalgebra of the Malvenuto--Reutenauer Hopf algebra.
Many variations of this saga have been further investigated, notably for other lattice quotients of the weak order and for generalized associahedra arizing from finite type cluster algebras.
See \cite{PilaudSantosZiegler} for a recent survey on this topic, in particular for a bibliography.

In the present remake, permutations are replaced by binary $m$-painted $n$-trees (binary trees on~$n$ nodes with $m$ horizontal labeled edge cuts), while binary trees are replaced by unary $m$-lighted $n$-shades (compositions of~$n$ with $m$ labels inside their gaps).
The precise definitions are delayed to \cref{sec:combinatorics}, but the reader can already glance at \cref{fig:multiplihedronFreehedronLabeledOriented13}  for~${m = 1}$ and~$n = 3$.
The $m$-painted $n$-trees already appeared in \cite[Sect.~3.1]{ChapotonPilaud}, inspired from the case $m = 1$ studied in~\cite{Stasheff-HSpaces, Forcey-multiplihedra, ArdilaDoker}.
They are mixtures (in the sense of~\cite{ChapotonPilaud}) between the permutations of~$[m]$ and the binary trees with~$n$ nodes.
The $m$-lighted $n$-shades are introduced in this paper, inspired from the case $m = 1$ studied in~\cite{AbadCrainicDherin, Poliakova, Chapoton-Dyck, Combe, Muhle}.
Here again, the central character is a natural surjective map from the former to the latter.
Namely, the shadow map sends an $m$-painted $n$-tree to the $m$-lighted $n$-shade obtained by collecting the arity sequence along the right branch.
In other words, this map records the shadow projected on the right of the tree when the sun sets on the left of the tree.

We first use this map for lattice purposes.
It was proved in~\cite{ChapotonPilaud} that the right rotation digraph on binary $m$-painted $n$-trees (a mixture of the simple transposition digraph on permutations and the right rotation digraph on binary trees) defines a lattice.
We consider here the right rotation digraph on unary $m$-lighted $n$-shades.
%In contrast to the rotation graph on binary $m$-painted $n$-trees, the rotation graph on unary $m$-lighted $n$-shades is regular (each node has $m+n-1$ incoming plus outgoing neighbors).
We prove that it defines as well a lattice by showing that the shadow map is a meet semilattice morphism (but not a lattice morphism).
When~$m = 0$, this gives an unusual meet semilattice morphism from the Tamari lattice to the Boolean lattice (distinct from the usual lattice morphism given by the canopy map).
When~$m = 1$, this gives a connection, reminiscent of~\cite{Poliakova}, between the painted tree rotation lattice and the Hochschild lattice~\cite{Chapoton-Dyck, Combe, Muhle}.
%The Hochschild lattice has nice lattice properties: it was proved to be congruence uniform and extremal in~\cite{Combe}, its Galois graph, its canonical join complex and its core label order were described in~\cite{Muhle}, and its Coxeter polynomial was conjectured to be a product of cyclotomic polynomials~\cite[Appendix]{Combe}.
%For $m > 1$, computational experiments indicate that the $m$-lighted $n$-shade rotation lattice is still constructible by interval doubling (hence semi-distributive and congruence uniform), but it is not extremal and its Coxeter polynomial is not a product of cyclotomic polynomials.
%However, its subposet induced by unary $m$-lighted $n$-shades where the labels of the lights are ordered seems to enjoy all these nice properties.
%The lattice theory of the $m$-lighted $n$-shade right rotations certainly deserves to be investigated further.

We then use the shadow map for polytopal purposes.
The refinement poset on all $m$-painted $n$-trees is isomorphic to the face lattice of the $(m,n)$-multiplihedron~$\Multiplihedron$.
This polytope is a deformed permutahedron (\aka po\-lymatroid~\cite{Edmonds}, or generalized permutahedron~\cite{Postnikov}) obtained as the shuffle product~\cite{ChapotonPilaud} of an $m$-permutahedron with an $n$-associahedron of~\cite{Loday}.
Oriented in a suitable direction, the skeleton of the \mbox{$(m,n)$-multi}\-plihedron is isomorphic to the right rotation digraph on binary $m$-painted $n$-trees~\cite{ChapotonPilaud}.
Similarly, we show that the refinement poset on all $m$-lighted $n$-shades is isomorphic to the face lattice of the $(m,n)$-Hochschild polytope~$\HP$.
We obtain this polytope by deleting some inequalities in the facet description of the $(m,n)$-multiplihedron.
We also work out the vertex description of the $(m,n)$-Hochschild polytope. % and its decomposition as Minkowski sum of faces of the standard simplex.
We obtain a deformed permutahedron whose oriented skeleton is isomorphic to the right rotation digraph on unary \mbox{$m$-lighted} $n$-shades.
When~$m \! = \! 0$, the $(0,n)$-multiplihedron is the \mbox{$n$-associahedron} and the $(0,n)$-Hochschild polytope is a skew cube (which is not a parallelotope).
When~$m \! = \! 1$, the $(1,n)$-multiplihedron is the classical multiplihedron~\cite{Stasheff-HSpaces, Forcey-multiplihedra, ArdilaDoker}, and the $(1,n)$-Hochschild polytope is a deformed permutahedron realizing the Hochschild lattice~\cite{Chapoton-Dyck, Combe, Muhle}, \mbox{answering an open question~of~F.~Chapoton.}
%Let us insist here on the fact that our Hochschild polytope provides a much stronger geometric realization of the Hochschild lattice than the already two existing ones.
%Namely, the Hochschild lattice is known to be realized
%\begin{compactitem}
%\item on the one hand, as the standard orientation of a graph drawn on the boundary of an hypercube (see \cref{sec:cubicRealizations}), but this graph is not the skeleton of a convex polytope,
%\item on the other hand, as an orientation of the skeleton of a convex polytope called freehedron and obtained as a truncation of the standard simplex~\cite{Saneblidze} (or equivalently as the Minkowski sum of the faces of the standard simplex corresponding to all initial and final intervals), but this orientation cannot be obtained as a Morse orientation given by a linear functional (see \cref{exm:badFreehedron}).
%\end{compactitem}
%Finding a deformed permutahedron whose skeleton oriented in the standard linear direction is isomorphic to the Hasse diagram of the Hochschild lattice was an open question raised by F.~Chapoton.

%The groupies of the permutahedron--associahedron saga probably wonder about properties of the singletons of the shadow map (\ie a unary $m$-lighted $n$-shade whose shadow fiber consists of a single binary $m$-painted $n$-tree).
%Interestingly, these singletons are counted by binomial transforms of Fibonacci numbers.
%Moreover, the common facet defining inequalities of~$\Multiplihedron$ and~$\HP$ are precisely those that contain a common vertex of~$\Multiplihedron$ and~$\HP$.
%This property was essential in the original realization of the Cambrian fans of~\cite{ReadingSpeyer} as generalized associahedra~\cite{HohlwegLangeThomas}.
%
%Somewhat independently, we also show that the right rotation digraph on unary $m$-lighted \mbox{$n$-shades} can also be realized on the boundary of an hypercube, generalizing the existing cubic coordinates for the Hochschild lattice~\cite{Combe}.
%Cubic coordinates are well known for many famous lattices (they are called Lehmer codes for weak Bruhat lattices~\cite{Lehmer}, and bracket vectors for Tamari lattices~\cite{HuangTamari}).
%In \cite{SaneblidzeUmble-diagonals}, a stronger notion of cubic subdivisions was used to construct combinatorial diagonals for the corresponding polytopes.
%When available, cubic coordinates also provide an elegant alternative proof of the lattice property.
%
%We conclude this introduction by a glance at the algebraic motivation for painted trees and lighted shades, coming from homological algebra.
%The family of multiplihedra controls the notion of $A_\infty$-morphisms.
%If $A$ and $B$ are two $A_\infty$-algebras and $f : A \to B$ is an $A_\infty$-morphism, then each face of the multiplihedron encodes an operation $A^{ \otimes n} \to B$, with the cellular differential taking care of the relations.
%Equivalently, one can view the faces of the multiplihedron as encoding the operations $A^{ \otimes n-1} \otimes M \to N$, where $A$ is an $A_\infty$-algebra and $M$ and $N$ are $A_\infty$-modules over~$A$.
%Now if one assumes $A$ strictly associative (DG instead of $A_\infty$), there are clearly less such operations.
%A universal basis for such operations was constructed in \cite[Thm.~6.4]{AbadCrainicDherin} in the form of short forest-tree-forest triples, and it was observed in \cite[Sect.~5]{Poliakova} that these objects are nothing else but the faces of the freehedra of~\cite{Saneblidze}.
%This gave the case $m=1$ of the shadow map \cite[Construction 2]{Poliakova}.

We refer to~\cite{PilaudPoliakova} for many details and all proofs omitted in this extended abstract due to space limitations. The interested reader will in particular find enumerative formulas and cubic coordinates for multiplihedra and Hochschild polytopes.

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

\cleardoublepage
\section{Painted trees, lighted shades, and the shadow map}
\label{sec:combinatorics}

%In this section, we first recall the combinatorics of $m$-painted $n$-trees (\cref{subsec:paintedTrees}) and introduce that of \mbox{$m$-lighted} $n$-shades (\cref{subsec:lightedShades}).
%We then analyse the natural shadow map from $m$-painted $n$-trees to $m$-lighted $n$-shades (\cref{subsec:shadow}), with a particular focus on its singletons (\cref{subsec:singletons}).

%%%%%%%%%

\subsection{$m$-painted $n$-trees}
\label{subsec:paintedTrees}

We start with the combinatorics of $m$-painted $n$-trees already studied in detail in \cite[Sect.~3.1]{ChapotonPilaud}.
It was inspired from the case $m = 1$ studied in~\cite{Stasheff-HSpaces, Forcey-multiplihedra, ArdilaDoker}.

An \defn{$n$-tree} is a rooted plane tree with $n+1$ leaves.
As usual, we orient such a tree towards its root and label its vertices in inorder.
Namely, each node with $\ell$ children is labeled by an $(\ell-1)$-subset~$\{x_1, \dots, x_{\ell-1}\}$ of~$[n]$ such that all labels in  its $i$th subtree are larger than~$x_{i-1}$ and smaller than~$x_i$ (where by convention~$x_0 = 0$ and~$x_\ell = n+1$). Note in particular that unary nodes receive an empty label.
A \defn{cut} of an $n$-tree~$T$ is a subset~$c$ of nodes of~$T$ containing precisely one node along the path from the root to any leaf of~$T$.
A cut~$c$ is \defn{below} a cut~$c'$ if the unique node of $c$ is after the unique node of~$c'$ along any path from the root to a leaf of~$T$ (note that we draw trees growing downward).

\begin{definition}[{\cite[Def.~105]{ChapotonPilaud}}]
\label{def:paintedTrees}
An \defn{$m$-painted $n$-tree}~$\PT \eqdef (T, C, \mu)$ is an $n$-tree~$T$ together with a sequence~$C \eqdef (c_1, \dots, c_k)$ of $k$ cuts of~$T$ and an ordered partition~$\mu$ of~$[m]$ into~$k$ parts for some~$k \in [m]$, such that
\begin{compactitem}
\item $c_i$ is below~$c_{i+1}$ for all~$i \in [k-1]$,
\item $\bigcup C \eqdef c_1 \cup \dots \cup c_k$ contains all unary nodes of~$T$.
\end{compactitem}
\end{definition}

We represent an $m$-painted $n$-tree~$\PT \eqdef (T, C, \mu)$ as a downward growing tree~$T$, where the cuts of~$C$ are red horizontal lines, labeled by the corresponding parts of~$\mu$. As there is no ambiguity, we write $12$ for the set~$\{1,2\}$. See \cref{fig:paintedTrees,fig:deletionsPaintedTrees,fig:rotationsPaintedTrees} for illustrations.

We now associate to each $m$-painted $n$-tree a preposet (\ie a reflexive and transitive binary relation) on~$[m+n]$.
See \cref{fig:paintedTrees}.
%These preposets will often be helpful.

\begin{definition}
\label{def:preorderPaintedTree}
Consider an $m$-painted $n$-tree~$\PT \eqdef (T, C, \mu)$.
Orient~$T$ towards its root, label each node~$x$ of~$T$ by the union of the part in~$\mu$ corresponding to the cut of~$C$ passing through~$x$ (empty set if~$x$ is in no cut of~$C$) and the inorder label of~$x$ in~$T$ shifted by~$m$, and merge all nodes contained in each cut.
Define~$\preccurlyeq_{\PT}$ as the preposet on~$[m+n]$ where~$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.
%See \cref{fig:paintedTrees}.
\end{definition}

We now use these preposets to define the refinement poset on $m$-painted $n$-trees.

\begin{definition}[{\cite[Def.~108]{ChapotonPilaud}}]
The \defn{$m$-painted $n$-tree refinement poset} is the poset on $m$-painted $n$-trees ordered by refinement of their corresponding preposets, that is, $\PT \le \PT'$ if~${\preccurlyeq_{\PT}} \supseteq {\preccurlyeq_{\PT'}}$.
\end{definition}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{paintedTrees}}
%	\centerline{
%		\begin{tabular}{c@{\hspace{-.1cm}}c@{\hspace{-.1cm}}c@{\hspace{-.1cm}}c@{\hspace{-.1cm}}c@{\hspace{-.1cm}}c}
%		    \paintedTree[1]{[[[]][[][]][[[[][][]][]]]]}{}
%		    &
%		    \paintedTree[1]{[[[][[][]]][[[[[][]][]][]]]]}{}
%		    &
%		    \paintedTree[1]{[[1 []][[1 []][1 [][]][1 [][]]]]}{1}
%		    &
%		    \paintedTree[1]{[[1 []][[[1 []][1 [[][]]]][1 [[][]]]]]}{1}
%		    &
%		    \paintedTree[1]{[ [12 []][12 [][[][]][]]]}{12}
%		    &
%		    \paintedTree[1]{[ [1 [2 []]][1 [[[2 [[]]][2 [[][]]]][2 []]]]]}{1,2}
%		    \\
%		    \tree{[.13 [.2 ] [.6 [.45 ] ] ]}
%		    &
%		    \tree{[.3 [.1 [.2 ] ] [.6 [.5 [.4 ] ] ] ]}
%		    &
%		    \tree{[.2 [.35 [.146 ] ] ]}
%		    &
%		    \tree{[.2 [.5 [.3 [.1 [.4 ] [.6 ] ] ] ] ]}
%		    &
%		    \tree{[.3 [.1246 [.5 ] ] ]}
%		    &
%		    \tree{[.3 [.1 [.6 [.4 [.2 [.5 ] ] ] ] ] ]}
%		\end{tabular}
%	}
	\caption{Some $m$-painted $n$-trees (top) and their preposets (bottom). Here~$m + n = 6$.}
	\label{fig:paintedTrees}
\end{figure}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{deletionsPaintedTrees}}
%	\centerline{
%	\centerline{
%		\paintedTree[1]{[12 [][][][][]]}{12}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\paintedTree[1]{[1 [2 []][2 [][]][2 [][]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\paintedTree[1]{[1 [[2 []][2 [][]][2 [][]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\paintedTree[1]{[1 [[2 []][[2 []][2 []]][2 [][]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\paintedTree[1]{[1 [[[2 []][[2 []][2 []]]][2 [][]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\paintedTree[1]{[1 [[[2 []][[2 []][2 []]]][2 [[][]]]]]}{1,2}
%	}
%	}
	\caption{Refinements of some $2$-painted $4$-trees.} % Each refinement is labeled by its type.}
	\label{fig:deletionsPaintedTrees}
\end{figure}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{rotationsPaintedTrees}}
%	\centerline{
%		\paintedTree[1]{[ [2 [1 []]][2 [[[[1 []][1 []]][1 []]][1 []]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [2 [1 []]][2 [[[1 []][[1 []][1 []]]][1 []]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [2 [1 []]][2 [[1 []][[[1 []][1 []]][1 []]]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [2 [1 []]][2 [[1 []][[1 [[][]]][1 []]]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [2 [1 []]][2 [[1 []][1 [[[][]][]]]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [2 [1 []]][2 [1 [[][[[][]][]]]]]]}{2,1}
%		\hspace{-.5cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.5cm}
%		\paintedTree[1]{[ [1 [2 []]][1 [2 [[][[[][]][]]]]]]}{1,2}
%	}
	\caption{Rotations of some binary $2$-painted $4$-trees.} % Each rotation is labeled by its type.}
	\label{fig:rotationsPaintedTrees}
\end{figure}

In the following statement, we denote by~$|T|$ the number of nodes of a tree~$T$ (including unary nodes), and define~$|C| \eqdef k$ and~$|\bigcup C| \eqdef |c_1 \cup \dots \cup c_k|$ for~$C = (c_1, \dots, c_k)$.

\begin{proposition}[{\cite[Props.~107 \& 116]{ChapotonPilaud}}]
The $m$-painted $n$-tree refinement poset is a meet semilattice ranked by ${m+n-|T|-|C|+|\bigcup C|}$.
\end{proposition}

We now define another lattice, but on rank~$0$ $m$-painted $n$-trees.
See \cref{fig:rotationsPaintedTrees,fig:multiplihedronFreehedronLabeledLattice13}.

\begin{definition}[{\cite[Def.~112]{ChapotonPilaud}}]
An $m$-painted $n$-tree~$\PT \eqdef (T, C, \mu)$ is \defn{binary} if it has rank~$0$, meaning that all nodes in~$\bigcup C$ are unary, while all nodes not in~$\bigcup C$ are binary.
The \defn{binary $m$-painted $n$-tree right rotation digraph} is the directed graph on binary $m$-painted $n$-tree with an edge~$(\PT, \PT')$ if and only if there exists~$1 \le i < j \le m+n$ such that~${{\preccurlyeq_{\PT}} \! \ssm \! \{(i,j)\} = {\preccurlyeq_{\PT'}} \! \ssm \! \{(j,i)\}}$.
\end{definition}

\begin{proposition}[{\cite[Def.~119]{ChapotonPilaud}}]
The binary $m$-painted $n$-tree right rotation digraph is the Hasse diagram of a lattice. % It is meet semidistributive, but not join semidistributive when~$m \ge 1$.
\end{proposition}

\begin{example}
When~$m = 0$, the $0$-painted $n$-tree rotation lattice is the Tamari lattice~\cite{Tamari}.
When~$m = 1$, the $1$-painted $n$-tree rotation lattice is the multiplihedron lattice introduced in~\cite{ChapotonPilaud}.
\end{example}

\begin{remark}
Note that the $m$-painted $n$-tree rotation lattice is meet semidistributive, but not join semidistributive when~$m \ge 1$.
\end{remark}

Let us finally mention that $m$-painted $n$-trees have interesting enumerative properties. See~\cite[Sect.~1.1]{PilaudPoliakova} for formulas for some $m$-painted $n$-trees generating functions.

%%%%%%%%%

\pagebreak
\subsection{$m$-lighted $n$-shades}
\label{subsec:lightedShades}

We now introduce the main new characters of this paper, which will later appear as certain shadows of $m$-painted $n$-trees.

\begin{definition}
\label{def:lightedShades}
An \defn{$n$-shade} is a sequence of (possibly empty) tuples of integers, whose total sum is~$n$.
An \defn{$m$-lighted $n$-shade}~$\LS \eqdef (S, C, \mu)$ is an $n$-shade~$S$ together with a set~$C$ of $k$ distinguished positions in~$S$, containing all positions of empty tuples of~$S$, and an ordered partition~$\mu$ of~$[m]$ into~$k$ parts for some~$k \in [m]$.
\end{definition}

We represent an $m$-lighted $n$-shade~$\LS \eqdef (S, C, \mu)$ as a vertical line, with the tuples of the sequence~$S$ in black on the left, and the cuts of~$C$ in red on the right, all from top to bottom. As there is no ambiguity, we write $12$ for the tuple $(1,2)$ or the set~$\{1,2\}$. See \cref{fig:lightedShades,fig:deletionsLightedShades,fig:rotationsLightedShades} for illustrations.

We now associate to each $m$-lighted $n$-shade a preposet on~$[m+n]$.
See \cref{fig:lightedShades}

\begin{definition}
\label{def:preorderLightedShade}
Consider an $m$-lighted $n$-shade~$\LS \eqdef (S, C, \mu)$.
The \defn{preceeding sum}~$ps(x)$ of an entry~$x$ in a tuple of~$S$ is $m$ plus the sum of all entries that appear weakly before~$x$ in~$S$ (meaning either the entries in a strictly earlier tuple of~$S$, or the weakly earlier entries in the same tuple as~$x$).
Define~$\preccurlyeq_{\LS}$ as the preposet on~$[m+n]$ given by the relations
\begin{compactitem}
\item $i \preccurlyeq_{\LS} j$ if~$i,j \in [m]$ and~$i$ appears weakly after~$j$ in~$\mu$,
\item $k \preccurlyeq_{\LS} ps(y)$ if~$x$ and~$y$ are elements of tuples of~$S$ such that the tuple of~$x$ appears weakly after the tuple of~$y$, and~$ps(x)-x < k \le ps(x)$,
\item $i \preccurlyeq_{\LS} ps(x)$ if~$i \in [m]$ and~$x$ is an element of a tuple of~$S$ which appears weakly before the cut containing~$i$,
\item $k \preccurlyeq_{\LS} i$ if~$i \in [m]$ and~$ps(x)-x < k \le ps(x)$ for some element~$x$ of a tuple of~$S$ which appears weakly after the cut containing~$i$.
\end{compactitem}
%See \cref{fig:lightedShades}
\end{definition}

We now use these preposets to define the refinement poset on $m$-lighted $n$-shades.

\begin{definition}
The \defn{$m$-lighted $n$-shade refinement poset} is the poset on $m$-lighted $n$-shades defined by refinement of their corresponding preposets, that is, $\LS \le \LS'$ if~${\preccurlyeq_{\LS}} \supseteq {\preccurlyeq_{\LS'}}$.
\end{definition}

For a sequence~$S \eqdef (s_1, \dots, s_\ell)$ of tuples, we define~$|S| \eqdef \ell$ and~$\|S\| \eqdef \sum_{i \in [\ell]} |s_i|$, where~$|s_i|$ is the length of the tuple~$s_i$.

\begin{proposition}
\label{prop:lightedShadeRefinementLattice}
The $m$-lighted $n$-shade refinement poset is a meet semilattice ranked \linebreak by ${m - |S| + \|S\|}$.
\end{proposition}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{lightedShades}}
%	\centerline{
%		\begin{tabular}{c@{\hspace{.1cm}}c@{\hspace{.1cm}}c@{\hspace{.1cm}}c@{\hspace{.1cm}}c@{\hspace{.1cm}}c}
%		    \lightedShade[1]{[{12} [3 []]]}{}
%		    &
%		    \lightedShade[1]{[3 [3 []]]}{}
%		    &
%		    \lightedShade[1]{[1 [{12} [1, tier=1 []]]]}{1}
%		    &
%		    \lightedShade[1]{[1 [3 [, tier=1 [1 []]]]]}{1}
%		    &
%		    \lightedShade[1]{[1 [{12}, tier=12 []]]}{12}
%		    &
%		    \lightedShade[1]{[1 [, tier=1 [3 [, tier=2 []]]]]}{1,2}
%		    \\
%		    \tree{[.13 [.2 ] [.6 [.4 ] [.5 ] ] ]}
%		    &
%		    \tree{[.3 [.1 ] [.2 ] [.6 [.4 ] [.5 ] ] ]}
%		    &
%		    \tree{[.2 [.35 [.16 ] [.4 ] ] ]}
%		    &
%		    \tree{[.2 [.5 [.1 [.6 ] ] [.3 ] [.4 ] ] ]}
%		    &
%		    \tree{[.3 [.1246 [.5 ] ] ]}
%		    &
%		    \tree{[.3 [.1 [.6 [.2 ] [.4 ] [.5 ] ] ] ]}
%		\end{tabular}
%	}
	\caption{Some $m$-lighted $n$-shades (top) and their preposets (bottom). Here~$m + n = 6$.}
	\label{fig:lightedShades}
\end{figure}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{deletionsLightedShades}}
%	\centerline{
%		\lightedShade[1]{[{1111}, tier=12 []]}{12}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[{121}, tier=12 []]}{12}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[{12}, tier=1 [1, tier=2 []]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[, tier=1 [{12} [1, tier=2 []]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[, tier=1 [3 [1, tier=2 []]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-.7cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[, tier=1 [3 [, tier=2 [1 []]]]]}{1,2}
%	}
	\caption{Refinements of some $2$-lighted $4$-shades. } %Each refinement is labeled by its type.}
	\label{fig:deletionsLightedShades}
\end{figure}

\begin{figure}[!t]
	\centerline{\includegraphics[scale=.83]{rotationsLightedShades}}
%	\centerline{
%		\lightedShade[1]{[1 [, tier=2 [3 [, tier=1 []]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[1 [, tier=2 [1 [2 [, tier=1 []]]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[1 [, tier=2 [1 [, tier=1 [2 []]]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[1 [, tier=2 [, tier=1 [1 [2 []]]]]]}{1,2}
%		\hspace{-.3cm}\raisebox{-1.2cm}{$\longrightarrow$}\hspace{-.3cm}
%		\lightedShade[1]{[1 [, tier=1 [, tier=2 [1 [2 []]]]]]}{2,1}
%	}
	\caption{Rotations of some unary $2$-lighted $4$-shades.} % Each rotation is labeled by its type.}
	\label{fig:rotationsLightedShades}
\end{figure}

We now define another lattice, but on rank~$0$ $m$-lighted $n$-shades.
\mbox{See \cref{fig:rotationsLightedShades,fig:multiplihedronFreehedronLabeledLattice13}.}

\begin{definition}
An $m$-lighted $n$-shade~$\LS \eqdef (S, C, \mu)$ is \defn{unary} if it has rank~$0$, meaning that~all tuples in~$\bigcup C$ are empty tuples, while all tuples not in~$\bigcup C$ are singletons.
The \defn{unary \mbox{$m$-lighted} \mbox{$n$-shade} right rotation digraph} is the directed graph on unary $m$-lighted $n$-shades with an \linebreak edge~$(\LS, \LS')$ if and only if there exists~$1 \le i < j \le m+n$ such that~${{\preccurlyeq_{\LS}} \! \ssm \! \{(i,j)\} = {\preccurlyeq_{\LS'}} \! \ssm \! \{(j,i)\}}$.
\end{definition}

\begin{remark}
\label{rem:rotationGraphLightedShadesRegular}
We observe that any unary $m$-lighted $n$-shade~$\LS$ with singleton tuples~$s_1, \dots, s_k$ admits~$m+k-1+\sum_{i \in [k]} (s_i-1) = m+n-1$ (left or right) rotations.
In other words, the (undirected) rotation graph is regular of degree~$m+n-1$.
%Note that this can also be seen as a consequence of \cref{rem:caterpillar}.
\end{remark}

%The next statement will follow from \cref{prop:shadowMapSemilatticeMapRotation}.

\begin{proposition}
\label{prop:lightedShadeRotationLattice}
The unary $m$-lighted $n$-shade right rotation digraph is the Hasse diagram of a lattice.
\end{proposition}

\begin{example}
When~$m = 0$, the $0$-lighted $n$-shade rotation lattice is boolean.
When~${m = 1}$, the $1$-lighted $n$-shade rotation lattice is the Hochschild lattice studied in~\cite{Chapoton-Dyck, Combe, Muhle}.
\end{example}

\begin{remark}
\label{rem:latticeProperties}
Computational experiments indicate that the $m$-lighted $n$-shade rotation lattice is constructible by interval doubling (hence semidistributive and congruence uniform).
However, in contrast to the case when~$m \le 1$, it is not extremal (see~\cite{Muhle} for context), and its Coxeter polynomial is not a product of cyclotomic polynomials (see \cite{Chapoton-PFCIC} and \cite[Appendix]{Combe} for context).
Nevertheless, its subposet induced by unary $m$-lighted $n$-shades where the labels of the lights are ordered %(see also \cref{def:multiwords}) 
seems to enjoy all these nice properties.
%The lattice properties of the $m$-lighted $n$-shade rotation lattice and its subposet deserve to be investigated further.
\end{remark}

Let us finally mention that $m$-lighted $n$-shades have interesting enumerative properties. See~\cite[Sect.~1.1]{PilaudPoliakova} for formulas for some $m$-lighted $n$-shades generating functions.

\begin{figure}[t]
	\centerline{\includegraphics[scale=.91]{multiplihedronFreehedronLabeledLattice13}}
%	\centerline{\input{multiplihedronFreehedronLabeledLattice13}}
	\caption{The $1$-painted $3$-tree (left) and $1$-lighted $3$-shade (right) rotation lattices.}
	\label{fig:multiplihedronFreehedronLabeledLattice13}
\end{figure}

%%%%%%%%%

\subsection{Shadow map}
\label{subsec:shadow}

We now describe the shadow map sending an $m$-painted $n$-tree to an $m$-lighted $n$-shade.
Intuitively, the shadow is what you see on the right of the tree when the sun sets on its left.
For instance, the $m$-painted $n$-trees of \cref{fig:paintedTrees} are sent to the $m$-lighted $n$-shade of \cref{fig:lightedShades}.
We call \defn{right branch} of a tree~$T$ the path from the root to the rightmost leaf~of~$T$.

\begin{definition}
The \defn{shadow} of an $n$-tree~$T$ is the $n$-shade~$\shadow(T)$ obtained by 
\begin{compactitem}
\item contracting all edges joining a child to a parent which does not lie on the right branch~of~$T$,
\item replacing each node on the right branch of~$T$ by the tuple of the arities of its children except its rightmost.
\end{compactitem}
The \defn{shadow} of a cut~$c$ in~$T$ is the position~$\shadow(c)$ in~$\shadow(T)$ of the unique node of the right branch of~$T$ contained in~$c$.
For a sequence~$C = (c_1, \dots, c_k)$, define~$\shadow(C) \eqdef (\shadow(c_1), \dots, \shadow(c_k))$.
The \defn{shadow} of an $m$-painted $n$-tree\,$\PT \! \eqdef \! (T, C, \mu)$ is the $m$-lighted\,$n$-shade\,$\shadow(\PT) \! \eqdef \! (\shadow(S), \shadow(C), \mu)$.
\end{definition}

%\begin{definition}
%The \defn{shadow congruence} is the equivalence class on $m$-painted $n$-trees whose equivalence classes are the fibers of the shadow map. In other words, two $m$-painted $n$-trees are shadow congruent if they have the same shadow.
%\end{definition}

Given two meet semilattices~$(M, \meet)$ and~$(M', \meet')$, a map~$f : M \to M'$ is a \defn{meet semilattice morphism} if~$f(x \meet y) = f(x) \meet' f(y)$ for all~$x,y \in M$.
%The fibers of~$f$ are the classes of a \defn{meet semilattice congruence}~$\equiv_f$ on~$M$, and the image of~$f$ is then called the \defn{meet semilattice quotient} of~$M$ by~$\equiv_f$.
%In other words, an equivalence relation~$\equiv$ on~$M$ is a meet semilattice congruence when~$x_1 \equiv x_2$ and~$y_1 \equiv y_2$ implies~$x_1 \meet y_1 \equiv x_2 \meet y_2$, and the quotient~$M / {\equiv}$ is the meet semilattice on the $\equiv$-equivalence classes, where for two $\equiv$-equivalence classes~$X$ and~$Y$, 
%\begin{compactitem}
%\item the order relation is given by~$X \le Y$ if there exist representatives~$x \in X$ and~$y \in Y$ such that~$x \le y$, 
%\item the meet~$X \meet Y$ is the $\equiv$-equivalence class of~$x \meet y$ for any representatives~$x \in X$ and~$y \in Y$.
%\end{compactitem}
%The following classical criterion will be fundamental.
%
%\begin{proposition}
%\label{prop:characterizationMeetSemilatticeCongruence}
%An equivalence relation~$\equiv$ on a meet semilattice~$(M, \meet)$ is a meet semilattice congruence if and only if
%\begin{compactitem}
%\item each $\equiv$-equivalence class admits a unique minimal element,
%\item the map~$\projDown : M \to M$ sending an element of~$M$ to the minimal element of its $\equiv$-equivalence class is order preserving.
%\end{compactitem}
%\end{proposition}
%
%%Join semilattice morphisms, congruences and quotients are defined dually, and the dual characterization to \cref{prop:characterizationMeetSemilatticeCongruence} holds.
%We will now apply this characterization to the shadow congruence on the binary $m$-painted $n$-tree rotation lattice.
%This will prove along the way that the binary $m$-painted $n$-tree rotation poset is a meet semilattice quotient, hence a meetsemilattice, hence a lattice as it is bounded.
%This completes the proof of \cref{prop:lightedShadeRotationLattice}.

\begin{theorem}
\label{thm:shadowMapSemilatticeMapRotation}
The shadow map is a surjective meet semilattice morphism from the binary \mbox{$m$-pain}\-ted $n$-tree rotation lattice to the unary $m$-lighted $n$-shade rotation lattice.
See \cref{fig:multiplihedronFreehedronLabeledLattice13}.
\end{theorem}

\begin{remark}
Note that the shadow map is not a join semilattice morphism.
For instance,
\[
\raisebox{-.48cm}{\includegraphics[scale=.83]{notLatticeMorphism1}}
%\shadow \bigg( \hspace{-.4cm} \raisebox{.8cm}{\paintedTree[1]{[[1[[][]]][1[]]]}{1}} \hspace{-.4cm} \join \hspace{-.4cm} \raisebox{.8cm}{\paintedTree[1]{[[1[]][[1[]][1[]]]]}{1}} \hspace{-.4cm} \bigg) = \hspace{-.4cm} \raisebox{1cm}{\lightedShade[1]{[, tier=1 [1 [1 []]]]}{1}} \hspace{-.4cm},
\qquad\text{while}\qquad
\raisebox{-.48cm}{\includegraphics[scale=.83]{notLatticeMorphism2}}
%\shadow \bigg( \hspace{-.4cm} \raisebox{.8cm}{\paintedTree[1]{[[1[[][]]][1[]]]}{1}} \hspace{-.4cm} \bigg) \join \shadow \bigg( \hspace{-.4cm} \raisebox{.8cm}{\paintedTree[1]{[[1[]][[1[]][1[]]]]}{1}} \hspace{-.4cm} \bigg)  \hspace{-.4cm} \raisebox{1cm}{\lightedShade[1]{[1 [1 [, tier=1 []]]]}{1}} \hspace{-.4cm}.
\]
\end{remark}

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

\section{Multiplihedra and Hochschild polytopes}
%\label{sec:combinatorics}

%%%%%%%%%

\subsection{Multiplihedra}
\label{subsec:multiplihedra}

We now consider the $(m,n)$-multiplihedron which realizes the $m$-painted $n$-tree refinement lattice.
It is illustrated for~$m = 1$ and~$n = 3$ in \cref{fig:multiplihedronFreehedronLabeledOriented13}.
Although they were previously constructed when~$m = 1$ in~\cite{Stasheff-HSpaces, Forcey-multiplihedra, ArdilaDoker}, we use here the construction of~\cite[Sect.~3]{ChapotonPilaud}.
This construction is just an example of the shuffle product on deformed permutahedra, introduced in~\cite[Sect.~2]{ChapotonPilaud}.
However, we do not need the generality of this operation and define the $(m,n)$-multiplihedron using its vertex and facet~descriptions.

\begin{definition}
\label{def:verticesPaintedTrees}
Consider a binary $m$-painted $n$-tree\,$\PT\!\eqdef\!(T, C, \mu)$.
We associate to\,$\PT$ a point\,$\b{a}(\PT)$ whose $p$th coordinate is
\begin{compactitem}
\item if~$p \le m$, the number of binary nodes and cuts weakly below the cut labeled by~$p$,
\item if~$p \ge m+1$, the number of cuts below plus the product of the numbers of leaves in the left and right subtrees of the node of~$T$ labeled by~$p-m$ in inorder.
\end{compactitem}
See \cref{fig:verticesFacetsPaintedTrees} for some examples.
\end{definition}

\begin{definition}
\label{def:inequalitiesPaintedTrees}
Consider the hyperplane~$\HH_{m+n}$ of~$\R^{m+n}$ defined by % the equality
\(
\bigdotprod{\b{x}}{\b{1}_{[m+n]}} = \binom{m+n+1}{2}.
\)
Moreover, for each rank~$m+n-2$ $m$-painted $n$-tree~$\PT \eqdef (T, C, \mu)$, consider the halfspace~$\b{H}(\PT)$ of~$\R^{m+n}$ defined by % the inequality
\(
\bigdotprod{\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|,
\)
where
\begin{compactitem}
\item $A$ denotes the set of elements of~$[m]$ which label the cut of~$C$ not containing the root of~$T$ (hence, $A = \varnothing$ if~$C$ has only one cut, which contains the root of~$T$), 
\item $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$.
\end{compactitem}
See \cref{fig:verticesFacetsPaintedTrees} for some examples.
\end{definition}

\begin{theorem}[{\cite[Props.~116, 122, 123]{ChapotonPilaud}}]
\label{thm:VHDescriptionsPaintedTrees}
The $m$-painted $n$-tree refinement lattice is anti-isomorphic to the face lattice of the \defn{$(m,n)$-multiplihedron}~$\Multiplihedron$, defined equivalently as
\begin{compactenum}[(i)]
\item the convex hull of the vertices~$\b{a}(\PT)$ for all binary $m$-painted $n$-trees~$\PT$,
\item the intersection of the hyperplane~$\HH_{m+n}$ with the halfspaces~$\b{H}(\PT)$ for all rank~$m+n-2$ \mbox{$m$-painted} $n$-trees~$\PT$.
\end{compactenum}
\end{theorem}

\begin{proposition}[{\cite[Prop.~118]{ChapotonPilaud}}]
\label{prop:fanPaintedTrees}
The normal fan of the $(m,n)$-multiplihedron~$\Multiplihedron$ is the fan whose cones are the preposet cones of the preposets~$\preccurlyeq_{\PT}$ of all $m$-painted $n$-trees~$\PT$.
%The preposet cones of the preposets~$\preccurlyeq_{\PT}$ of all $m$-painted $n$-trees~$\PT$ form a fan, called the \defn{$m$-painted $n$-tree fan}.
\end{proposition}

\begin{proposition}[{\cite[Prop.~119]{ChapotonPilaud}}]
\label{prop:graphPaintedTrees}
The skeleton of the $(m,n)$-multiplihedron~$\Multiplihedron$ oriented in the direction~$\b{\omega}_{m+n} \eqdef (m+n, \dots, 1) - (1, \dots, m+n)$ is isomorphic to the right rotation digraph on binary $m$-painted $n$-trees.
\end{proposition}

\begin{example}
When~$m \! = \! 0$, the $(0,n)$-multiplihedron is Loday's associahedron~\cite{Loday}.
When~$m \! = \! 1$, the $(1,n)$-multiplihedron is the classical multiplihedron alternatively constructed in~\cite{Forcey-multiplihedra, ArdilaDoker}.
\end{example}

%%%%%%%%%

\begin{figure}[t]
	\centerline{\includegraphics[scale=.91]{multiplihedronFreehedronLabeledOriented13}}
%	\centerline{\input{multiplihedronFreehedronLabeledOriented13}}
	\caption{Multiplihedron~$\Multiplihedron[1][3]$ (left) and Hochschild polytope~$\HP[1][3]$ (right).}
	\label{fig:multiplihedronFreehedronLabeledOriented13}
\end{figure}

%%%%%%%%%

\begin{figure}
	\vspace{.3cm}
	\centerline{\includegraphics[scale=.83]{verticesPaintedTrees}}
%	\centerline{
%	\begin{tabular}{c@{}c@{}c@{}c@{}c@{}c@{}c}
%		\paintedTree[1]{[[[[1[]][1[]]][1[]]][1[]]]}{1} &
%		\paintedTree[1]{[[[1[]][[1[]][1[]]]][1[]]]}{1} &
%		\paintedTree[1]{[[[1[[][]]][1[]]][1[]]]}{1} &
%		\paintedTree[1]{[[[1[]][1[]]][[1[]][1[]]]]}{1} &
%		\paintedTree[1]{[[1[]][[[1[]][1[]]][1[]]]]}{1} &
%		\paintedTree[1]{[[[1[]][1[[][]]]][1[]]]}{1} &
%		\paintedTree[1]{[[1[[[][]][]]][1[]]]}{1} \\
%		$1234$ & 
%		$1324$ & 
%		$2134$ & 
%		$1252$ & 
%		$1423$ & 
%		$2314$ & 
%		$3124$ \\
%	\end{tabular}
%	}
	\vspace{.5cm}
	\centerline{\includegraphics[scale=.83]{inequalitiesPaintedTrees}}
%	\centerline{
%	\begin{tabular}{c@{}c@{}c@{}c@{}c@{}c@{}c}
%		\paintedTree[1]{[[1[]][1[]][1[]][1[]]]}{1} &
%		\paintedTree[1]{[[1[][]][1[]][1[]]]}{1} &
%		\paintedTree[1]{[[1[]][1[][]][1[]]]}{1} &
%		\paintedTree[1]{[[1[]][1[]][1[][]]]}{1} &
%		\paintedTree[1]{[[1[][][]][1[]]]}{1} &
%		\paintedTree[1]{[[1[][]][1[][]]]}{1} &
%		\paintedTree[1]{[[1[]][1[][][]]]}{1} \\
%		$x_1 \ge 1$ & 
%		$x_1 + x_2 \ge 3$ & 
%		$x_1 + x_3 \ge 3$ & 
%		$x_1 + x_4 \ge 3$ & 
%		$x_1 + x_2$ & 
%		$x_1 + x_2$ & 
%		$x_1 + x_3$ \\
%		&
%		&
%		&
%		&
%		$+ x_3 \ge 6$ & 
%		$+ x_4 \ge 5$ &
%		$+ x_4 \ge 6$
%	\end{tabular}
%	}
	\caption{Some vertices (top) and facet defining inequalities (bottom) of~$\Multiplihedron[1][3]$.}
	\label{fig:verticesFacetsPaintedTrees}
\end{figure}

\begin{figure}
	\vspace{.3cm}
	\centerline{\includegraphics[scale=.83]{verticesLightedShades}}
%	\centerline{
%	\begin{tabular}{c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c@{\hspace{-.2cm}}c}
%		\lightedShade[1]{[3 [, tier=1[]]]}{1} &
%		\lightedShade[1]{[2 [1 [, tier=1[]]]]}{1} &
%		\lightedShade[1]{[1 [2 [, tier=1[]]]]}{1} &
%		\lightedShade[1]{[2 [, tier=1[1 []]]]}{1} &
%		\lightedShade[1]{[1 [1 [1 [, tier=1[]]]]]}{1} &
%		\lightedShade[1]{[, tier=1[3 []]]}{1} &
%		\lightedShade[1]{[1 [1 [, tier=1[1 []]]]]}{1} &
%		\lightedShade[1]{[1 [, tier=1[2 []]]]}{1} &
%		\lightedShade[1]{[1 [, tier=1[1 [1 []]]]]}{1} &
%		\lightedShade[1]{[, tier=1[2 [1 []]]]}{1} &
%		\lightedShade[1]{[, tier=1[1 [2 []]]]}{1} &
%		\lightedShade[1]{[, tier=1[1 [1 [1 []]]]]}{1}
%		\\
%		$1117$ &
%		$1162$ &
%		$1414$ &
%		$2161$ &
%		$1432$ &
%		$4114$ &
%		$2431$ &
%		$3412$ &
%		$3421$ &
%		$4141$ &
%		$4312$ &
%		$4321$
%	\end{tabular}
%	}
	\vspace{.5cm}
	\centerline{\includegraphics[scale=.83]{inequalitiesLightedShades}}
%	\centerline{
%	\begin{tabular}{c@{}c@{}c@{}c@{}c@{}c@{}c@{}c}
%		\lightedShade[1]{[111 [, tier=1 []]]}{1} &
%		\lightedShade[1]{[11 [1, tier=1 []]]}{1} &
%		\lightedShade[1]{[1 [11, tier=1 []]]}{1} &
%		\lightedShade[1]{[21, tier=1 []]}{1} &
%		\lightedShade[1]{[12, tier=1 []]}{1} &
%		\lightedShade[1]{[11, tier=1 [1 []]]}{1} &
%		\lightedShade[1]{[1, tier=1 [11 []]]}{1} &
%		\lightedShade[1]{[, tier=1 [111 []]]}{1} \\
%		$x_1 \ge 1$ & 
%		$x_1 + x_4 \ge 3$ & 
%		$x_1 + x_3$ &
%		$x_2 \ge 1$ & 
%		$x_3 \ge 1$ & 
%		$x_4 \ge 1$ & 
%		$x_3 + x_4 \ge 1$ &
%		$x_2 + x_3$ \\
%		&
%		&
%		$+ x_4 \ge 6$ &
%		&
%		&
%		&
%		&
%		$+ x_4 \ge 6$
%	\end{tabular}
%	}
	\caption{Vertices (top) and facet defining inequalities (bottom) of~$\HP[1][3]$.}
	\label{fig:verticesFacetsLightedShades}
\end{figure}

%%%%%%%%%

\clearpage
\subsection{Hochschild polytopes}
\label{subsec:freehedra}

We now construct the $(m,n)$-Hochschild polytope which realizes the $m$-lighted $n$-shade refinement lattice.
It is illustrated for~$m = 1$ and~$n = 3$ in \cref{fig:multiplihedronFreehedronLabeledOriented13}.
Recall that we denote by~$ps(x)$ the preceeding sum of an entry~$x$ in an $m$-lighted $n$-shade (see \cref{def:preorderLightedShade}).

\begin{definition}
\label{def:verticesLightedShades}
Consider a unary $m$-lighted $n$-shade~$\LS \eqdef (S, C, \mu)$ and denote by~$s_1, s_2, \dots, s_k$ the values of the singleton tuples of~$S$.
We associate to~$\LS$ a point~$\b{a}(\LS)$ whose $p$th coordinate is
\begin{compactitem}
\item if $p \le m$, then the number of cuts plus the sum of the entries~$s_i$ which are weakly below the cut labeled~$p$,
\item if there is~$j \in [k]$ such that~$p = ps(s_j)$, then~$1 + s_j \big( m + n - p + c_p \big) + \binom{s_j}{2}$ where~$c_p$ is the number of cuts below $s_j$,
\item $1$ otherwise.
\end{compactitem}
See \cref{fig:verticesFacetsLightedShades} for some examples.
\end{definition}

\begin{definition}
\label{def:inequalitiesLightedShades}
Consider the hyperplane~$\HH_{m+n}$ of~$\R^{m+n}$ defined by % the equality
\(
{\bigdotprod{\b{x}}{\b{1}_{[m+n]}} = \binom{m+n+1}{2}}.
\)
Moreover, for each rank~$m+n-2$ $m$-lighted $n$-shade~$\LS \eqdef (S, C, \mu)$, consider the halfspace~$\b{H}(\LS)$ of~$\R^{m+n}$ defined by %the inequality
\(
\bigdotprod{\b{x}}{\one_{A \cup B}} \ge \binom{|A|+|B|+1}{2},
\)
where
\begin{compactitem}
\item $A$ denotes the set of elements of~$[m]$ which label the cut of~$C$ not containing the first tuple of~$S$ (hence, $A = \varnothing$ if~$C$ has only one cut, which contains the first tuple of~$S$), 
\item $B = \{m+q\}$ if $S$ is a single tuple with $2$ in position~$q$, and~$B = \{m+q+1, \dots, m+n\}$ if~$S = (s_1, s_2)$ is a pair of tuples with~$|s_1| = q$.
\end{compactitem}
See \cref{fig:verticesFacetsLightedShades} for some examples.
\end{definition}

%\begin{remark}
%\label{rem:removahedron}
%The inequalities of \cref{def:inequalitiesLightedShades} form a subset of the inequalities of \cref{def:inequalitiesPaintedTrees}.
%\end{remark}
%
%We postpone the proofs of the next three statements to \cref{subsec:proofs}.

\begin{theorem}
\label{thm:VHDescriptionsLightedShades}
The $m$-lighted $n$-shade refinement lattice is anti-isomorphic to the face lattice of the \defn{$(m,n)$-Hochschild polytope}~$\HP$, defined equivalently as
\begin{compactenum}[(i)]
\item the convex hull of the vertices~$\b{a}(\LS)$ for all unary $m$-lighted $n$-shades~$\LS$,
\item the intersection of the hyperplane~$\HH_{m+n}$ with the halfspaces~$\b{H}(\LS)$ for all rank~$m+n-2$ $m$-lighted $n$-shades~$\LS$.
\end{compactenum}
\end{theorem}

\begin{proposition}
\label{prop:fanLightedShades}
The normal fan of the $(m,n)$-Hochschild polytope~$\HP$ is the fan whose cones are the preposet cones of the preposets~$\preccurlyeq_{\LS}$ of all $m$-lighted $n$-shades~$\LS$.
%The preposet cones of the preposets~$\preccurlyeq_{\LS}$ of all $m$-lighted $n$-shades~$\LS$ form a fan, called the \defn{$m$-lighted $n$-shade fan}.
\end{proposition}

\begin{proposition}
\label{prop:graphLightedShades}
The skeleton of the $(m,n)$-Hochschild polytope~$\HP$ oriented in the direction~$\b{\omega}_{m+n} \eqdef (m+n, \dots, 1) - (1, \dots, m+n)$ is isomorphic to the right rotation digraph on unary $m$-lighted $n$-shades.
\end{proposition}

\begin{remark}
It follows from \cref{rem:rotationGraphLightedShadesRegular} that the $(m,n)$-Hochschild polytope is simple and the $m$-lighted $n$-shade fan is simplicial.
\end{remark}

\begin{remark}
\label{rem:similarities}
As mentioned in the introduction, there are deep similarities between the behaviors~of
\begin{compactitem}
\item the permutahedron~$\Perm$ and the associahedron~$\Asso$,
\item the multiplihedron~$\Multiplihedron$ and the Hochschild polytope~$\HP$.
\end{compactitem}
Some comments on the behavior of the latter for the reader familiar with the behavior of the former:
\begin{compactitem}
\item The $(m,n)$-Hochschild polytope~$\HP$ can be obtained by deleting inequalities in the facet description of the $(m,n)$-multiplihedron~$\Multiplihedron$.
\item The common facet defining inequalities of~$\Multiplihedron$ and~$\HP$ are precisely those that contain a common vertex of~$\Multiplihedron$ and~$\HP$. % (the singletons of \cref{subsec:singletons}).
\item In contrast, the vertex barycenters of the $(m,n)$-multiplihedron~$\Multiplihedron$ and of the \mbox{$(m,n)$-Hochschild} polytope~$\HP$ do not coincide.
\item When~$m = 0$, the $(0,n)$-Hochschild polytope~$\HP[0][n]$ is a skew cube distinct from the parallelepiped obtained by considering the canopy congruence on binary trees. % (which is a lattice congruence, in contrast to the shadow meet semilattice congruence).
\end{compactitem}
\end{remark}

\begin{example}
\label{exm:badFreehedron}
When~$m = 0$, the $(0,n)$-Hochschild polytope is a skew cube, distinct from the parallelotope~$\sum_{i \in [n-1]} [\b{e}_i, \b{e}_{i+1}]$.
When~$m = 1$, the $(1,n)$-Hochschild polytope gives a realization of the Hochschild lattice~\cite{Chapoton-Dyck, Combe, Muhle}.
Note that the unoriented rotation graph on \mbox{$1$-lighted} $n$-shades was already known to be isomorphic to the unoriented skeleton of a deformed permutahedron called \defn{freehedron} and obtained as a truncation of the standard simplex~\cite{Saneblidze}, or more precisely as the Minkowski sum~$\sum_{i \in [n]} \simplex_{\{1, \dots, i\}} + \sum_{i \in [n]} \simplex_{\{i, \dots, n\}}$ of the faces of the standard simplex corresponding to initial and final intervals, see \cref{fig:badFreehedron}.
However, orienting the skeleton of the freehedron in direction~$\b{\omega}_{m+n}$, we obtain a poset different from the Hochschild lattice, and which is not even a lattice.
Indeed, in \cref{fig:badFreehedron}\,(left) the two blue vertices have no join while the two red vertices have no meet.
In fact, the Hasse diagram of the Hochschild lattice cannot be obtained as a Morse orientation given by a linear functional on the freehedron.
Finally, observe that the freehedron cannot be obtained by removing inequalities in the facet description of the permutahedron or of the multiplihedron.
See \cref{fig:badFreehedron} where the removahedra have the wrong~combinatorics. % (look at the $4$-valent vertex on the right of the polytopes).
%
\begin{figure}[h]
	\centerline{
		\includegraphics[scale=.6]{badFreehedronNotLattice}
		\quad
		\includegraphics[scale=.6]{badFreehedronNotRemovahedronPermutahedron}
		\includegraphics[scale=.6]{badFreehedronNotRemovahedronMultiplihedron}
	}
%	\centerline{
%		\input{figures/badFreehedronNotLattice}
%		\input{figures/badFreehedronNotRemovahedronPermutahedron}
%		\input{figures/badFreehedronNotRemovahedronMultiplihedron}
%	}
	\caption{The freehedron obtained as Minkowski sum of the faces of the standard simplex corresponding to initial or final intervals (left), and failed attempts to obtain it as a removahedron of the permutahedron (middle) or of the multiplihedron (right).}
	\label{fig:badFreehedron}
\end{figure}
%
\end{example}

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

\vspace{-1.2cm}
\acknowledgements{
We thank F.~Chapoton for suggesting to look for polytopal realizations of Hochschild lattices.
This work started at the workshop ``Combinatorics and Geometry of Convex Polyhedra'' of the Simons Center for Geometry and Physics in March~2023.
We thank the organizers for this inspiring event, and all participants for the wonderful atmosphere.
}

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



\end{document}
