%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{76}
\addbibresource{76.bib}

\usepackage[latin1]{inputenc} % accents under linux
%\usepackage{amssymb}
\usepackage{colordvi}
\usepackage{graphicx,tikz}
\usetikzlibrary{patterns,calc}
%\usepackage{vmargin}
\usepackage{todonotes}
%\usepackage{hyperref}
\usepackage{overpic,graphics}
\usepackage{algpseudocode}
\usepackage{enumerate}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{paralist}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}


%% note that the class file already loads {amsmath, amsthm, amssymb}

%%%%%%%%%%%% Environments %%%%%%%%%%%%%%%%%%%%%%%%%
%\numberwithin{equation}{section}
\newtheorem*{Theorem}{Theorem}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{fact}[theorem]{fact}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}{Question}
\newtheorem{conjecture}{Conjecture}
\newtheorem{problem}{Problem}
\newtheorem{note}{Note}
\newtheorem{algo}[theorem]{Algorithm}

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\newtheorem{proofpart}{Part}
\makeatletter
\@addtoreset{proofpart}{theorem}
\makeatother

%Symbols 
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\TP}{{\mathbb T}{\mathbb{P}}}

% math special letters

% math commands
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\reverse}[1]{\overleftarrow{#1}} % reading the black and white sequence backwards


% operators
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\Cat}{Cat} % convex hull
\DeclareMathOperator{\asc}{asc} % convex hull
\DeclareMathOperator{\tasc}{tasc} % number of tamari ascents
\DeclareMathOperator{\inv}{inv} % inversion set
\DeclareMathOperator{\spe}{\sigma} % s-permutation of a s-decreasing tree
\DeclareMathOperator{\card}{\#} % cardinality of inversions

% lattice relations and operations
\newcommand{\wole}{\preccurlyeq} % weak order on decreasing trees
\newcommand{\woless}{\prec}
\newcommand{\tc}[1]{#1^{\mathsf{tc}}} % transitive closure of a relation
\newcommand{\meet}{\wedge} % meet in lattice
\newcommand{\join}{\vee} % join in lattice
\newcommand{\maxs}{\Sigma} % maximal inversion set

%permutahedron and associahedron
\newcommand{\Perm}[1]{\operatorname{Perm}(#1)} % permutahedron
\newcommand{\Asso}[1]{\operatorname{Asso}(#1)} % associahedron

%notation for v-Tamari objects
\newcommand{\vT}{{\mathcal T}} % v-Tamari tree
\newcommand{\vF}{{\mathcal F}} % v-Tamari face
\newcommand{\vA}{{\mathcal A}} % a set of v-ascents

%bijections
\newcommand{\streestovtrees}{{\varphi}} % bijection from s-trees to v-trees


%others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % id est


\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\emph{\darkblue #1}} % emphasis of a definition

% todo
\usepackage{todonotes}
\newcommand{\cesar}[1]{\todo[color=orange!30, inline, size=\footnotesize]{#1  \hfill --- C.}}
\newcommand{\cesarm}[1]{\todo[color=orange!30, size=\tiny]{#1 \\ \hfill --- C.}}
\newcommand{\viviane}[1]{\todo[color=blue!30, inline, size=\footnotesize]{#1  \hfill --- V.}}

% figures
\graphicspath{{figures/}} 


\date{\today}

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


%% define your title in the usual way
\title{The $s$-weak order and $s$-permutahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
Cesar Ceballos\thanks{\href{mailto:cesar.ceballos@univie.ac.at}{cesar.ceballos@univie.ac.at}. Sup. by the Austrian Science Foundation FWF, grant F 5008-N15.}\addressmark{1} 
\and
Viviane Pons\thanks{\href{mailto:viviane.pons@lri.fr}{viviane.pons@lri.fr}\newline \indent \hspace{0.4em}Partially supported by the project ``Austria/France Scientific \& Technological Cooperation'' (Austrian \newline \indent\hspace{0.4em}BMWFW Project No. FR 10/2018 and French PHC Amadeus 2018 Project No. 39444WJ).}\addressmark{2}
%\thanks{This project was partially supported by the project ``Austria/France Scientific \& Technological
%Cooperation'', which is co-financed by the Austrian Federal Ministry of Science, Research and
%Economy BMWFW (Project No. FR 10/2018) and by the French Ministry of Foreign Affairs and
%International Development (PHC Amadeus 2018 Project No. 39444WJ).
%\addressmark{1}CC was supported by the Austrian Science Foundation FWF, grant F 5008-N15, in the framework of the Special Research Program Algorithmic and Enumerative Combinatorics.
}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Faculty of Mathematics, University of Vienna, Vienna, Austria \\ \addressmark{2}LRI, Univ. Paris-Sud - CNRS - Centrale Supelec - Univ. Paris-Saclay, Orsay, France}



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

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
%\abstract{We present a lattice on decreasing trees which generalizes the weak order on permutations. By selecting certain trees, we obtain in particular the $\nu$-Tamari lattice as a sublattice. Beside, we define a polytopal complex related to the lattice. We give conjectures and open questions related to the geometrical realization of the complex.}
\abstract{We introduce the $s$-weak order on decreasing trees, a lattice which generalizes the classical weak order on permutations.
Restricting this lattice to certain trees gives rise to the $s$-Tamari lattice, a sublattice which generalizes the Tamari lattice.
The $s$-weak order and the $s$-Tamari lattice have beautiful underlying geometric structures which we call the $s$-permutahedron and the $s$-associahedron. 
We provide geometric realizations of these objects in dimensions two and three, %as polyhedral subdivisions of certain polytopes,
and conjecture that similar constructions exist in general. 
We also show that our construction is related to the $\nu$-Tamari lattices of Pr\'eville-Ratelle and Viennot.
}

\resumetitle{R\'esum\'e}
%% put your French abstract here, or comment this out if you don't have one
\resume{Nous d\'efinissons le $s$-ordre faible sur les arbres d\'ecroissants : un treillis qui g\'en\'eralise l'ordre faible sur les permutations. En restreignant \`a certains arbres, nous obtenons le treillis de $s$-Tamari, un sous-treillis qui g\'en\'eralise le treillis de Tamari. Ces deux objets ont de jolies structures g\'eom\'e-triques sous-jacentes que nous nommons le $s$-permutoh\`edre et $s$-associa\`edre. Nous donnons les r\'ealisations g\'eom\'etriques de ces objets en dimensions deux et trois et conjecturons que des constructions similaires existent en g\'en\'eral. Par ailleurs, notre travaille est li\'e au treillis de $\nu$-Tamari de  Pr\'eville-Ratelle et Viennot.}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{Weak order, Permutahedron, Metasylvester Lattice, Tamari Lattice, Rational Catalan Combinatorics.}
\keywords{Weak order, Permutahedron, Tamari Lattice, Associahedron.}

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

\begin{document}

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

\section{Introduction}

The weak order is a partial order on the set of permutations of $[n]$, which is defined as the inclusion order of their corresponding inversion sets.
This partial order turns out to be a lattice, whose Hasse diagram can be realized geometrically as the edge graph of a polytope called the permutahedron.
%the classical permutahedron, a well know $(n-1)$-dimensional polytope obtained as the convex hall of all permutations of $[n]$ in~$\mathbb{R}^n$.
Restricting the weak order to the set of $231$-avoiding permutations gives rise to the Tamari lattice, a well-studied lattice whose 
Hasse diagram can be realized as the edge graph of another polytope called the associahedron~\cite{hoissen12associahedra}.
A beautiful realization of the associahedron obtained by removing certain facets of the permutahedron is described by Hohlweg and Lange in~\cite{HohlwegLange}.


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[height= 5cm]{s022_complex.pdf}&
\includegraphics[height= 5cm]{s022_asso.pdf}
\end{tabular}
\caption{The $s$-permutahedron and the $s$-associahedron for $s=(0,2,2)$.
Their edge graphs are the Hasse diagrams of the $s$-weak order and the $s$-Tamari lattice, respectively.}
\label{fig_s022_perm_asso}
\end{center}
\end{figure}

In this article, we introduce a wider generalization of these concepts indexed by a weak composition $s=(s(1),s(2),\dots, s(n))$. 
Our generalizations recover the classical objects for $s=(1,1,\dots,1)$.
The \emph{$s$-weak order} is a partial order on a set of certain trees which we call \emph{$s$-decreasing trees}, 
and is defined as the inclusion order of their \emph{$s$-tree inversions}.
We show that the $s$-weak order has the structure of a lattice (\cref{thm:lattice}), and give a complete characterization of 
its cover relations in terms of a simple combinatorial rule on the trees (\cref{thm:cover-relations}).
Restricting the $s$-weak order to certain trees, which play the role of $231$-avoiding permutations, 
gives rise to a sublattice which we call the $s$-Tamari lattice (\cref{thm:sTamarilattice}).
As in the classical case, the $s$-weak order and the $s$-Tamari lattice possess beautiful underlying geometric structures which are illustrated in \cref{fig_s022_perm_asso}. 
We described them in purely combinatorial terms as potential polyhedral complexes which we call
the \emph{$s$-permutahedron} and the \emph{$s$-associahedron}.  
We conjecture that the $s$-permutahedron can be realized geometrically as a polytopal subdivision of a polytope (\cref{coj:spermutahedra}), and 
that the $s$-associahedron can be obtained from it by removing certain facets (\cref{con:sassociahedra})\footnote{When $s$ contains no zeros except possibly for $s(1)$.}. 
We show that these two conjectures hold in dimensions two and three ($n=3$ and $n=4$ resp.). Some 3-dimensional examples are illustrated in \cref{fig_geometricrealizations_intro}.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc|ccc}
\includegraphics[height= 2cm]{s0222}&
\includegraphics[height= 2cm]{s0222_asso}&
\includegraphics[height= 2cm]{s0222_both} &
\includegraphics[height= 2cm]{s0333}&
\includegraphics[height= 2cm]{s0333_asso}&
\includegraphics[height= 2cm]{s0333_both} \\
%\includegraphics[height= 4.2cm]{s0555}&
%\includegraphics[height= 4.2cm]{s0555_asso}&
%\includegraphics[height= 4.2cm]{s0555_both} \\
\end{tabular}
\caption{The $s$-permutahedron and the $s$-associahedron obtained from it by removing certain facets,  for $s=(0,2,2,2)$ and $s=(0,3,3,3)$.}
\label{fig_geometricrealizations_intro}
\end{center}
\end{figure}

In \cite{PrevilleRatelleViennot}, Pr\'eville-Ratelle and Viennot introduced another generalization of the Tamari lattice called the \emph{$\nu$-Tamari lattice}. 
Its Hasse diagram was recently proved to be realizable as the edge graph of the \emph{$\nu$-associahedron}, 
a polyhedral complex induced by an arrangement of tropical hyperplanes introduced in~\cite{CeballosPadrolSarmiento-geometryNuTamari}.  
We prove that the $\nu$-Tamari lattices and the $\nu$-associahedra are isomorphic to the 
$s$-Tamari lattices and the $s$-associahedra, respectively, 
for specific choices of $\nu$ and $s$ (\cref{thm:sTamari_vTamari,thm:sassociahedron_vassociahedron}).  
This gives a new perspective for the geometric realization problem of $\nu$-associahedra.

%Previous studies on $s$-Catalan combinatorics can be found in~\cite{ceballos_signature_2018}.
The $s$-weak order has been considered in \cite{pons_lattice_2015} for the case $s=(m,\dots, m)$ under the name "metasylvester lattice". 
The results in this paper are more general and we study the objects in consideration from a more geometrical point of view.

%\emph{Acknowledgements: the computation and tests needed along the research were done using the open-source mathematical software \texttt{Sage}~\cite{Sage}.}

\section{The $s$-weak order on decreasing trees}

We denote by $\PP$ the set of positive integers, $\NN$ the set of nonnegative integers and for any 
$n \in \PP$ let $[n]:=\{1,2,\dots,n\}$. A \defn{weak composition} is a finite sequence 
$\mu=(\mu(1),\mu(2),\dots, \mu(n))$ of numbers $\mu(i) \in \NN$. For a weak composition $\mu$ we 
define its \defn{weight} $|\mu|:=\sum_i \mu(i)$ and its \defn{length} $\ell(\mu):=n$. 
%For example for $\mu=(2,0,3,4,0,1)$ we have that $\ell(\mu)=6$ and $|\mu|=10$.
%A \defn{composition} is a weak composition~$\mu$ such that $\mu(i)\ne 0$ for all $i\in [\ell]$, in 
%other words, a composition is a finite sequence of entries in $\PP$. 

\subsection{$s$-decreasing trees}

Let $s=(s(1),s(2),\dots,s(n))$ be a weak composition (with possible zero entries). 
An \defn{$s$-decreasing tree} is a plane rooted tree with $n$ internal nodes labeled from $1$ to $n$, 
such that node~$i$ has $s(i)+1$ children (we write the corresponding subtrees $T_0^i, \dots, T_{s(i)}^i$) and all its descendants have smaller labels (see \cref{fig:ex-dtree}).
%An example is given in Fig.~\ref{fig:ex-dtree}. 
%Note that each node is given a unique label. For practicality, we then write \emph{the node $y$} instead of \emph{the node labeled by $y$}. Our goal is now to define a partial order on $s$-decreasing trees. 
If $s(i)\neq 0$ for all $i$, the $s$-decreasing trees are in bijection with $212$-avoiding permutations of the word $1^{s(1)}2^{s(2)}\dots n^{s(n)}$ (also known as Stirling $s$-permutations), see \eg \cite[Sec.~3.3.1]{ceballos_signature_2018} and the references therein.
%%%%%%%%%%%
%%%%%%%%%%%
%%%All this part was removed
%%%%%%%%%%
%%%%%%%%%%
%\begin{definition}
%\label{def:tree-notations}
%Let $T$ be an $s$-decreasing tree and $y \in T$ with $m = s(y)$, we write $T_0^y, \dots, T_{m}^y$ the children subtrees from left to right of the node $y$. 
%Note that in this definition, a \defn{child} always means the full subtree and not just a node.
%\begin{enumerate}
%\item $T_0^y$ is the \defn{left child} of $y$. If $s(y) > 0$, then $T_0^y$ is a \defn{strict left child} of $y$;
%\item $T_{m}^y$ is the \defn{right child} of $y$. If $s(y) > 0$, then $T_{m}^y$ is a \defn{strict right child} of $y$.
%\item $T_i^y$ for $i \neq 0$ and $i \neq m$ is a \defn{middle child} of $y$.
%\item If $s(y) = 0$ then $T_0^y$ is the \defn{unique child} of $y$.
%\end{enumerate}
%
%Note that a unique child is also both a left and a right child but not a strict left child nor a strict right child. In addition, we say that a node $x$ is
%\begin{itemize}
%\item \defn{right} (resp. \defn{left}) of a node $y$ if $x$ is not a descendant of $y$ and if their first common ancestor $z$ is such that $x \in T_j^z$ and $y \in T_i^z$ with $j > i$ (resp. $j < i$);
%\item \defn{weakly right} (resp. \defn{weakly left}) of a subtree $T_i^y$ if $x \in T_j^y$ with $j \geq i$ (resp. $j \leq i$) or if $x$ is right (resp. left) of $y$.
%\item \defn{strongly right} (resp. \defn{strongly left}) of a a subtree $I_i^y$ if $x \in T_j^y$ with $j > i$ (resp. $j < i$) or $x$ is right (resp. left) of $y$.
%\end{itemize} 
%\end{definition}

%An example is given in Fig.~\ref{fig:ex-dtree}. We have that $3, 2, $ and $1$ are right of $4$ and also strongly right of $T_0^5$ and weakly right of $T_2^5$. 
%
%\begin{remark}
%If $x < y$, then there are only 3 options for $x$: being left of $y$, being a descendant of $y$, being right of $x$. Similarly, for $0 \leq i \leq s(y)$, if $x$ is not weakly right of $T_i^y$ (resp. weakly left), then $x$ is strongly left (strongly right). 
%\end{remark}
%%%%%%%%%%%
%%%%%%%%%%%
%%%%%%%%%%%
%%%%%%%%%%%

\begin{definition}[Tree-inversions]
\label{def:tree-inversions}
%For all $y > x$ in an $s$-decreasing tree $T$, we define the \defn{cardinality} $\card_T(y,x)$ of $(y,x)$ in $T$ by 
Let $T$ be an $s$-decreasing tree and $1\leq x<y\leq n$.
The \defn{cardinality} $\card_T(y,x)$ of $(y,x)$ in $T$ is determined as follows: if $x$ belongs $T_0^y$ or is left of $y$, then $\card_T(y,x) = 0$; if $x \in T_i^y$ with $T_i^y$ a middle child of $y$ (\ie with $0<i<s(y)$), then $\card_T(y,x) = i$; if $x$ belongs to $T_{s(y)}^y$ or is right of $y$, then $\card_T(y,x) = s(y)$.  

This covers all positions of $x$ relatively to $y$. If $\card_T(y,x) > 0$, we say that $(y,x)$ is a \defn{tree-inversion} of $T$, and denote by $\inv(T)$ the multi-set of tree-inversions counted with their cardinalities. When the context is clear, we omit $T$ and simply write $\card(y,x)$.
\end{definition}

%See for example all the tree-inversions corresponding to a given tree in Fig.~\ref{fig:ex-dtree}. Note that in the case where $s(y) =0$ and $x$ is right of $y$, both conditions~\eqref{def-cond:tree-inversion0} and~\eqref{def-cond:tree-inversionr} apply and are consistent with $\card_T(y,x) = 0$. In particular, there is no tree-inversion $(y,x)$ if $s(y) = 0$ even if $x$ is right of $y$. If $s = (m,m, \dots, m)$ with $m > 0$, this definition coincides with the one given in \cite{pons_lattice_2015}. In particular, when $s = (1,1,\dots, 1)$ then the $s$-decreasing trees are decreasing binary trees, in bijection with permutations. In this case, the tree-inversions of $T$ are exactly the inversions of the corresponding permutation. More generally, we consider tree-inversions a natural analogue of classical inversions of permutations. As such, the sets of tree-inversions can be characterized, following some rules very similar to the ones of classical permutations inversions sets.
An example is given in \cref{fig:ex-dtree}. 
Note that if $s(y) =0$ then $\card_T(y,x) = 0$ for every $x<y$. 
If $s = (m,m, \dots, m)$ with $m > 0$, this definition coincides with the one given in \cite{pons_lattice_2015}. 
When $s = (1,1,\dots, 1)$, the $s$-decreasing trees are decreasing binary trees, which are in natural bijection with permutations, 
and tree-inversions are exactly inversions of permutations. 
We will provide a characterization of the sets of tree-inversions in general below.

\begin{figure}[ht]
\begin{center}
\scalebox{.6}{\input{figures/example_def_dtree}}
\end{center}
\caption{An $s$-decreasing tree and its tree-inversions for $s=(0,0,2,1,3)$.}
\label{fig:ex-dtree}
\end{figure}

\begin{definition}
\label{def:multi-inversion-set}
A \defn{multi inversion set} on $1, \dots, n$ is a multi set $I$ of inversions $(y,x)$ with $1 \leq x < y \leq n$. We write $\card_I(y,x)$ for the number of occurrences of $(y,x)$ in $I$. If there is no occurrence of $(y,x)$ in $I$ we write $(y,x) \notin I$ or equivalently $\card_I(y,x) = 0$.

Given two multi inversion sets $I$ and $J$, we say that $I$ is \defn{included} in $J$ (resp. strictly included) and write $I \subseteq J$ (resp. $I \subset J$) if $\card_I(y,x) \leq \card_J(y,x)$ (resp. $\card_I(y,x) < \card_J(y,x)$) for every $1 \leq x < y \leq n$.

Given a weak composition $s$ with $\ell(s) = n$, we denote by $\maxs_s$ the \defn{maximal $s$-inversion set} defined by  $\card_{\maxs_s}(y,x) = s(y)$ for all $1 \leq x < y \leq n$.
\end{definition}

%\begin{definition}
%\label{def:tree-inversion-set}
%Let $s$ be a weak composition with $\ell(s) = n$ and $I \subseteq \maxs_s$ a multi inversion set. Then $I$ is said to be an \defn{$s$-tree-inversion set} if it satisfies the following two rules:
%\begin{itemize}
%\item \defn{Transitivity}: if $a < b < c$ with $\card(c,b) = i$, then $\card(b,a) = 0$ or $\card(c,a) \geq i$.
%\item \defn{Planarity}: if $a < b < c$ with $\card(c,a) = i$, then $\card(b,a) = s(b)$ or $\card(c,b) \geq i$.
%\end{itemize}
%\end{definition}
%
%The transitivity and planarity conditions can be easily understood from the geometric drawing of the tree, as illustrated in Fig.~\ref{fig:transitivity_planarity}. 
%
%\begin{figure}[htbp]
%\begin{center}
%\includegraphics[width = 0.25\textwidth]{transitivity_planarity.pdf}
%\caption{The transitivity and planarity conditions on $s$-tree inversion sets.}
%\label{fig:transitivity_planarity}
%\end{center}
%\end{figure}

\begin{definition}
\label{def:tree-inversion-set}
Let $s$ be a weak composition with $\ell(s) = n$ and $I \subseteq \maxs_s$ a multi inversion set. Then $I$ is said to be an \defn{$s$-tree-inversion set} if it satisfies the following two rules:
\begin{minipage}{0.6\textwidth}
\begin{itemize}
\item \defn{Transitivity}: if $a < b < c$ with $\card(c,b) = i$, then $\card(b,a) = 0$ or $\card(c,a) \geq i$.
\item \defn{Planarity}: if $a < b < c$ with $\card(c,a) = i$, then $\card(b,a) = s(b)$ or $\card(c,b) \geq i$.
\end{itemize}
 \end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{center}
\includegraphics[width = 0.6\textwidth]{transitivity_planarity.pdf}
\end{center}
\end{minipage}
\end{definition}



\begin{proposition}
\label{prop:tree-inversions-bij}
%For $s$ a given weak composition, the set of $s$-decreasing trees is in bijection with the set of $s$-tree-inversions sets. 
$s$-decreasing trees are in bijection with $s$-tree-inversions sets. 
\end{proposition}

%It is quite straightforward to check that for any $s$-decreasing trees, its tree-inversions indeed form an $s$-tree-inversions set. To prove
%the proposition, one then has to construct an $s$-decreasing tree from an $s$-tree-inversion set and check that the tree-inversions of the constructed
%tree match the original set. The construction algorithm is very natural: it starts from the root (always labeled by $n$) and recursively partitions the remaining labels into subsets labeling the subtrees following the tree-inversions.

\subsection{Lattice definition and cover relations}

Tree-inversions are an analogue of permutation inversions. This motivates the following definition of an analogue of the weak order on $s$-decreasing trees.

\begin{definition}
%Let $R$ and $T$ be two $s$-decreasing trees of a same weak composition $s$ with $\ell(s) = n$. We say that $R \wole T$ if 
Let $s$ be a weak composition and $R$ and $T$ be two $s$-decreasing trees. We say that $R \wole T$ if 
%\begin{equation}
%\inv(R) \subseteq \inv(T)
%\end{equation}
$\inv(R) \subseteq \inv(T)$
using the inclusion of multi inversion sets from \cref{def:multi-inversion-set}. We call the relation $\wole$ the \defn{$s$-weak order}.
\end{definition}

%It is immediate to see that this defines a partial order, see Fig.\ref{fig:sweak_lattice} for an example. Note that when $s = (1,1, \dots, 1)$, this is actually the classical weak order on permutations which is known to be a lattice. In the case where $s =(m, m, \dots, m)$, this is the \emph{metasylvester lattice} defined in \cite{pons_lattice_2015}. For general $s$, we can also prove that the $s$-weak order is a lattice. In the case where $s$ does not contain any 0, there is a natural bijection between $s$-decreasing trees and certain multi permutations allowing to the see the $s$-weak order as a sublattice of the weak order, slightly generalizing the results of \cite{pons_lattice_2015}. The more interesting case is when $s$ contains some 0 values. In this case, one needs to re-enact the proof that the weak order is a lattice in a more general settings. The set of multi inversion sets is endowed with a natural lattice structure through inclusion of multisets. We define
It is immediate to see that this defines a partial order, see \cref{fig:sweak_lattice} for some examples. 
Note that when $s = (1,1, \dots, 1)$, this is the classical weak order on permutations which is known to be a lattice. 
In the case where $s =(m, m, \dots, m)$, this is the \emph{metasylvester lattice} defined in \cite{pons_lattice_2015}. 
For general $s$ (possibly including some zero entries), the proof of~\cite{pons_lattice_2015} does not apply. We use the following two operations.

\begin{itemize}
\item the \defn{union} $I \cup J$ of two multi inversion sets $I$ and $J$ is the smallest multi inversion set, in terms of inclusion, 
%such that $I \subseteq I \cup J$ and $J \subseteq I \cup J$;
containing both $I$ and $J$.
\item the \defn{transitive closure} $\tc{I}$ of a multi inversion set $I$ is the smallest transitive multi inversion set, in terms of inclusion, 
%such that $I \subseteq \tc{I}$.
containing $I$.
\end{itemize}
%The union is easy to construct: we have $\card_{I \cup J} (y,x) = \max \left( \card_{I}(y,x), \card_{J}(y,x) \right)$ for all $x < y$. The transitive closure asks for a more technical construction which we do not describe in this extended abstract. By proving that the planarity condition on multi inversion sets is stable through both the union and the transitive closure, we then obtain the following theorem.

\begin{theorem}
\label{thm:lattice}
For any weak composition $s$, the $s$-weak order on $s$-decreasing trees is a lattice. The join of two $s$-decreasing trees $T$ and $R$ is determined by
\begin{equation}
\inv(T \join R) = \tc{ \left( \inv(T) \cup \inv(R) \right) }.
\end{equation}
\end{theorem}

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\includegraphics[height=6cm]{sweaklattice_s002.pdf} &
\includegraphics[height=6cm]{sweaklattice_s012.pdf} &
\includegraphics[height=6cm]{sweaklattice_s022.pdf} \\
$s = (0,0,2)$ & $s = (0,1,2)$ & $s = (0,2,2)$
\end{tabular}

\caption{Examples of $s$-weak lattices.}
\label{fig:sweak_lattice}
\end{center}

\end{figure}

Indeed, planarity is stable through union and transitive closure.
The cover relations of the $s$-weak-order can be described in terms of certain rotations on trees which we call \defn{$s$-tree rotations}. 
Such rotations can be performed along \emph{tree-ascents}, which generalize the classical notion of ascents of a permutation. 
A \defn{tree-ascent} of an $s$-decreasing tree $T$ is a pair $(a,c)$ such that:
%\begin{enumerate}[(i)]
%\item $a$ is a descendant of $c$ which does not belong to the right child of $c$;
%\item if $a$ is a descendant of $b$ with $c > b > a$, then $a$ belongs to the right descendant of~$b$;
%\item if it exists, the strict right child of $a$ is empty. 
%\end{enumerate}
\begin{enumerate}[(i)]
\item $a\in T_i^c$ for some $0\leq i < s(c)$ ($a$ is a non-right descendant of $c$);
\item if $a\in T_i^b$ and $c > b > a$, then $i=s(b)$ ($a$ is a right descendant of $b$);
\item if $s(a)>0$, then $T_{s(a)}^a$ is empty (strict right descendant of $a$ is empty).
\end{enumerate}


Having a tree-ascent $(a,c)$ means that we can move the tree rooted in $a$ along the node $c$. 
The tree rooted in $a$ needs to have no strict right child. It will move, taking along its middle children but not its left child. 
This can be expressed formally by the \defn{$s$-tree rotation}: we increase the cardinality $\card(c,a)$ by one and take the transitive closure of the obtained multi inversion set. We write the new multi inversion set $\tc{\left( \inv(T) + (c,a) \right)}$ and prove that it is indeed a tree-inversion set. The corresponding tree is called the \defn{$s$-tree rotation} of $T$ along $(a,c)$.

\begin{theorem}
\label{thm:cover-relations}
The cover relations of the $s$-weak order are in correspondence with $s$-tree rotations. 
\end{theorem}





\section{The $s$-Tamari lattice and the $\nu$-Tamari lattice}

\subsection{The $s$-Tamari lattice}

\begin{definition}
An $s$-decreasing tree $T$ is called an \emph{$s$-Tamari tree} if for any $a<b<c$ 
%the number of~$(c,a)$ inversions is less than or equal to the number of~$(c,b)$ inversions: 
\[
\card_T(c,a)\leq \card_T(c,b).
\]
In other words, the labels in $T^c_i$ are smaller than all the labels in $T^c_j$ for $i<j$\footnote{This is a natural generalization of $231$-avoiding permutations for $s$-decreasing trees.}.
The multi set of inversions of an $s$-Tamari tree is called an $s$-Tamari inversion set.
\end{definition}

\begin{theorem}
\label{thm:sTamarilattice}
The collection of $s$-Tamari trees forms a sublattice of the $s$-week order, which we call the \defn{$s$-Tamari lattice}.
\end{theorem}

%\subsection{Cover relations}
An example is given in \cref{fig_bijection_sTamarivTamari}. Similarly as in the $s$-weak order, 
the cover relations of the $s$-Tamari lattice can be described in terms of certain tree rotations. We say that $(a,c)$ is an \defn{$s$-Tamari-ascent} of $T$ is $a$ is a non-right (direct) child of $c$. As before, we can compute the multi inversion set $\tc{\left( \inv(T) + (c,a) \right)}$. We prove that this corresponds to an $s$-Tamari tree which we call the \defn{$s$-Tamari rotation} of $T$ along $(a,c)$. Basically, $a$ is still moving along $c$ but now it takes along its middle children and strict right child. 

\begin{theorem}
\label{thm:sTamaricoverrelations}
The cover relations of the $s$-Tamari lattice are in correspondence with $s$-Tamari rotations.
\end{theorem}


\subsection{Isomorphism with the $\nu$-Tamari lattice}
\label{sec_sTamarivTamari}
We will show that the $s$-Tamari lattice is isomorphic to the $\nu$-Tamari lattice introduced by Pr\'eville-Ratelle and Viennot in~\cite{PrevilleRatelleViennot}. 
We recall the definition of this lattice in terms of certain combinatorial objects called $\nu$-trees following~\cite{ceballos_vtamarivtrees_2018}.

Let $\nu$ be a lattice path in the plane which starts at the origin and consists of a finite number of north and east unit steps. 
We denote by $A_\nu$ the set of lattice points weakly above $\nu$ inside the smallest rectangle containing $\nu$. We say that two points $p,q \in A_\nu$ are \defn{$\nu$-incompatible} if and only if $p$ is southwest or northeast of $q$ and the south-east corner of the smallest rectangle containing $p$ and $q$ is weakly above $\nu$. Otherwise, we say that $p$ and $q$ are \defn{$\nu$-compatible}.

\begin{definition}
A \defn{$\nu$-tree} is a maximal set of pairwise $\nu$-compatible elements in $A_\nu$.
\end{definition}

Each $\nu$-tree can be regarded as a rooted binary tree: each vertex is connected to the next vertex to its right if any, and to the next vertex below it if any. 
%The result is a rooted binary tree with the root a the top left corner of~$A_\nu$.
This gives an identification between $\nu$-trees and rooted binary trees~\cite[Lem.~2.4]{ceballos_vtamarivtrees_2018}.

Let $p,q,r$ be three vertices of a $\nu$-tree $\vT$, such that $q$ lies below $p$ and to the left of $r$.
Then $q$ may be exchanged by the vertex $q'$ located to the right of $p$ and above~$r$, creating a new $\nu$-Tamari tree $\vT'$. 
In such a case, $q$ is called a \defn{$\nu$-ascent} of $T$, and exchanging $q$ by $q'$ is called a \defn{$\nu$-Tamari rotation}. 
The \defn{$\nu$-Tamari lattice} is the lattice of $\nu$-trees whose cover relations are $\nu$-Tamari rotations.
An example is shown in \cref{fig_bijection_sTamarivTamari}.

%Let $s=(s(1),\dots,s(n))$ be a weak composition and denote by $\nu(s)$ the lattice path $\nu(s):=NE^{s(1)}\dots NE^{s(n)}$. 
%We also denote by $\reverse s$ the reversed sequence $(s(n),\dots,s(2),s(1))$ and fix $\nu=\nu(\reverse s)$. 
Let $s=(s(1),\dots,s(n))$ be a weak composition and denote by $\nu(s)$ the lattice path $\nu(s):=NE^{s(n)}\dots NE^{s(1)}$. 
From now on we fix $\nu=\nu(s)$. %Note that the number of vertices in every $s$-tree is equal to the number of vertices in every $\nu$-tree for this choice of $\nu$. 
By~\cite[Lem.~2.11]{ceballos_vtamarivtrees_2018}, all $\nu$-trees have exactly $1+s(1)+\dots+s(n)$ vertices, which is the number of vertices of every $s$-tree. 

Let $T$ be an $s$-Tamari tree. We say that its vertices (internal nodes and leaves) are traversed from \emph{right-to-left} 
if we visit the root $r$ first and then traverse from right-to-left each of the trees $T^r_i$ such that $T^r_i$ is visited before~$T^r_j$ for $i>j$.  
We label the vertices of $T$ with the numbers $0,1,\dots ,n$, such that a vertex $u$ has label~$i$ if the number of internal nodes traversed strictly before $u$ is equal to $i$. We denote by $\streestovtrees(T)$ the unique $\nu$-tree containing as many vertices with $y$-coordinate equal to~$i$ as there are vertices in $T$ with label $i$. Such a $\nu$-tree can be uniquely constructed using the right flushing algorithm described in~\cite[Section~3.2]{ceballos_vtamarivtrees_2018}. See \cref{fig_bijection_sTamarivTamari} for an illustration.
%$\streestovtrees$

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[width=.39\textwidth]{bijection_stree_nutree.pdf} \quad& \quad
\includegraphics[width=.39\textwidth]{stamlattice_s022_nutree.pdf}\\
right-to-left traversal & $\nu(s)=NE^2NE^2NE^0$
\end{tabular}
\caption{The $s$-Tamari lattice and the $\nu({s})$-Tamari lattice for $s=(0,2,2)$.}
\label{fig_bijection_sTamarivTamari}
\end{center}
\end{figure}


\begin{theorem}
\label{thm:sTamari_vTamari}
The map $\streestovtrees$ is isomorphism between the $s$-Tamari lattice and the $\nu(s)$-Tamari lattice.
\end{theorem}



\section{The $s$-Permutahedron}
%The Hasse diagram of the classical weak order can be geometrically realized as the edge graph of the permutahedron, a convex polytope obtained as the convex hull of all permutations of $[n]$ in $\mathbb R^{n}$. In this section we conjecture that a similar statement holds for any $s$-weak order, namely that its Hasse diagram can be realized as the edge graph of a polytopal subdivision of a polytope. This polytope is a classical permutahedron if $s$ contain no zeros (except at the first entry), or a more general zonotope otherwise. Before stating the precise conjecture we will define the $s$-permutahedron as a purely polyhedral complex. 

Let $T$ be an $s$-decreasing tree and $A$ be a subset of tree-ascents of $T$. We will denote by $T+A$ the $s$-decreasing tree with inversion set $\tc{(\inv(T)+A)}$.  

 \begin{definition}[The $s$-permutahedron]
 The \defn{$s$-permutahedron} $\Perm{s}$ is the complex\footnote{We have strong indications that it is a polyhedral complex, which we should prove in a longer version of this abstract.} whose faces are pairs $(T,A)$ where $T$ is an $s$-decreasing tree and $A$ is a subset of tree-ascents of $T$. The dimension of $(T,A)$ is equal to $|A|$. In particular, 
 \begin{enumerate}
\item the vertices of $\Perm{s}$ are $s$-decreasing trees T, and
\item two trees $T$ and $T'$ are connected by an edge if they are related by an $s$-tree rotation. 
\end{enumerate} 
 The face $(T,A)$ is contained in $(T',A')$ if and only if $[T,T+A]\subseteq [T',T'+A']$ as intervals in the $s$-weak order. %\footnote{In a longer version of this abstract we will explain how this yields a polyhedral complex.}
 See an example in \cref{fig_s022_perm_asso}.
 \end{definition}

\begin{proposition}
The $f$-vector of %the $s$-permutahedron 
$\Perm{s}$ is 
%given by 
the coefficient vector of
\[
\sum_{T} (1+t)^{\asc(T)},
\]
where the sum ranges over all $s$-decreasing trees $T$ and $\asc(T)$ denotes the number of $s$-tree ascents of $T$. 
\end{proposition}

The polynomial 
$
E(s)=\sum_{T} t^{\asc(T)}
$
may be regarded as an $s$-generalization of the Eulerian polynomials, since they coincide for $s=(1,\dots,1)$.

The Hasse diagram of the $s$-permutahedron seems to be realizable as the edge graph of a polytopal subdivision of a polytope. This polytope should be combinatorially isomorphic to the zonotope  
\begin{equation}\label{eq_zonotope}
Z(s) = \sum_{1\leq i < j \leq n} s(j)\Delta_{ij},
\end{equation}

where $\Delta_{ij}=\conv\{e_i,e_j\}\subset \mathbb R^n$. In particular, if $s$ has no zeros (except possibly for~$s(1)$) then $Z(s)$ is combinatorially an $(n-1)$-dimensional permutahedron.

\begin{conjecture}
\label{coj:spermutahedra}
The $s$-permutahedron can be realized as a polyhedral subdivision of a polytope which is combinatorially isomorphic to $Z(s)$. 
\end{conjecture}


\section{The $s$-associahedron and the $\nu$-associahedron}

\subsection{The $s$-associahedron}
Let $T$ be an $s$-Tamari tree and $A$ be a subset of Tamari-ascents of $T$. 
For simplicity, we will denote by $T+A$ the $s$-Tamari tree with inversion set $\tc{(\inv(T)+A)}$.  

 \begin{definition}[The $s$-associahedron]
 The \defn{$s$-associahedron} $\Asso{s}$ is the polyhedral complex\footnote{This follows from \cref{thm:sassociahedron_vassociahedron} and \cite[Thm.~5.2]{CeballosPadrolSarmiento-geometryNuTamari}.} whose faces are pairs $(T,A)$ where $T$ is an $s$-Tamari tree and $A$ is a subset of Tamari-ascents of $T$. The dimension of $(T,A)$ is equal to $|A|$. In particular, 
 \begin{enumerate}
\item the vertices of $\Asso{s}$ are $s$-Tamari trees $T$, and
\item two $s$-Tamari trees are connected by an edge if they are related by an $s$-Tamari rotation. 
\end{enumerate} 
 The face $(T,A)$ is contained in $(T',A')$ if and only if $[T,T+A]\subseteq [T',T'+A']$ as intervals in the $s$-Tamari lattice. See an example in \cref{fig_s022_perm_asso}.
 \end{definition}

\begin{proposition}
The $f$-vector of 
%the $s$-associahedron 
$\Asso{s}$ is 
%given by 
the coefficient vector of
\[
\sum_{T} (1+t)^{\tasc(T)},
\]
where the sum ranges over all $s$-Tamari trees $T$ and $\tasc(T)$ denotes the number of $s$-Tamari ascents of~$T$. 
\end{proposition}

The entries of $\sum_{T} t^{\tasc(T)}$ may be regarded as $s$-generalizations of the Narayana numbers. The $s$-Narayana numbers have already been considered in~\cite{CeballosPadrolSarmiento-geometryNuTamari,ceballos_signature_2018} in this general set up, and in~\cite{ArmstrongRhoadesWilliams2013} for the special case of rational Catalan combinatorics. 

\begin{conjecture}
\label{con:sassociahedra}
If $s$ has no zeros (except for $s(1)$), there exists a geometric realization of $\Perm{s}$ such that $\Asso{s}$ can be obtained from it by removing certain facets.\footnote{If $s$ contains zeros other than $s(1)$ then $\Asso{s}$ is not convex (\cref{thm:sassociahedron_vassociahedron} and \cite[Cor.~5.13]{CeballosPadrolSarmiento-geometryNuTamari}).}
\end{conjecture}



\subsection{Isomorphism with the $\nu$-associahedron}
It was shown in~\cite{CeballosPadrolSarmiento-geometryNuTamari} that the Hasse diagram of the $\nu$-Tamari lattice can be realized as the edge graph of a polyhedral complex, called the $\nu$-associahedron. We recall its definition following the conventions in~\cite{ceballos_vtamarivtrees_2018}.

Let $\nu$ be a lattice path as before. A \defn{$\nu$-face} is a pairwise $\nu$-compatible subset of~$A_\nu$. A $\nu$-face $\vF$ is said to be \defn{covering} if it contains the top left corner in~$A_\nu$ and at least one point in each row and each column.     

\begin{definition}
The \defn{$\nu$-associahedron} $\Asso{\nu}$ is the polyhedral complex of covering $\nu$-faces ordered by reverse inclusion. The dimension of a covering $\nu$-face $\vF$ is $\ell(\nu)+1-|\vF|$, where $\ell(\nu)$ is the length of $\nu$.  
In particular,
 \begin{enumerate}
\item the vertices of $\Asso{\nu}$ are $\nu$-trees, and
\item two $\nu$-trees are connected by an edge if they are related by a $\nu$-Tamari rotation. 
\end{enumerate} 
\end{definition}

Before matching the definitions of $s$-associahedra and $\nu$-associahedra we need the following lemmas.

\begin{lemma}
\label{lem_vfaces1}
Covering $\nu$-faces $\vF$ are in bijection with pairs $(\vT,\vA)$ such that  $\vT$ is a $\nu$-tree and~$\vA$ is a subset of $\nu$-ascents of $\vT$. The bijection is determined by $\vF=\vT\smallsetminus \vA$ and~$\dim(\vF)=|\vA|$.
\end{lemma}

For $a\in \vA$ we denote by $\vT_a$ the $\nu$-tree obtained from $\vT$ by applying a $\nu$-Tamari rotation at the $\nu$-ascent~$a$, and by $\vT+\vA$ the join of the set $\{\vT_a: a\in\vA\}$. 

\begin{lemma}
\label{lem_vfaces2}
%Let $\vF,\vF'$ be two covering $\nu$-faces and $(\vT,\vA),(\vT',\vA')$ be their corresponding pairs of $\nu$-trees with a subset of $\nu$-ascents. Then $\vF\supseteq\vF'$ if and only if $[\vT,\vT+\vA]\subseteq [\vT',\vT'+\vA']$ as intervals in the $\nu$-Tamari lattice.
Let $(\vT,\vA)$ and $(\vT',\vA')$ be two pairs of a $\nu$-tree with a subset of $\nu$-ascents, 
and let $\vF=\vT\smallsetminus \vA$ and $\vF'=\vT'\smallsetminus \vA'$ be their corresponding covering $\nu$-faces.
Then $\vF\supseteq\vF'$ if and only if $[\vT,\vT+\vA]\subseteq [\vT',\vT'+\vA']$ as intervals in the $\nu$-Tamari lattice.
\end{lemma}
%\cesar{Cesar writes the proof of the previous two lemmas}

The bijection $\streestovtrees$ between $s$-Tamari trees and $\nu(s)$-trees described in \cref{sec_sTamarivTamari} extends naturally to a bijection $\overline \streestovtrees$ between the faces of the $s$-associahedron and the faces of the $\nu(s)$-associahedron. For each pair $(T,A)$ of an $s$-Tamari tree $T$ and a subset $A$ of Tamari-ascents of $T$, we can associate a pair $(\vT,\vA)$ of a $\nu$-tree $\vT=\streestovtrees(T)$ and a subsets $\vA$ of $\nu$-assents of $\vT$ corresponding to $A$. We denote by $\overline \streestovtrees$ the map that sends the pair $(T,A)$ to $(\vT,\vA)$. 
\cref{lem_vfaces1,lem_vfaces2} imply the following result.

\begin{theorem}
\label{thm:sassociahedron_vassociahedron}
The map $\overline \streestovtrees$ is an isomorphism between $\Asso{s}$ and $\Asso{\nu(s)}$.
\end{theorem}



\section{Geometric realizations in dimensions 2 and 3}

There is a natural way of assigning coordinates to each $s$-decreasing tree. 
Let $e_{ij}:= e_i-e_j$ for $i<j$, where $e_1,\dots ,e_n\in \R^n$ are the standard basis vectors in $\R^n$. 
Let $s=(s(1),s(2),\dots,s(n))$ be a weak composition, $T$ be an $s$-decreasing tree and $A$ be a subset of tree-ascents of $T$. We define

\begin{equation*}
v_T = \sum_{i<j} \card_T(j,i) e_{ij} \quad \text{and} \quad 
F_{(T,A)}= \conv\{v_{T'}: T'\in [T,T+A]\}.
\end{equation*}

%In dimension 2, this gives a realization of the $s$-permutahedron. Some examples are shown in Fig.~\ref{fig:s-perm_dim2}. 
For $n=3$ and $s(3)\neq 0$, this gives a 2-dimensional realization of the $s$-permutahedron in the  subspace $\{(x_1,x_2,x_3)\in\R^3: x_1+x_2+x_3=0\}\subset \R^3$, see \cref{fig:s-perm_dim2}. 
This realization ``cuts'' a polygon (a hexagon if $s_2\neq 0$ or a quadrilateral if $s(2)=0$) into smaller polygons. Each polygon is convex and corresponds to one facet of the $s$-permutahedron. 

\begin{figure}[htbp]
\begin{center}
\scalebox{.7}{
\begin{tabular}{cccc}
\includegraphics[height=2cm]{s002.pdf} &
\includegraphics[height=2cm]{s012.pdf} &
\includegraphics[height=2cm]{s022.pdf} &
\includegraphics[height=2cm]{s043.pdf} \\
$s = (0,0,2)$ & $s = (0,1,2)$ & $s = (0,2,2)$ & $s = (0,4,3)$   
\end{tabular}
}

\caption{Some geometric realizations of $s$-permutahedra in dimension~2.}
\label{fig:s-perm_dim2}
\end{center}
\end{figure}

%One would hope that this construction directly extends to other dimensions, but it is not the case. 
%In dimension 3 (and beyond), even though the permutahedron is still cut into identifiable pieces, those pieces do not form convex polytopes. 
One would hope that this construction directly extends to higher dimensions, but it is not the case. 
For $n\geq 4$, the convex hull of all $v_T$'s is the zonotope $Z(s)$ from~\eqref{eq_zonotope}, which is still cut into identifiable pieces; however, those pieces do not form convex polytopes. 
We were able to fix this realization in dimension 3 ($n=4$ and $s(4)\neq 0$), using a procedure illustrated in \cref{fig:fix-d3}. The first image shows the direct realization obtained by $v_T$: 
we notice some bent edges and can identify what we call a ``broken pattern'' in trees related to those edges. 
The solution is to push the selected trees into a given direction by a parameter given by a broken pattern itself. 
In certain compositions $s$, this push leads to a ``collision'' (see middle of \cref{fig:fix-d3}) which again forces us to push certain trees further away. 
The process can be explicitly described for dimension 3. 
The new coordinates are given by 
$\overline v_T = \sum_{i<j} (3\card_T(j,i) + f_T(j,i)) e_{ij}$
where $f_T(j,i)=0$ for $j \neq 3$ and 
\begin{equation*}
f_T(3,i) = \begin{cases}
0 & \mbox{if }\card_T(3,i) = 0, \\
s_3 + \left( \card_T(4,1) - \card_T(4,3) \right) + \left(\card_T(4,2) - \card_T(4,3) \right) & \mbox{if } 0 < \card_T(3,i) < s_3, \\
2 s_3 & \mbox{if } \card_T(3,i) = s_3.
\end{cases}
\end{equation*}
See \cref{fig_geometricrealizations_intro} for examples. You can find 3-dimensional animations of these polyhedral subdivisions and more in  \href{https://www.lri.fr/~pons/static/spermutahedron/}{this webpage}\footnote{https://www.lri.fr/\~{}pons/static/spermutahedron/}.
We conjecture that such a construction also exists for higher dimensions.


\begin{figure}[htbp]
\begin{center}
\begin{tabular}{ccc}
\includegraphics[height=3.5cm]{broken.pdf} &
\includegraphics[height=3.5cm]{collision.pdf} &
\includegraphics[height=3.5cm]{s0333.png}
\end{tabular}

\caption{Construction of a 3 dimensional realization.}
\label{fig:fix-d3}
\end{center}
\end{figure}

Once we have a geometric realization of the $s$-permutahedron, we are able to identify what we call \defn{Tamari-valid} faces and 
construct a realization of the $s$-associahedron by removing faces of the $s$-permutahedron. This works for both our $2D$ and $3D$ realizations,
and is an analogue of a construction in~\cite{HohlwegLange} giving rise to Loday's realization of the associahedron.
The process is illustrated in \cref{fig:s022_asso} in $2D$, see \cref{fig_geometricrealizations_intro} for $3D$ examples.

\begin{figure}[htbp]
\begin{center}
\begin{tabular}{cc}
\includegraphics[height=1.5cm]{s022_valid.png} &
\includegraphics[height=1.5cm]{s022_asso_construct.png} 
\end{tabular}

\caption{Realization of $s$-Associahedron for $s = (0,2,2)$.}
\label{fig:s022_asso}
\end{center}
\end{figure}



\acknowledgements{The computation and tests needed along the research were done using the open-source mathematical software \texttt{Sage}~\cite{Sage}.}


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

\sloppy
\printbibliography
\fussy


\end{document}
