\documentclass[finalversion]{FPSAC2024}
\articlenumber{60}


\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}

\usepackage{lipsum}

\usepackage{subcaption}

\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{tikz}
\usepackage{url}
\usepackage{graphicx}
\usepackage{mleftright}
\usepackage{color,hyperref}
\usepackage{booktabs}


\newcommand{\vol}{\operatorname{vol}}
\usepackage[textwidth=2.5cm,textsize=small]{todonotes}
\newcommand{\alejandro}[1]{\todo[inline,color=blue!30]{#1 --- Alejandro}}
\newcommand{\Alejandro}[1]{\todo[size=\tiny,color=blue!30]{#1  \hfill --- Alejandro}}
\newcommand{\daniel}[1]{\todo[inline,color=yellow!30]{#1 --- Daniel}}
\newcommand{\Daniel}[1]{\todo[size=\tiny,color=yellow!30]{#1  \hfill --- Daniel}}
\newcommand{\eva}[1]{\todo[inline,color=cyan!30]{#1 --- Eva}}
\newcommand{\Eva}[1]{\todo[size=\tiny,color=cyan!30]{#1  \hfill --- Eva}}
\newcommand{\martha}[1]{\todo[inline,color=purple!30]{#1 --- Martha}}
\newcommand{\Martha}[1]{\todo[size=\tiny,color=purple!30]{#1  \hfill --- Martha}}
\newcommand{\rafael}[1]{\todo[inline,color=deepblue!30]{#1 --- Rafael}}
\newcommand{\Rafa}[1]{\todo[size=\tiny,color=deepblue!30]{#1  \hfill --- Rafa}}


\newtheorem{theorem}{Theorem}[section] 
\newtheorem{proposition}[theorem]{Proposition} 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem*{theorem*}{Theorem}%

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition} 
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{notation}[theorem]{Notation}

\newcommand{\defn}[1]{\emph{\color{blue} #1}} %


\def\NN{\mathbb{N}}
\def\ZZ{\mathbb{Z}}
\def\RR{\mathbb{R}}

\def\cA{\mathcal{A}}
\def\cC{\mathcal{C}}
\def\cD{\mathcal{D}}
\def\cF{\mathcal{F}}
\def\cH{\mathcal{H}}
\def\cI{\mathcal{I}}
\def\cN{\mathcal{N}}
\def\cO{\mathcal{O}}
\def\cR{\mathcal{R}}
\def\cS{\mathcal{S}}
\def\cT{\mathcal{T}}
\def\cU{\mathcal{U}}
\def\cW{\mathcal{W}}

\DeclareMathOperator{\ASC}{ASC}
\DeclareMathOperator{\pos}{pos}
\newcommand{\s}{s}
\DeclareMathOperator{\car}{car}
\DeclareMathOperator{\oru}{oru}
\newcommand{\sizes}[1][\s]{|\!#1\!|} %
\newcommand{\settrees}[1][\s]{\cT_{#1}} %
\newcommand{\spermcombi}[1][\s]{\text{Perm}_{#1}} %
\newcommand{\setperms}[1][\s]{\cW_{#1}} %

\newcommand{\fpol}[1][G]{\cF_{#1}} %
\newcommand{\oruga}[1][n]{\oru_{#1}} %
\newcommand{\Gs}[1][\s]{\oru(#1)} %

\DeclareMathOperator{\route}{R} %
\newcommand{\routep}[1]{\route[#1]} %
\newcommand{\prefix}[2]{{#1}_{[{#2}]}} %
\newcommand{\conv}{\text{conv}}
\DeclareMathOperator{\supp}{\text{supp}} %
\DeclareMathOperator {\inv}{inv}
\DeclareMathOperator {\indeg}{indeg}
\DeclareMathOperator {\outdeg}{outdeg}
\DeclareMathOperator{\height}{h}
\newcommand{\heightDKK}[1][\varepsilon]{\height_{DKK}(#1)}
\newcommand{\triangDKK}[1][G]{\text{Triang}_{DKK}({#1} , \preceq\nolinebreak)} %
\newcommand{\cliques}[1][G]{\text{Cliques}(#1, \preceq)} %
\newcommand{\maxcliques}[1][G]{\text{MaxCliques}(#1, \preceq)} %
\newcommand{\subdivCay}[1][\s] {\text{Subdiv}_{\square}(#1)} %
\newcommand{\spermgeom}[1][\height]{\text{Perm}_{\s}(#1)} %
\newcommand{\troparr}[1][\height]{\cH_{\s}(#1)} %
\newcommand{\Gale}[1][k,m]{\textit{Gale}(#1)} %

\title[Realizing the~\texorpdfstring{$\s$}{}-Permutahedron via Flow Polytopes]
{Realizing the~\texorpdfstring{$\s$}{}-Permutahedron via Flow Polytopes}

\author[R. S. Gonz\'{a}lez D'Le\'{o}n, A. H. Morales, E. Philippe, D. Tamayo Jiménez, and M. Yip]{
Rafael S. Gonz\'{a}lez D'Le\'{o}n\thanks{\href{mailto:rgonzalezdleon@luc.edu}{rgonzalezdleon@luc.edu}}\addressmark{1}, 
Alejandro H. Morales\thanks{\href{mailto:morales_borrero.alejandro@uqam.ca}{morales\_borrero.alejandro@uqam.ca}. AHM is partially supported by NSF grant DMS-2154019.}\addressmark{2}, 
Eva Philippe\thanks{\href{mailto:eva.philippe@imj-prg.fr}{eva.philippe@imj-prg.fr}. EP is supported by grants ANR-21-CE48-0020 of the French National Research Agency ANR (project PAGCAP) and PID2022-137283NB-C21 of the Spanish MCIN/AEI.}\addressmark{3},
Daniel Tamayo Jiménez\thanks{\href{mailto:tamayo@lri.fr}{tamayo@lri.fr}. DTJ is supported by grant ANR-21-CE48-0020 of the French National Research Agency ANR (project PAGCAP).}\addressmark{4}, \and
Martha Yip\thanks{\href{mailto:martha.yip@uky.edu}{martha.yip@uky.edu}. MY is partially supported by Simons collaboration grant 964456.}\addressmark{5}
}

\address{\addressmark{1} Department of Mathematics and Statistics, Loyola University, Chicago IL, USA \\
\addressmark{2} LACIM, D\'epartement de Math\'ematiques, UQAM, Montr\'eal QC, Canada \\
Department of Mathematics and Statistics, UMass Amherst, Amherst MA, USA\\
\addressmark{3} Sorbonne Université and Universitat de Barcelona, CNRS, IMJ-PRG, F-75005 Paris, France \\
\addressmark{4} Université Paris-Saclay, GALaC, Gif-sur-Yvette, France. \\
\addressmark{5} Department of Mathematics, University of Kentucky, Lexington KY, USA}


\received{November 14, 2022}


\abstract{In 2019, Ceballos and Pons introduced the $s$-weak order on $s$-decreasing trees, for any weak composition $s$. They proved its lattice structure and conjectured that it could be realized as the $1$-skeleton of a polyhedral subdivision of a zonotope of dimension~$n-1$. We answer their conjecture in the case where $s$ is a (strict) composition by providing three geometric realizations of the $s$-permutahedron. 
The first one is the dual graph of a triangulation of a flow polytope of high dimension. The second, obtained using the Cayley trick, is the dual graph of a fine mixed subdivision of a sum of hypercubes that has the conjectured dimension. The third, obtained using tropical geometry, is the $1$-skeleton of a polyhedral complex for which we can provide explicit coordinates of the vertices and whose support is a permutahedron as conjectured.}


\keywords{$s$-decreasing tree, $s$-weak order, flow polytope, geometric realization, polyhedral subdivision, Cayley trick, tropical hypersurface.}



\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio_s-permutahedron.bib}

\begin{document}

\maketitle

\section{Introduction}


In \cite{CP20, CP22, CP23}, Ceballos and Pons introduced and studied the $\s$-weak order,  a lattice structure on $\s$-decreasing trees parameterized by a weak composition $\s=(s_1, \ldots, s_n)$. It generalizes the classical weak order on permutations of $[n]:=\{1,\ldots,n\}$, that is recovered with~$\s=(1, \ldots, 1)$. 
Figure~\ref{fig:adjacency_graph_121} shows the Hasse diagram of the $(1,2,1)$-weak order. 

In the same way that the weak order on permutations is related to the Tamari order on Catalan objects, the $\s$-weak order is related to the $\s$-Tamari lattice which has
received a lot of attention under various guises. 
It was first introduced by Préville--Ratelle and Viennot \cite{PRV17} on grid paths weakly above the path $\nu=NE^{s_n}\ldots NE^{s_1}$. %
The Hasse diagram of the $\s$-Tamari lattice was realized as the edge graph of a polyhedral complex by Ceballos et al.~\cite{CPS19}. 
This complex is dual to a subdivision of a subpolytope of a product of simplices called $\cU_{I, \overline{J}}$ and to a fine mixed subdivision of a generalized permutahedron. 
Bell et al.~\cite{vBGDLMCY21} showed that the $\s$-Tamari lattice can also be realized as the graph dual to a triangulation of a flow polytope, by using a method of Danilov, Karzanov, and Koshevoy~\cite{DKK12} for obtaining regular unimodular triangulations. 

\begin{figure}[h!]
    \centering
    \includegraphics[scale=0.65]{dual_graph_triangulation_121_fpsac_2024_v2.pdf}
    \caption{The $\s$-permutahedron for $\s=(1,2,1)$. The vertices are indexed by the following combinatorial objects: $\s$-decreasing trees, Stirling $\s$-permutations, maximal cliques of routes (omitting the all bumps or dips routes), and integer flows (in red on the topmost graph). The edges are oriented according to the $\s$-weak order.
    }
    \label{fig:adjacency_graph_121}
    \vspace{-0.25cm}
\end{figure}





As notation for the rest of this article, let~$\s=(s_1,\ldots,s_n)$ be a composition (\emph{i.e.} a vector with positive integer entries). 
An~\defn{$\s$-decreasing tree} is a planar rooted tree on~$n$ internal vertices (called nodes), labeled by~$[n]$, such that the node labeled~$i$ has~$\s_i+1$ children and any descendant~$j$ of~$i$ satisfies~$j<i$. We denote by~\defn{$T_0^i,\ldots,T_{s_i}^i$} the subtrees of node~$i$ from left to right. The collection of~$\s$-decreasing trees is in bijection with~$121$-avoiding permutations of the word~$1^{s_1}2^{s_2}\ldots n^{s_n}$, called \defn{Stirling~$\s$-permutations}. %
The bijection consists of reading labels along the in-order traversal of $\s$-decreasing trees. 




Let $T$ be an $\s$-decreasing tree and $1\leq x<y\leq n$. We denote by \defn{$\inv(T)$} the multi-set of \defn{tree-inversions} of $T$ formed by pairs $(y,x)$ with multiplicity (also called cardinality)
\[\defn{$\#(y,x)_T$} =\left\{\begin{array}{ll}
    0, & \text{ if } x \text{ is left of } y, \\
    i, & \text{ if } x \in T^y_{i}, \\
    s_y, & \text{ if } x \text{ is right of } y.
    \end{array}\right.\]
An \defn{ascent} on an $\s$-decreasing tree $T$ is a pair $(a,c)$ satisfying
\begin{itemize}[noitemsep]
    \item $a\in T^c_{i}$ for some $0\leq i < s_c$,
    \item if $a < b < c$ and $a\in T^b_{i}$, then $i=s_b$, and
    \item if $s_a>0$, then $T^a_{s_a}$ consists of only one leaf.
\end{itemize}



In \cite{CP20} Ceballos and Pons introduced the \defn{$\s$-weak order $\trianglelefteq$} on $\s$-decreasing trees as follows. For $\s$-decreasing trees $R$ and $T$, we say that $R \trianglelefteq T$ if $\inv(R)\subseteq \inv(T)$.

If $A$ is a subset of ascents of $T$, we denote by \defn{$T+A$} the $\s$-decreasing tree whose inversion set is the smallest one that contains $\inv(T)\cup A$. %
Ceballos and Pons conjectured that the combinatorial complex whose faces are the intervals $[T, T+A]$, which they call the ~\defn{$\s$-permutahedron $\spermcombi$}, has the following geometric structure.

\begin{conjecture}[{\cite[Conj.~1]{CP20}, \cite[Conj.~3.1.2]{CP23}}]\label{conj:s-permutahedron}
Let $\s=(s_1, \ldots, s_n)$ be a weak composition. 
The $\s$-permutahedron can be realized as a polyhedral subdivision of a polytope
which is combinatorially isomorphic to the zonotope $\sum_{1\leq i < j \leq n} s_j  \Delta_{ij}$, where $(e_i)_{1\leq i\leq n}$ is the canonical basis of $\RR^n$ and $\Delta_{ij}$ is the segment $\conv\{e_i, e_j\}$.
\end{conjecture}

\section{Three geometric realizations of the \texorpdfstring{$\s$}{}-permutahedron}\label{sec:realizations}

In the following subsections we provide background on the techniques we use and present our three realizations of the $\s$-permutahedron, finally answering Conjecture~\ref{conj:s-permutahedron} when $\s$ is a composition. 
The proofs are in the long version of this extended abstract~\cite{GMPTY23}.

Examples of the third realization are available on this  \href{https://sites.google.com/view/danieltamayo22/gallery-of-s-permutahedra}{webpage}\footnote{{https://sites.google.com/view/danieltamayo22/gallery-of-s-permutahedra}} and code can be found on this \href{https://cocalc.com/ahmorales/s-permutahedron-flows/demo-realizations}{webpage}\footnote{{https://cocalc.com/ahmorales/s-permutahedron-flows/demo-realizations}}. Figure~\ref{fig:adjacency_graph_121} shows the $(1,2,1)$-permutahedron together with the corresponding combinatorial objects used throughout this work.

\subsection{Triangulations of flow polytopes}\label{sec:subdivisions_flow_polytopes}
Let $G=(V, E)$ be a loopless connected oriented multigraph on vertices $V=\{v_0, \ldots, v_n\}$ with edges oriented from $v_i$ to $v_j$ if $i<j$ such that~$v_0$ (resp.\ $v_n$) is the only source (resp.\ sink) of~$G$. For any vertex $v_i$ we denote by \defn{$\cI_i$} its set of incoming edges and by \defn{$\cO_i$} its set of outgoing edges.

Given a vector $\mathbf{a}=(a_0, a_1 \ldots, a_{n-1}, a_n)$ such that $\sum_i a_i=0$, a \defn{flow} of $G$ with \defn{netflow} $\mathbf{a}$ is a vector $(f_e)_{e\in E}\in (\RR_{\geq 0})^E$ such that $\sum_{e\in \cI_i}f_e + a_i=\sum_{e\in \cO_i}f_e$ for all $i\in [0, n]$. A flow $(f_e)_{e\in E}$ of $G$ is called an \defn{integer flow} if all $f_e$ are integers. 
We denote by \defn{$\mathcal{F}_G^{\mathbb{Z}}({\bf a})$} the set of integer flows of $G$ with netflow $\mathbf{a}$. A \defn{route} of $G$ is a path from $v_0$ to $v_n$ \emph{i.e.} a sequence of edges $((v_0, v_{k_1}), (v_{k_1}, v_{k_2}), \ldots, (v_{k_l}, v_n))$, with $0<k_1<k_2< \ldots <k_l<n$. The \defn{flow polytope} of $G$ is
$$\fpol({\bf a}) = \Big\{ (f_e)_{e\in E} \text{ flow of } G \text{ with netflow } {\bf a} \Big\} \subset \RR^E.$$
It is a polytope of dimension $|E|-|V|+1$. %
When it is not specified, the netflow is assumed to be $\mathbf{a}=(1, 0, \ldots, 0, -1)$. 
In this case, the vertices of $\fpol$ correspond to the routes of $G$.


Flow polytopes admit several nice subdivisions that can be understood via certain combinatorial properties of the graph $G$ with respect to a framing.  
Let $P$ be a route of $G$ that contains vertices $v_i$ and $v_j$. We denote by \defn{$Pv_i$} the prefix of $P$ that ends at $v_i$ and \defn{$v_iP$} the suffix of $P$ that starts at $v_i$.
A \defn{framing $\preceq$} of $G$ is a choice of linear orders $\preceq_{\cI_i}$ and $\preceq_{\cO_i}$ on the sets of incoming and outgoing edges for each inner vertex $v_i$. 
This induces a total order on the set of partial routes from $v_0$ to $v_i$ (resp.\ from $v_i$ to $v_n$) by taking $Pv_i\preceq Qv_i$ if $e_P \preceq_{\cI_j} e_Q$ where $v_j$ is the first vertex after which the two partial routes coincide, and $e_P$, $e_Q$ are the edges of $P$ and $Q$ that end at $v_j$. The definition of~$v_iP\preceq v_iQ$ is similar using~$\preceq_{\cO_j}$. When $G$ is endowed with such a framing $\preceq$, we say that $G$ is \defn{framed}. See Figure~\ref{fig:framed_graph} for an example.

\begin{figure}[!ht]
    \begin{subfigure}[b]{0.55\textwidth}
    \centering
    \includegraphics[scale=0.8]{s-graphs_framing.pdf}
    \caption{}
    \label{fig:framed_graph}
    \end{subfigure}
    \begin{subfigure}[b]{0.4\textwidth}
    \centering
    \includegraphics[scale=0.8]{graph_framing_121.pdf}
    \caption{}
        \label{fig:graph_framing_12}
\end{subfigure}
    \caption{(a) The graph $\Gs$ for $\s=(2,3,2,2)$ with framing in red. %
    (b) The graph $\Gs$ for $\s=(1,2,1)$ with edge labels.}
    \vspace{-6mm}
\end{figure}


We say that routes $P$ and $Q$ of~$G$ are \defn{in conflict} at a common path of inner vertices $[v_i,v_j]$ if the initial parts $Pv_i$ and $Qv_i$ are ordered differently than the final parts $v_jP, v_jQ$. Otherwise we say that $P$ and $Q$ are \defn{coherent} at $[v_i,v_j]$. We say that $P$ and $Q$ are \defn{coherent} if they are coherent at each common inner path.


Defining the sets of mutually coherent routes as the \defn{cliques} of $(G, \preceq)$, we denote by \defn{$\maxcliques$} the set of maximal collections of cliques under inclusion. Given a set of routes $C$ let \defn{$\Delta_C$} be the convex hull of the vertices of $\fpol$ corresponding to the routes in~$C$.



\begin{theorem}[{\cite[Sec. 1]{DKK12}}]\label{thm:DKKsimplices}
The simplices $\{\Delta_C\, |\, C \in \maxcliques\}$ are the maximal cells of a regular triangulation of~$\fpol$.
\end{theorem}

The triangulation obtained this way is called the \defn{DKK triangulation} of $\fpol$ with respect to the framing $\preceq$ and we denote it by \defn{$\triangDKK$}.

Another scheme to subdivide flow polytopes is a recursive procedure by Postnikov and Stanley (see \cite{S00}) based on subdividing $\mathcal{F}_G$ into two polytopes that are integrally equivalent to other flow polytopes. They used this to show that the volume of $\fpol$ equals the number of integer flows in  $\mathcal{F}_G^{\mathbb{Z}}({\bf d})$, where 
 ${\bf d}=(0,d_1,\ldots,d_{n-1},-\sum_i d_i)$ and $d_i=\indeg_G(v_i)-1$. This recursive subdivision can be made compatible with DKK triangulations in what are called \defn{framed Postnikov--Stanley triangulations} \cite{MMS19}. This allows for the following explicit bijection between the maximal cliques and the integer flows. 



\begin{theorem}[{\cite[Thm 7.8]{MMS19}}]
\label{thm:bij_cliques_intflows}
Given a framed graph $(G,\preceq)$, the map \[\Omega_{G,\preceq}: 
\begin{cases}
\maxcliques &\to \mathcal{F}_G^{\mathbb{Z}}({\bf d})\\ 
C &\mapsto (n_C(e)-1)_{e\in E(G)}
\end{cases},\] where $n_C(v_i,v_j)$ is the number of times the edge~$(v_i,v_j)$ appears in the prefixes~$\{Pv_j \mid P \in C\}$, is a bijection between the maximal cliques of~$(G, \preceq)$ and the integer flows in~$\mathcal{F}^{\mathbb{Z}}_G({\bf d})$.
\end{theorem}


We define a framed graph associated to the composition~$\s$ such that the corresponding DKK triangulation encodes the combinatorial structure of the $\s$-weak order.

\begin{definition} \label{def:Gs}
Let $\s=(s_1, \ldots, s_n)$ be a composition, and for convenience of notation set $s_{n+1}=2$.
The framed graph \defn{$(\Gs, \preceq)$} consists of vertices $\{v_{-1},v_0, \ldots, v_n\}$ and
\begin{itemize}[noitemsep]
    \item for $i\in [n+1]$, there are $s_i-1$ \defn{source-edges} $(v_{-1}, v_{n+1-i})$ labeled $e^i_1$, \ldots,  $e^i_{s_{i}-1}$,
    \item for $i\in [n]$, there are two edges $(v_{n+1-i-1}, v_{n+1-i})$ called \defn{bump} and \defn{dip} labeled $e^{i}_0$ and $e^{i}_{s_{i}}$,
    \item the incoming edges of $v_{n+1-i}$ are ordered $e^i_j \prec_{\cI_{n+1-i}} e^i_k$ for $0\leq j < k \leq s_{i}$,
    \item the outgoing edges of $v_{n+1-i}$ are ordered $e^{i-1}_0\prec_{\cO_{n+1-i}} e^{i-1}_{s_{i-1}}$.
\end{itemize}
We denote by \defn{$\Gs$} the \defn{$\s$-oruga graph} and \defn{$\oruga$} the \defn{oruga graph} of length $n$ which is the induced subgraph of $\Gs$ with vertices $\{v_0,\ldots,v_n\}$. Figure~\ref{fig:framed_graph} and Figure~\ref{fig:graph_framing_12} show examples of our construction. The corresponding flow polytope $\fpol[\Gs]$ has dimension $\sizes:=\sum_{i=1}^n s_i$. 
\end{definition}

We describe the routes of $\Gs$ intuitively as follows. 
Every route of $\Gs$ starts from $v_{-1}$, lands in a vertex $v_{n+1-k}$ via a source-edge labeled $e_{t}^k$ and follows $k-1$ edges that are either bumps or dips denoted by a $01$-vector $\delta$. 
 Formally, for $k\in[n+1]$, $t\in [s_k-1]$, and $\delta=(\delta_1, \ldots, \delta_{k-1})\in \{0, 1\}^{k-1}$, we denote by \defn{$\route(k, t, \delta)$} the sequence of edges $(e^{k}_{t_k}, \, e^{k-1}_{t_{k-1}}, \, \ldots, \, e^1_{t_1})$ where 
 $t_k=t$ and $t_j=\delta_j s_j$ for all $j\in [k-1]$.

\begin{theorem}\label{thm:bij_simplices_trees}
The $\s$-decreasing trees are in bijection with the maximal simplices of the DKK triangulation of $\fpol[\Gs]$ with respect to the framing $\preceq$.
\end{theorem}


\begin{proof}
We describe a bijection between $\s$-decreasing trees and integer flows of $\Gs$ with netflow $\mathbf{d}=(0, s_n, s_{n-1}, \ldots, s_1, -\sum_{i=1}^n s_i)$. The statement then follows from Theorems~\ref{thm:bij_cliques_intflows} and~\ref{thm:DKKsimplices}. 

 Given an integer $\mathbf{d}$-flow $(f_e)_e$ of $\Gs$ (note that it is enough to know the values $f_{e_0^i}$ for $i\in [n-1]$ to determine the entire integer flow), we build an $\s$-decreasing tree inductively as follows.
Start with the tree given by the node $n$ and $s_n+1$ leaves. 
At step $i$ for $i \in [n-1]$, we have a partial $\s$-decreasing tree with labeled nodes $n$ to $n+1-i$, and $1+\sum_{k=n+1-i}^{n} s_{k}$ leaves that we momentarily label from $0$ to $\sum_{k=n+1-i}^{n} s_{k}$ along the counterclockwise traversal of the partial tree. 
Attach the next node $n-i$, with $s_{n-i}+1$ pending leaves, to the leaf of the partial tree labeled $f_{e^{n-i}_0}$. 
This procedure produces decreasing trees with the correct number of children at each node. 
Hence, after the $n$-th step we obtain an $\s$-decreasing tree.
Reciprocally, any $\s$-decreasing tree can be built iteratively in this way, so it is associated to a choice of integers $f_{e^i_0}\in [0, \sum_{k=n+1-i}^{n} s_{k}]$ for all $i\in[n-1]$.   
\end{proof}

We can now explicitly describe the DKK maximal cliques of coherent routes in terms of Stirling $\s$-permutations.

\begin{definition}\label{def:route_from_prefix}
Let $\s$ be a composition, and $u$ a (possibly empty) prefix of a Stirling $\s$-permutation.
For all $a\in [n]$, we denote by $t_a$ the number of occurrences of $a$ in $u$, and we denote by $c$ the smallest value in $[n]$ such that $0<t_c<s_{c}$. 
If there is no such value, we set $c=n+1$ and $t_{n+1}=1$. 
The definition of $c$ implies that for all $a<c$, either $t_a=0$ or $t_a=s_a$.
Then we define \defn{$\routep{u}$} to be the route $(e^{c}_{t_c}, \, e^{c-1}_{t_{c-1}}, \, \ldots, \, e^1_{t_1})$.
For example, for the subword $u=3372545$ of $w=33725455716$ we have that $c=5$, $t_5=2,t_4=1,t_3=2,t_2=1,t_1=0$ so $\routep{u}=(e^{5}_{2}, \, e^{4}_{1},e^{3}_{2},e^{2}_{1},e^{1}_{0})=\route(5, 2, (1,1,1,0))$.

Let $w$ be a Stirling $\s$-permutation.
For $i\in [\sizes]$, we denote by \defn{$w_i$} the $i$-th letter of $w$, and for $i\in [0, \sizes]$ we denote by \defn{$\prefix{w}{i}$} the prefix of $w$ of length $i$, with $\prefix{w}{0}:=\emptyset$. 
Let \defn{$\Delta_w$} be the set of routes $\{\routep{\prefix{w}{i}}\, |\, i\in [0, \sizes]\}$ and identify it with the simplex whose vertices are the indicator vectors of these routes.
\end{definition}


Note that each maximal clique always contains the routes $\routep{\prefix{w}{0}}=(e^{n+1}_1, e^n_0, \ldots, e^1_0)=\route(n+1, 1, (0)^n)$ and $\routep{\prefix{w}{\sizes}}=(e^{n+1}_1, e^n_{s_n}, \ldots, e^1_{s_1})=\route(n+1, 1, (1)^n)$.
See Figure~\ref{fig:clique_3221} for the example of $\Delta_w$  corresponding to the Stirling $(1,2,1)$-permutation $w=3221$.

\begin{lemma}[{\cite[Thm.~3.9]{GMPTY23}}]\label{lem:max_clique}
The maximal simplices of $\triangDKK[\Gs]$ are exactly the simplices $\Delta_{w}$ where $w$ ranges over all Stirling $\s$-permutations.
\end{lemma}

The next theorem shows that the triangulation $\triangDKK[\Gs]$ encodes the combinatorics of the $\s$-permutahedron.


\begin{theorem}[{\cite[Thm.~3.18]{GMPTY23}}]\label{thm:bij_interiorfacesDKK_facessperm}
    The face poset of the $\s$-permutahedron $\spermcombi$ is isomorphic (as a poset) to the set of interior simplices of $\triangDKK[\Gs]$ ordered by reverse inclusion.
\end{theorem}

Figure~\ref{fig:adjacency_graph_121} shows the graph dual to the DKK triangulation for $\s=(1,2,1)$, which corresponds to the Hasse diagram of the $(1,2,1)$-weak order.

\begin{figure}[!ht]

 $\routep{\prefix{w}{0}} = {\includegraphics[scale=0.8]{lw0.pdf}},$
 $\routep{\prefix{w}{1}} = {\includegraphics[scale=0.8]{lw1.pdf}}, $
 $\routep{\prefix{w}{2}} = {\includegraphics[scale=0.8]{lw2.pdf}},$

 \[\routep{\prefix{w}{3}} = {\includegraphics[scale=0.8]{lw3.pdf}}, \,
 \routep{\prefix{w}{4}} = {\includegraphics[scale=0.8]{lw4.pdf}}.\]
    \caption{The maximal clique $\Delta_w=\{\routep{\prefix{w}{0}},\ldots,\routep{\prefix{w}{\sizes}}\}$ corresponding to the Stirling $(1,2,1)$-permutation $w=3221$.}
    \label{fig:clique_3221}
    \vspace{-0.6cm}
\end{figure}

\subsection{Cayley trick and mixed subdivisions}\label{sec:Cayley_trick}

The Cayley trick allows us to give another geometric realization of the $\s$-permutahedron as the dual of a fine mixed subdivision of an $(n-1)$-dimensional polytope. This dimension coincides with the dimension of the polyhedral complex conjectured in \ref{conj:s-permutahedron}.

For more details on the Cayley trick, see \cite[Sec.~9.2]{DRS10} for a general introduction and~\cite[Sec.~7]{MM19} for its application on flow polytopes.  
We slightly adapt the work of M\'esz\'aros--Morales for our special case of $\fpol[\Gs]$. 


\begin{definition}
For the polytopes $P_1,\ldots,P_k$ in $\RR^n$ their \defn{Minkowski sum} is the polytope $P_1+\ldots+P_k:=\{\sum x_i\,|\,x_i\in P_i\}$. For the Minkowski sum of $k$ copies of a polytope $P$ we simply write $kP$. 
A \defn{Minkowski cell} is a sum $\sum B_i$ where $B_i$ is the convex hull of a subset of vertices of $P_i$. 
A \defn{mixed subdivision} of a Minkowski sum is a subdivision of their convex hull such that all the cells of the subdivision are Minkowski cells (see \cite[Def.~9.2.5]{DRS10}).
A \defn{fine mixed subdivision} is a minimal mixed subdivision via containment of its summands.

Let $e_1,\ldots,e_k$ be a basis of $\RR^k$. We call the polytope $\cC(P_1,\ldots,P_k):=\emph{conv}(\{e_1\}\times P_1, \ldots, \{e_k\}\times P_k)\subset \RR^{k}\times \RR^n$ the \defn{Cayley embedding} of $P_1,\ldots,P_k$.
\end{definition}


\begin{proposition}[The Cayley trick \cite{HRS00}]\label{prop:cayleytrick}
Let $P_1,\ldots,P_k$ be polytopes in $\RR^n$. The polytopal subdivisions (resp. triangulations) of $\cC(P_1,\ldots,P_k)$ are in bijection with the mixed subdivisions (resp. fine mixed subdivisions) of $P_1+\ldots+P_k$.
\end{proposition}



To apply the Cayley trick to our triangulation $\triangDKK[\Gs]$ of the flow polytope $\fpol[\Gs]$, we need to describe it as the Cayley embedding of some lower-dimensional polytopes. 
Recall that $\fpol[\Gs]$ lives in the space of edges of the graph $\Gs$. We parameterize this space as $\RR^{p} \times \RR^{2n}$, where $p=1 +\sum_{i=1}^n (s_i-1)$ and $\RR^p$ corresponds to the space of source-edges and $\RR^{2n}$ to the space of %
bumps and dips (edges of $\oruga$, see Definition~\ref{def:Gs}).
Moreover, for all $i\in [n]$ and for any point in $\fpol[\Gs]$, (\emph{i.e.}\ a flow of $\Gs$), we have that the sum of its coordinates along edges $e^i_0$ and $e^i_{s_{i}}$ is determined by the coordinates along the source-edges $e^k_t$ for $k\in[i+1, n+1]$, $t\in [s_k-1]$.
Thus, $\fpol[\Gs]$ is affinely equivalent to its projection on the space $\RR^p\times \RR^{n}$ where $\RR^{n}$ corresponds to the space of edges $e^i_0$ for $i\in [n]$.

With this parametrization, the indicator vector of the route of $\Gs$ denoted $\route(k,t,\delta)$ (as in the discussion after Def.~\ref{def:Gs}) with $k\in[n+1]$, $t\in[s_k-1]$ and $\delta\in \{0,1\}^{k-1}$  is
$$e^{k}_{t}\times \sum_{i\in[k-1], \, \delta_i=0} e^i_0.$$ 
Thus, denoting by $\square_{k-1}$ these $(k-1)$-dimensional hypercubes with the set of vertices $\{0,1\}^{k-1}\times 0^{n-k+1}$ embedded in $\RR^{n}$, we see that $\fpol[\Gs]$ is the Cayley embedding of $\square_n$ and $\square_{k-1}$ repeated $s_{k}-1$ times for $k\in [n]$. We denote by \defn{$\subdivCay$} the fine mixed subdivision of the Minkowski sum of hypercubes $\square_{n}+\sum_{i=1}^{n} (s_i-1)\square_{i-1} \subseteq \RR^n$ obtained by intersecting the triangulation $\triangDKK[\Gs]$ %
with the subspace ${\left\{\frac{1}{p}\right\}}^p\times \RR^{n}$.

The following theorem follows directly from the Cayley trick (Proposition~\ref{prop:cayleytrick}), and the isomorphism between the face poset of $\spermcombi$ and the interior simplices of the DKK triangulation given in Theorem~\ref{thm:bij_interiorfacesDKK_facessperm}.


\begin{theorem}[{\cite[Thm.~4.3]{GMPTY23}}]\label{thm:bij_mixed_subdiv}
The face poset of the $\s$-permutahedron $\spermcombi$ is isomorphic to the set of interior cells of $\subdivCay$ ordered by reverse inclusion. In particular, the $\s$-decreasing trees are in bijection with the maximal cells of $\subdivCay$.
\end{theorem}

\begin{figure}[!ht]
\centering
  \begin{subfigure}[b]{0.6\textwidth}
\centering
\includegraphics[scale=0.85]{mixed_cells_example_slim.pdf}
    \caption{}
        \label{fig:mixed_cell_3221}
\end{subfigure}
\qquad 
\begin{subfigure}[b]{0.3\textwidth}
  \centering
\includegraphics[scale=0.6]{mixed_subdivision.pdf}
  \caption{}
    \label{fig:mixed_subdivision}
\end{subfigure}
     \caption{(a) Summands of the Minkowski cell corresponding to $w=3221$ together with their corresponding routes in~$\Delta_w$. (b) Mixed subdivision of $2\square_2+\square_1$ corresponding dually to the $(1,2,1)$-permutahedron. The cells are numbered according to Figure~\ref{fig:adjacency_graph_121}. The highlighted cell in blue corresponds to $w=3221$ as obtained in Figure~\ref{fig:mixed_cell_3221}.}
    \label{fig:comparing flows PS and gen PS}
\end{figure}

\begin{remark}
    We can use a different parameterization of the space where $\fpol[\Gs]$ lives by considering the cube $\square_n$ as the Cayley embedding of two hypercubes $\square_{n-1}$, or equivalently intersect $\RR^n$ with the hyperplane $x_n=\frac{1}{2}$. This allows us to lower the dimension and obtain a fine mixed subdivision of the Minkowski sum of hypercubes $(s_n +1)\square_{n-1}+\sum_{i=1}^{n-1} (s_i-1)\square_{i-1}$. We use this representation in our figures.
\end{remark}

Figure~\ref{fig:mixed_cell_3221} shows the mixed cell corresponding to the Stirling $(1,2,1)$-permutation $w=3221$, obtained from the clique $\Delta_w$ with the Cayley trick.
Figure~\ref{fig:mixed_subdivision} shows the entire mixed subdivision for the case $\s=(1,2,1)$.
Both figures are represented in the coordinate system $(e^2_0, e^1_0)$. 


\subsection{Intersection of tropical hypersurfaces}\label{sec:realization_polyhedral_complex}


In this section, we explain how to dualize our previous realizations in order to obtain our desired polytopal realization and fully answer the conjecture for strict compositions. 
Tropical geometry offers a convenient setting to dualize regular polyhedral subdivisions that interacts nicely with the Cayley trick.

This section is based on the work of Joswig in~\cite{Joswig16} and \cite[Chap.~1]{Joswig21}.
Let $\cA=\{\mathbf{a}^1, \ldots, \mathbf{a}^m\}$ be a point configuration in $\RR^d$ with integer coordinates, and $\cS$ a subdivision of $\cA$. %
The subdivision $\cS$ is said to be \defn{regular} if there is a function $\height: [m]\to \RR, i\mapsto \height^i$ such that the faces of $\cS$ are the images of the lower faces of the lift of $\cA$ (the polytope with vertices $(\mathbf{a}^i, \height^i) \in \RR^{d+1}$ for $i \in [m]$) by the projection that omits the last coordinate. 
In this case, the function $\height$ is called an \defn{admissible height function} for $\cS$.

Such a point configuration together with a height function $\height$ is associated to the \defn{tropical polynomial}~$F(\mathbf{x})=\bigoplus_{i\in [m]} h^i \odot \mathbf{x}^{\mathbf{a}^i}=\min\left\{h^i + \langle \mathbf{a}^i, \mathbf{x}\rangle \, |\, i\in [m] \right\}$ in the min-plus algebra
where $\mathbf{x}\in \RR^d$ and $\langle \cdot, \cdot \rangle$ is the usual scalar product in $\RR^d$. The \defn{tropical hypersurface defined by $F$} is~$\cT(F) := \left\{ \mathbf{x}\in \RR^d\, |\, \text{the minimum of $F(\mathbf{x})$ is attained at least twice}\right\}$
(see examples on Figure~\ref{fig:tropical_hypersurfaces}).
This tropical hypersurface is the image of the codimension-2-skeleton of the \defn{dome}~$\cD(F)=\left\{(\mathbf{x},y)\in \RR^{d+1}\mid \mathbf{x}\in \RR^d, \, y\in \RR, \,  y\leq F(\mathbf{x}) \right\}$ under the orthogonal projection that omits the last coordinate.
The \defn{cells} of $\cT(F)$ are the projections of the faces of $\cD(F)$ (here we include the regions of $\RR^d$ delimited by $\cT(F)$ as its $d$-dimensional cells). We say that $\cT(F)$ is the \defn{tropical dual} of the subdivision $\cS$ with admissible function $\height$ since we have the following theorem.

\begin{theorem}[{\cite[Thm.~1.13]{Joswig21}}]\label{thm:tropical_dual}
There is a bijection between the $k$-dimensional cells of $\cS$ and the $(d-k)$-dimensional cells of $\cT(F)$ that reverses the inclusion order.
\end{theorem}

We showed in \cite[Lem.~5.2]{GMPTY23} that this bijection restricts to a bijection between the interior cells of $\cS$ and the bounded cells of $\cT(F)$.

In the case where $\cA$ is a Cayley embedding, Joswig explains in
~\cite[Cor.~4.9]{Joswig21} how the Cayley trick allows us to describe the tropical dual of a regular mixed subdivision with an arrangement of tropical hypersurfaces. 
We consider $\cA$ given by the vertices of the Cayley embedding $\cC(P_1, \ldots, P_k)$, with $P_j=\conv(\mathbf{a}^{j, 1}, \ldots, \mathbf{a}^{j, m_j})$ being a polytope in $\RR^d$ with integer coordinate vertices, and consider a regular subdivision $\cS$ given by the height $\height=(h^{1,1}, \ldots, h^{1, m_1}, \ldots, h^{k, m_k})\in \RR^{[m_1]\times \ldots \times [m_k]}$. After the Cayley trick we obtain the subdivision $\widetilde{\cS}$ of the point configuration $\widetilde{\cA}$ given by the points  
$\sum_{j=1}^k \mathbf{a}^{j, i_j}$
 for $(i_1, \ldots, i_k)\in [m_1]\times \ldots \times [m_k]$ with height $h^{(i_1, \ldots, i_k)}=\sum_{j=1}^k h^{j, i_j}$. 

\begin{theorem}[{\cite[Cor.~4.9]{Joswig21}}]\label{thm:arrangement_tropical_hypersurfaces}
The tropical dual of the mixed subdivision $\widetilde{\cS}$ obtained after applying the Cayley trick to $\cS$ is the polyhedral complex of cells induced by the arrangement of tropical hypersurfaces $\left\{\cT(F_j) \, |\, j\in [m]\right\}$ where $F_j$ is the tropical polynomial $F_j(\mathbf{x}) =  \bigoplus_{i_j\in [m_j]} h^{j, i_j}\odot \mathbf{x}^{\mathbf{a}^{j, i_j}}$.
\end{theorem}

For example, the arrangement on Figure~\ref{fig:tropical_hypersurfaces} is dual to the mixed subdivision depicted on Figure~\ref{fig:mixed_subdivision}.


\definecolor{ccqqcc}{rgb}{0.8,0,0.8}
\definecolor{qqzztt}{rgb}{0,0.6,0.2}
\definecolor{ttttff}{rgb}{0.2,0.2,1}
\definecolor{cqcqcq}{rgb}{0.75,0.75,0.75}

\begin{figure}[h!]
\centering
\includegraphics[scale=1]{tropical_arr.pdf}
\caption{Arrangement of three tropical hypersurfaces, associated to the tropical polynomials on the right. The bounded cells of this arrangement give a realization of the $(1,2,1)$-permutahedron.}\label{fig:tropical_hypersurfaces}
\end{figure}




Danilov et al.\ provided explicit constructions of admissible height functions for the DKK triangulation (\cite[Lem.~2 \& 3]{DKK12}) that we can adapt to~$\Gs$. 
We refined their results in \cite[Lem.~5.5]{GMPTY23} to prove that the following height function is admissible.

\begin{lemma}[{\cite[Lem.~5.6 and Prop.~5.7]{GMPTY23}}]\label{lem:epsilonheight}
Let $\s$ be a composition and~$0<\varepsilon<\frac{1}{n(1+\sum_{j=2}^n (2s_j+1))}$. 
Consider $\height_{\varepsilon}$ to be the function that associates to a route $\route:=\route(k, t_k, \delta)$ of $\Gs$ the quantity~$\height_{\varepsilon}(\route)=-\sum_{k\geq c > a \geq 1} \varepsilon^{c-a} (t_c+\delta_a)^2$, where $t_c=0$ if $\delta_c=0$ or $t_c=s_c$ if $\delta_c=1$,
 for all $c\in [k-1]$. Then $\height_{\varepsilon}$ is an admissible height function for $\triangDKK[\Gs]$.
\end{lemma}




Since we defined in Subsection~\ref{sec:Cayley_trick} the mixed subdivision $\subdivCay$ from the regular triangulation $\triangDKK[\Gs]$ via the Cayley trick, the following theorem directly follows from Theorem~\ref{thm:arrangement_tropical_hypersurfaces}.


\begin{theorem}[{\cite[Thm.~5.8]{GMPTY23}}]\label{thm:arr_trop_hypersurfaces_s-perm}
The tropical dual of~$\subdivCay$ is the polyhedral complex induced by the arrangement of hypersurfaces~$\troparr:=\left\{\cT(F^k_{t}) \, |\, k\in [2, n+1], \, t\in [s_k-1]\right\}$, where $\height$ is an admissible height function for $\triangDKK[\Gs]$ and 

$\displaystyle F^k_{t}(\mathbf{x})=\bigoplus_{\delta\in\{0,1\}^{k-1}} \height(\route(k, t, \delta)) \odot \mathbf{x}^{\delta} = \min \Biggl\{\height(\route(k, t, \delta)) + \sum_{i\in [k-1]} \delta_i x_i \, |\, \delta\in\{0,1\}^{k-1}  \Biggr\}$.
\end{theorem}

\begin{definition}\label{def:s-perm_geom}
We denote by \defn{$\spermgeom$} the polyhedral complex of bounded cells induced by the arrangement $\troparr$.
\end{definition}

\begin{theorem}[{\cite[Thm.~5.10]{GMPTY23}}]\label{thm:bij_trop_arr}
The face poset of the geometric polyhedral complex $\spermgeom$ is isomorphic to the face poset of the combinatorial $\s$-permutahedron $\spermcombi$.
\end{theorem}

Figure~\ref{fig:tropical_realizations} shows some examples of such realizations of the $\s$-permutahedron. %

\begin{figure}[!ht]
    \centering
    \includegraphics[scale=0.35]{1112tropical.png}
    \includegraphics[scale=0.35]{1222tropical.png}
    \caption{The $(1,1,1,2)$-permutahedron (left) and the $(1,2,2,2)$-permutahedron (right) via their tropical realization.}
    \label{fig:tropical_realizations}
\end{figure}

Moreover, we can describe the explicit coordinates of the vertices of $\spermgeom$. 
For a Stirling $\s$-permutation $w$, $a\in [n]$ and $t\in [s_a]$, we denote $i(a^t)$ the length of the prefix of $w$ that precedes the $t$-th occurrence of $a$. 
As explained in the argument leading to Lemma \ref{lem:max_clique},
this prefix is associated to the route $\routep{\prefix{w}{i(a^t)}}$ in the clique
$\Delta_w$. 

\begin{theorem}[{\cite[Thm.~5.11]{GMPTY23}}]\label{thm:vertices}
The vertex $\mathbf{v}(w)=(\mathbf{v}(w)_a)_{a\in[n]}$ of $\spermgeom$ associated to a Stirling $\s$-permutation $w$ has coordinates~$\mathbf{v}(w)_a = \sum_{t=1}^{s_a} \left(\height(\routep{\prefix{w}{i(a^t)}})-\height(\routep{\prefix{w}{i(a^t)+1}})\right)$.
\end{theorem}


With these explicit coordinates, we obtain the directions of the edges of $\spermgeom$ and show that its support, \emph{i.e.}\ the union of faces of $\spermgeom$, is a polytope combinatorially isomorphic to the $(n-1)$-dimensional permutahedron. 
This completely answers Conjecture~\ref{conj:s-permutahedron} in the case where $\s$ is a composition, as then the zonotope $\sum_{1\leq i<j\leq n}s_j[\mathbf{e}_i,\mathbf{e}_j]$ is combinatorially isomorphic to the $(n-1)$-dimensional permutahedron. 















\acknowledgements{
We thank V. Pons for helpful comments and for proposing this problem in the open problem session of the VIII Encuentro Colombiano de Combinatoria ECCO 2022. 
We also thank J. Bastidas, C. Ceballos, B. Charles, S. Giraudo, A. Padrol,  V. Pilaud, G. Poullot, F. Santos, H. Thomas, Y. Vargas, the combinatorics team of LIGM, and anonymous reviewers for helpful comments and proofreading.
} 


\printbibliography

\end{document}
