% 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]{FPSAC2025}
\articlenumber{40}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc
\appto\bibfont{\setlength{\emergencystretch}{1em}}
%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{comment}
\usepackage{thm-restate}
\usepackage{amsfonts}
\usepackage{url}
%\usepackage{enumerate, paralist}
%\usepackage[shortlabels]{enumitem}%with that package references to items automatically include delimiters
\usepackage{units}
\usepackage{tikz}
% \usepackage{dingbat} %for eye-symbol
\usepackage{mathtools}  


\usepackage{paralist}  
\usepackage{subcaption}

\usepackage[english]{babel}
\addto\extrasenglish{
  \def\subsectionautorefname{Subsection}
}
\addto\extrasenglish{
  \def\sectionautorefname{Section}
}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\DeclareMathOperator*{\argmax}{arg\!\max}


\usepackage{lipsum}

%% define your title in the usual way
\title[]{Poset Permutahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author{\texorpdfstring{Alexander E. Black \thanks{\href{mailto:alexander.black@math.ethz.ch}{alexander.black@math.ethz.ch}. Alexander E. Black was partially supported by the NSF GRFP}\addressmark{1}, Sophie Rehberg \thanks{\href{mailto:s.rehberg@fu-berlin.de}{s.rehberg@fu-berlin.de}. Sophie Rehberg was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).}\addressmark{2}, 
\and Raman Sanyal\addressmark{3}}{Alexander E. Black , Sophie Rehberg , 
and Raman Sanyal}}%[Optional shorter names]

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1} Institute for Mathematical Research, ETH Z\"{u}rich \\ \addressmark{2} Department of Mathematics, Freie Universit\"{a}t Berlin \\ \addressmark{3} Department of Mathematics, Goethe-Universit\"{a}t Frankfurt}

%% 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{
% Order polytopes are fundamental families of polytopes in geometric combinatorics given by intersecting the hypercube with the order cone.
% We introduce a new family of polytopes associated to a poset called poset permutahedra given by intersecting the permutahedron with the order cone.
% Special cases of poset permutahedra have occurred in disparate areas such as colorful subdivisions of polygons and partitioned permutahedra recently introduced by Horiguchi et al. in the context of Hessenberg varieties and representation theory.
% As with order polytopes, the combinatorics of the face lattice and volume may be read off entirely from the underlying poset.
% Unlike order polytopes, poset permutahedra are simple if and only if the Hasse diagram of the underlying poset is a forest. 
% The lattice points may be interpreted as poset generalization of Landau's classical score sequences for tournaments. 
% To prove our results, we show that poset permutahedra arise from order polytopes via the fiber polytope construction of Billera and Sturmfels.
% % We conclude by observing the partitioned permutahedra recently introduced by Horiguchi et al. in the context of Hessenberg varieties and representation theory are special cases of our construction and offer new insight into their combinatorics. 
Poset permutahedra are an amalgamation of order polytopes and permutahedra. We show that poset
permutahedra give a unifying perspective on several recent classes of polytopes that occurred, for
example, in connection with colorful subdivisions of polygons and Hessenberg varieties. As with
order polytopes, the geometry and the combinatorics of poset permutahedra can be completely
described in terms of the underlying poset. As applications of our results, we give a combinatorial
description of the $h$-vectors of the partitioned permutahedra of Horiguchi et al. and
poset generalizations of Landau's score sequences of tournaments.  To prove our results, we show that
poset permutahedra arise from order polytopes via the fiber polytope construction of Billera and
Sturmfels.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Order Polytopes, Fiber Polytopes, Monotone Path Polytopes, Score Sequences} % 3-6 keywords

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

%---------------------------------------------------------------
%--------------------------------------------------------------


\newcommand\preceqdot{\mathrel{\ooalign{$\preceq$\cr
  \hidewidth\raise0.225ex\hbox{$\cdot\mkern0.5mu$}\cr}}}
%\newcommand\cov{\prec\!\!\!\bullet}%
\newcommand\cov{\lessdot}%

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\conv}{\mathrm{conv}}
\newcommand{\dist}{\mathrm{dist}}
\newcommand{\Ind}{\mathrm{I}}
\newcommand{\KG}{\mathrm{KG}}

%%%% some notation macros -------
\newcommand{\poset}{\mathcal{P}} %  a poset P
\newcommand{\qoset}{\mathcal{Q}} %  another poset Q
\newcommand{\chain}{\mathcal{C}} % a chain C
\newcommand{\antichain}{\mathcal{A}} % a antichain A
\newcommand{\chains}[1]{\mathfrak{C}({#1})} % set of connected chains of a poset (one mandatory argument)
\newcommand{\fil}{\mathcal{F}} % a filter
\newcommand{\gil}{\mathcal{G}} % an other filter
\newcommand{\filters}[1]{\mathfrak{F}({#1})} % set of filters of a poset (one mandatory argument)
\newcommand{\id}{\mathcal{I}} % an ideal
\newcommand{\linex}[1]{\mathfrak{L}(#1)} % the set of linear extensions of a poset (one mandatory argument)
\newcommand{\birk}[1]{\mathfrak{B}(#1)} % the Birkhoff-lattice of a polytope (lattice of ideals) (one mandatory argument)

\newcommand{\Pol}{\mathsf{P}} % a polytope P
\newcommand{\Qol}{\mathsf{Q}} % another polytope Q
\newcommand{\Fa}{\mathsf{F}} % a face
\newcommand{\Ga}{\mathsf{G}} % another face
\newcommand{\C}{\mathsf{C}} % a cellular string
\newcommand{\Cone}{\mathsf{C}} % a cone C
\newcommand{\Done}{\mathsf{D}} % another cone D
\newcommand{\perm}{\Pi} %  permutahedron
\newcommand{\mpp}[1]{\mathsf{MPP}({#1})} % monotone path polytope of some polytope (one mandatory argument)
\newcommand{\orderPol}[1]{\mathsf{O}({#1})} % order polytopes of some poset (one mandatory argument)

\renewcommand\phi{\varphi}%
\newcommand\1{\mathbf{1}}%
\newcommand\MPP[2]{\Sigma_{#1}(#2)}%

\newcommand{\sG}{S} %symmetric group 

\DeclareMathOperator{\vol}{vol}
% \DeclareMathOperator{\vertices}{vert}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\outdeg}{outdeg}

\newcommand{\bx}{\mathbf{x}} % vector x in bold
\newcommand{\by}{\mathbf{y}} % vector y in bold
\newcommand{\be}{\mathbf{e}} % vector e in bold
\newcommand{\bv}{\mathbf{v}} % vector v in bold
\newcommand\bu{\mathbf{u}}%
\newcommand\bt{\mathbf{t}}%


%%% command for comments
\newcommand{\sophie}[1]{\noindent{\color{teal}\sf Sophie: {#1}}}
\newcommand{\alex}[1]{\noindent{\color{orange}\sf Alex: {#1} }}
\newcommand{\raman}[1]{\noindent{\color{red}\bf\sf Raman: {#1} }}
\newcommand{\todo}[1]{\noindent{\color{red}\sf \textbf{TODO}: {#1} }}
\newcommand{\mail}[1]{\noindent{\color{blue}\tt  {#1} }}

% command for definitions (high-lighting)
\newcommand{\Def}[1]{\textbf{#1}} 

%--------------------------------------------------------------
%---------------------------------------------------------------------



\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}

Order polytopes~\cite{OrderPolytopes} provide a powerful link between polyhedral
geometry and finite posets. Harnessing this connection resulted in many
important results including the computation of order polynomials, the
fundamental result that computing the volume of a polytope is $\sharp$P-Hard
\cite{brightwellwinkler}, and that certain statistics on linear extensions are
log-concave \cite{StanleyLogConcavity}. Since the foundational work of Stanley,
other poset polytopes have been introduced including marked poset
polytopes~\cite{MarkedPosetPolytopes}, double poset
polytopes~\cite{double_posets}, and poset associahedra \cite{PosetAssociahedra}.
In this extended abstract we introduce another class of poset polytopes that
provided a unified perspective of polytopes that have been studied recently.

Let $\poset = ([n],\preceq)$ be a finite poset. The \Def{order polytope}
$\orderPol{\poset}$ is the intersection of the $0/1$-hypercube $[0,1]^n$ with
the \Def{order cone} $\Cone_{\poset} = \{\bx \in \R^n: \bx_a \prec \bx_b \text{
    for all } a \preceq b \}$. This is a polytope with vertices in $\{0,1\}^n$
with remarkable combinatorics that will be recalled later. For our construction,
recall that the standard \Def{permutahedron} $\Pi_n \subset \R^n$ is the convex
hull of all $n!$ permutations of $(1,2,\dots,n)$. We define the \Def{poset
permutahedron} of $\poset$ by
\begin{equation}\label{eq:defposetpermutahedron}
\Pi_{\poset} := \Pi_{n} \cap \Cone_{\poset}.
\end{equation}
 This is an $(n-1)$-dimensional polytope with
half-integral vertices.  
See \autoref{fig:posetperm2d} for examples.

Poset permutahedra provide a unified construction principle for polytopes that
have occurred in disparate areas. What follows is a non-exhaustive list:
\begin{compactitem}
    \item If $\poset$ is the antichain, then $\Pi_\poset = \Pi_n$.
    \item If $\poset$ is a chain, then $2\Pi_\poset$ is unimodularly equivalent
        to the Newton polytope of the discriminant~\cite[Section III.12.2]{GKZ}.
        The lattice points in $\Pi_\poset-\1$ are the well-studied score
        sequences introduced by Landau~\cite{landau_dominance_1953}; see below
        for more.
    \item If $\poset$ arises from the antichain by adjoining a maximial element,
        then $\Pi_\poset$ is combinatorially equivalent to the
        stellahedron~\cite[Section~10.4]{GenPermFaces}.
    \item If $\poset$ is the disjoint union of two chains of length $m$ and $n$,
        respectively, then the face lattice of $\Pi_\poset$ is ismorphic to the
        poset of colorful subdivisions of an $(m + n+2)$-gon with bicolored
        vertices (cf.~\cite{colorfultriangulations}) and extends the
        combinatorial description of the Newton polytope of the classical
        resultant~\cite[Chapter~12]{GKZ}.  
    \item If $\poset$ is the disjoint union of $k$ chains of lengths $m_1, m_2,
        \dots, m_k$, then $\Pi_\poset$ is the type-$A$ partitioned
        permutahedron introduced and studied in \cite{PartitionedPermutahedra,
        PartitionedPerm2} in the context of Hessenberg varieties and
        representation theory; see \autoref{sec:specialcase} for more.
%    \item \cite{partperms}?
\end{compactitem}

\begin{figure}
    \centering
\begin{subfigure}[t]{.33\textwidth}
 \centering
 \includegraphics[trim=360 120 230 100, clip,width=.8\textwidth]{chain3permutahedroninPerm}
 
 \vspace{2ex}
 
 \includegraphics[scale=.6]{chain123}
\end{subfigure}%
\begin{subfigure}[t]{.33\textwidth}
\centering
 \includegraphics[trim=360 120 230 100, clip,width=.8\textwidth]{twochain3permutahedroninPerm}
 
  \vspace{2ex}
 
 \includegraphics[scale=.6]{tree1-23}
\end{subfigure}%
\begin{subfigure}[t]{.33\textwidth}
\centering
  \includegraphics[trim=360 120 230 100, clip,width=.8\textwidth]{threechain3permutahedroninPerm}
  
   \vspace{2ex}
 
 \includegraphics[scale=.6]{forest1-3}
\end{subfigure}
\caption{Pictured are each of the two dimensional poset permutahedra other than the permutahedron itself up to symmetry with their corresponding posets.}\label{fig:posetperm2d}
\end{figure}

\begin{comment}
\begin{figure}
    \centering
\begin{subfigure}{.5\textwidth}
\centering
    \includegraphics[trim=250 90 250 80, clip, width=.8\textwidth]{Permuta4meins}
    \caption{...}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
    \includegraphics[trim= 240 90 250 85 ,clip,width=.8\textwidth]{twochain4permutahedroninPerm}
    \caption{Caption}
    \label{fig:enter-label}
\end{subfigure}
\caption{...}
\end{figure}
\end{comment}

\medskip
\noindent
\textbf{Monotone Path Polytopes.}
Our key observation is that $\Pi_\poset$ is a fiber polytope in the sense of
Billera--Sturmfels~\cite{BSFiberPoly}. For a polytope $\Pol$ and a non-constant
linear function $\phi$ on $\Pol$, the notion of \Def{cellular strings}
generalizes that of maximal $\phi$-monotone paths in the graph of $\Pol$
oriented by $\phi$. The
collection of cellular strings ordered by inclusion (i.e., one cellular string is contained within another if the union of cells of one is a subset of the union of cells of the other) is the \Def{Baues poset} of
$(\Pol,\phi)$ from algebraic topology; see~\cite{CellString}. While Baues posets
can be rather wild, the subposet of \Def{coherent} cellular strings is
isomorphic to the face poset of the \Def{monotone path polytope}
$\MPP{\phi}{\Pol}$. 
\begin{thm}\label{thm:mpp}
    Let $\poset = ([n],\preceq)$ be a poset. Then
    $\Pi_{\poset} = \MPP{\1}{\orderPol{\poset}}+\frac{1}{2}\1$ with respect to
    the linear function $\1(\bx) = x_1 + \cdots + x_n$.
    % \raman{Need to sort out the translation issues.}
    % \raman{How do we handle repeated theorems?}
\end{thm}

It is typically nontrivial to determine if a cellular string is coherent. In our situation, however,
it turns out that \emph{all} cellular strings are coherent.

\begin{thm}\label{thm:all_coh}
    Let $\poset = ([n],\preceq)$ and $\phi$ a linear function that is positive
    on $\R^n_{\ge 0}$. Then all cellular strings are coherent. In particular the
    face lattice of $\Pi_\poset$ is isomorphic to the Baues poset of
    $(\orderPol{\poset},\1)$.
\end{thm}


\Cref{thm:all_coh} allows us to prove the following results about poset permutahedra:
\begin{compactenum}[\rm (1)]
    \item Vertices of $\Pi_\poset$ are in bijection to chains of filters
        $\emptyset = \fil_0 \subset \fil_1 \subset \cdots \subset \fil_k =
        \poset$ such that the poset $\fil_i \setminus \fil_{i-1}$ is connected for all $i=1,\dots,k$ 
        (\Cref{thm:vertices}).

    \item \Cref{thm:edges} gives a combinatorial characterization of edges and
        the corresponding edge directions.

    \item Facets of $\Pi_\poset$ are in bijection to the set of proper filters
        $\filters{\poset}$ and the cover relations of $\poset$
        (\Cref{cor:facets}).

    \item\label{it:simp}%
        \Cref{thm:vertfacet} yields the vertex-facet-incidences of
        $\Pi_\poset$, and \Cref{thm:simple} shows that $\Pi_\poset$ is simple if
        and only if the undirected Hasse diagram of $\poset$ is a forest.

    \item Analogous to order polytopes, $\Pi_\poset$ is subdivided by the set of
        all $\Pi_L$, where $L$ ranges over the linear extensions
        $\linex{\poset}$ (\autoref{thm:subdivs}).  This allows us to
        compute the volume of $\Pi_\poset$ as $|\linex{\poset}|
        \frac{n^{n-2}}{n!}$ (\Cref{cor:volumes}).

    \item \label{it:IDP}%
        For every poset $\poset$, $2\cdot\Pi_\poset$ is a lattice polytope that has the \Def{integer decomposition property}, that is, if $p \in m\cdot 2\Pi_\poset$ is a lattice point, then
        there are lattice points $p_1,\dots,p_m \in 2\Pi_\poset$ with $p = p_1 +
        \cdots + p_m$; see \Cref{sec:subdivvolip}.

%    \item Lattice points in the permutahedron correspond to score vectors.
%        Lattice points in a chain permutahedron correspond to score sequences.
%        The lattice points  the  poset permutahedron $\perm_\poset$ correspond
%        to \Def{$\poset$-score vectors}, i.e.,  tuples of integers $(s_1, \dots,
%        s_n)\in \{0,1,\dots,n-1\}^n$ that are  possible  result of an $n$-team
%        round-robin tournament under the condition that $s_a\leq s_b$ whenever
%        $a\preceq_\poset b$ is a relation in the poset $\poset$.  They
%        interpolate between score sequences and score vectors.  See
%        \autoref{sec:subdivvolip}.
\end{compactenum}


\medskip
\noindent
\textbf{Partitioned Permutahedra and $h$-vectors.}
In~\cite{PartitionedPermutahedra} a toric orbifold is associated to a Weyl group
$W$ and a choice of a parabolic subgroup $W_K$. In type $A$, they call the
associated moment polytope a \emph{partitioned permutahedron} $\Pi_n(K)$. It is
shown partitioned permutahedra are simple and their $h$-vectors were determined
by using the cohomology of regular Hessenberg varieties. 

\begin{thm}[{\cite[Proposition 7.4]{PartitionedPermutahedra}}]
\label{thm:partitionedpermutahedra}%
    The $h$-polynomial of the partitioned permutahedron for $K \subseteq [n-1]$
    is given by \[h_{\Pi_{n}(K)}(x) = \sum_{\sigma \in W(K)}
    x^{\text{des}(\sigma)},\] where $W(K)$ is the set of permutations $\sigma$
    such that $\sigma^{-1}(i) - \sigma^{-1}(i+1) \leq 1$ for all $i \in K$.
\end{thm}

In \Cref{sec:specialcase}, we show that $\Pi_n(K)$ is the poset permutahedron of
a disjoint union of chains, which implies simplicity by \autoref{thm:simple}. We
provide a direct bijective proof of \Cref{thm:partitionedpermutahedra}.

\medskip
\noindent
\textbf{$\poset$-score sequences.} 
Consider a tournament with teams $1,2,\dots,n$. Any two teams play against
each other and during each match $m$ points are distributed between the two
teams.  This gives rise to a score sequence $s = (s_1,s_2,\dots,s_n)$. We call
$s$ a (strict) $(\poset,m)$-score sequence if $s_i \le s_j$ (respectively  $s_i
< s_j$) if $i \preceq j$. Thus strict $(\poset,m)$-score sequences ensure a
relative ranking of the team given by $\poset$.

\begin{thm}\label{thm:score}
    The $\poset$-score sequences for $m$ points are precisely the lattice points
    in $m\cdot (\Pi_\poset-\1)$. 
    % \raman{@Sophie, please check!}
\end{thm}

\Cref{cor:facets} gives a simple characterization of $(\poset,m)$-score
sequences. If $\poset$ is a chain, then this characterization is classical and
originally due to Landau~\cite{landau_dominance_1953}. While the question of the
number of score sequence for $m=1$ and varying number of teams $n$ has received considerable
attention (cf.~\cite{claesson_counting_2023} and entries \href{https://oeis.org/A000571}{A000571}, \href{https://oeis.org/A007747}{A007747}, \href{https://oeis.org/A047729}{A047729}-\href{https://oeis.org/A047731}{A047731}, and \href{https://oeis.org/A047733}{A047733}-\href{https://oeis.org/A047737}{A047737} in OEIS \cite{oeis_foundation_inc_-line_2024}),
% \footnote{
%  The On-Line Encyclopedia of Integer Sequences (OEIS)  entries
% \href{https://oeis.org/A000571}{A000571}, \href{https://oeis.org/A007747}{A007747}, \href{https://oeis.org/A047729}{A047729}-\href{https://oeis.org/A047731}{A047731}, and \href{https://oeis.org/A047733}{A047733}-\href{https://oeis.org/A047737}{A047737}.}
we are not aware of results
pertaining to the number of score sequences with fixed number of teams $n$ and
varying the number of points $m$. 

\medskip
\noindent
\textbf{All-coherent and Connectivity of flip graphs.}
%Understanding monotone paths on order polytopes is also motivated by work of
%Hersh on polytopes whose directed graphs are Hasse diagrams of lattices
%\cite{HershHirsch}.  The vertices of the order polytope $\orderPol{\poset}$
%correspond to filters in $\poset$, and $\varphi(\bx)=\sum \bx_i$ is precisely
%the rank function of the distributive lattice of filters in $\poset$.  Then the
%Hasse diagram of the distributive lattice is a spanning subgraph of the graph of
%the polytope.  Interestingly the monotone paths in this subgraph are
%(facet-)revisiting  in general, this is in contrast to
%\cite[Conjecture~$1$]{HershHirsch}.
% 
We derive \Cref{thm:all_coh} from the more general \Cref{lem:01coherence}, that
gives a necessary condition when all cellular strings of $(\Pol,\1)$ are
coherent for $0/1$-polytopes $\Pol$. Little is known about polytopes for which
all cellular strings are coherent for some choice of $\varphi$. Our results add
to this list, which includes simplices and hypercubes~\cite{BSFiberPoly},
(poly)matroid independence polytopes~\cite{FlagPolymatroids}, and certain
zonotopes \cite{ZonotopeCoherence}. Furthermore, in very recent work
\cite{MonotonePathFlipConnectivity} expanding on \cite{dConnectedFlipGraph}, it
is shown that a certain graph called the \Def{flip graph} of monotone paths on
$d$-dimensional polytopes is $(d-1)$-connected assuming the polytope satisfies a
condition called being \Def{directionally simple} and that the graph is a Hasse diagram of a lattice.  In their paper, they note
``it is an interesting question for future study to determine exactly how much
further this result can be pushed." In our case, since all cellular strings are
coherent, this graph is precisely the one-skeleton of the corresponding poset
permutahedron.  By Balinski's theorem, this graph is always $(n-1)$-connected.
However, order polytopes are not directionally simple for the  orientation induced by the linear functional $\1(\bx)=x_1+\dots+x_n$, so
this family of polytopes pushes their results further.


%---------------------------------------
\begin{comment}
Our General Results:
\begin{itemize}
    \item Start: People love order polytopes. They are intersections of the hypercube with an order cone. 
    \item We define the poset permutahedron analogously. 
    \item one motivation: lattice points are poset-score sequences
    \item Main Theorem: The face lattice is blah. 
    \item How do we prove it? Recall that to get the permutahedron from the cube, you can take a sum of fibers. It turns out the same construction works here. Theorem: Poset permutahedron is a monotone path polytope of the order polytope for a certain orientation, and all cellular strings are coherent.
    This opens a tool box to prove properties
    \item We compute volumes and can apply this for asymptotics of score sequences, when the number of points in each game increases.
\end{itemize}
This is a general framework with a number of interesting concrete examples:
 
\begin{itemize}
    \item Chain -> Newton polytope of the Discriminant. From our results, we are able to compute the volume of this polytope, which has an interpretation in that setting. 
    \item 2 Chains -> Colorful triangulations and its a simple polytope analogous to the associahedron in that setting. (Connected to Gelfand, Kapranov, Zelevinsky stuff). 
    \item Disjoint Union of Chains Corollary: All cellular strings on a products of simplices for any generic orientation are coherent. Why interesting? There is an analogous question of whether all subdivisions of a product of simplices were regular that was proven to be false by De Loera and even in low dimensions by Gaku Liu. This is an interesting contrast. 
    \item Corollary: The monotone path polytope of the product of simplices is precisely the partitioned permutahedra studied by X people. We get new, nonobvious insight into the combinatorics of those polytopes. (Interesting for linking rook walk literature and algebraic combinatorics) 
    \item Unique Maximum: Stellahedron and this gives an interesting interpretation of the lattice points of the stellahedron.
    \item General Forests: Raman's tree linear extension counting thing? Interesting that we can characterize simplicity completely. 
\end{itemize}



Consider an $n$-team round-robin tournament, that is, every team plays against each other team and gets one point if it wins.
How many possible outcomes does such a tournament have? What if in every game there are $k$ points that are distributed between the two teams?
This question motivated quite some research... MacMahon...
 
A \Def{score sequence} is an integer sequence $0\leq s_1\leq \dots \leq s_n\leq n-1$ that is a possible  result of an $n$-team round-robin tournament.
Equivalently, a score sequence is a non-decreasingly ordered indegree sequence of a directed complete graph on $n$-nodes, such a graph is called a \Def{tournament} $T_n$.
% Note that there are non-isomorphic tournaments that result in the same score sequence.
% For a more detailed introduction to score sequences see, e.g., \cite{moon_topics_2013}.
Note that here we are interested in the possible outcomes for the entire tournament without taking into account which team actually wins.
Or phrasing it differently, how many outcomes of a tournament lead to the same (weakly) increasing total order of teams?
Example: for $n=2$ the only one score sequence is $0\leq 1$, 
for $n=3$ we have $0\leq1\leq2$ and $1\leq1\leq1$. 

cite OEIS entry ... finding a formula that counts score sequences is hard and has a long history....
also cite tournaments with more points in each game...

A \Def{score vector} is a tuple of integers $(t_1, \dots, t_n)$ where $t_i$ records the number of points team $i$ wins during the tournament.
% 
% If we record the number of points for each team 
Example: for $n=2$ there are two score vectors, $(0,1)$ and $(1,0)$, 
for $n=3$ we have $7$ score vectors, the six permutations of $(0,1,2)$ and $(1,1,1)$. 

It follows from Landau's theorem \cite{landau_dominance_1953} that score vectors are the integer points in the standard permutahedron.
% 
Then score sequences are the integer points in the standard permutahedron intersected with the order cone of the $n$-chain. 
% and score vectors are the integer points in the standard permutahedron (intersected with the order cone of the anti-chain, $\R^n$).
Integer points in the $k^{\text{th}}$ dilate of the permutahedron (resp. the permutahedron intersected with the order cone of a chain) correspond to score vectors (resp. score sequences) where $k$ points are distributed in each game.

We want to study \Def{poset permutahedra} $\perm_\poset$, that is, the standard permutahedron $\perm$ intersected with the order cone $\Cone_\poset$ of an arbitrary poset $\poset$.
The integer points in the poset permutahedron $\perm_\poset$ correspond to \Def{$\poset$-score vectors}, i.e.,  tuples of integers
$(t_1, \dots, t_n)\in \{0,1,\dots,n-1\}^n$ that are  possible  result of an $n$-team round-robin tournament under the condition that $t_i\leq t_j$ whenever $i\preceq_\poset j$ is a relation in the poset $\poset$.
% 
Hence, integer points in poset permutahedra interpolate between score vectors  and score sequences
This offers a unifying perspective to study $\poset$-score vectors (including classical score sequences) for arbitrary posets $\poset$ and arbitrary numbers of points awarded in each game of the tournament. 
% We hope to open new perspectives on these counting problems using Ehrhart theoretic techniques.

Poset permutahedra  also arise as the monotone path polytopes of order polytopes. 
This allows us to describe  vertices, facet descriptions, vertex-facet incidences, edge directions,  a subdivision and the volume of poset permutahedra in terms of the poset.

Special cases of poset permutahedra show up in several other contexts: partial permutahedra \cite{partperms}, partitioned permutahedra \cite{PartitionedPermutahedra}, \cite{PartitionedPerm2}, stellahedra, ... (?)
\end{comment}

\begin{comment}
We study a family of polytopes called poset permutahedra and do the following:
\begin{enumerate}
    \item Completely describe their vertices, edges, facets, and face lattice
    \item  Characterize simplicity 
    \item Characterize simplicity 
    Compute volumes 
\end{enumerate}


Special Cases of these polytopes include:
\begin{enumerate}
    \item The Newton polytope of the discriminant up to affine transformation, which is a combinatorial cube (the chain) 
    \item Certain colorful subdivisions of an n-gon (2 chains) -> Related study appeared independently recently 
    \item Partitioned Permutahedra (k chains) -> Connected to Hessenberg varieties and rep theory 
    \item Stellahedra (star with unique maximum) 
\end{enumerate}
Motivations: 
\begin{enumerate}
    \item     Lattice points correspond to generalized score sequences. (Talk about stellahedron case as a nice example??) 
    Interesting from the theory of fiber polytopes. \item As a corollary, we show all cellular strings on products of simplices are coherent in contrast to well known results concerning regular subdivisions. Interesting that this property occurs for a large family of polytopes in every dimension and seems to contrast with the case for regular subdivisions. 
    \item Order polytopes are core objects in algebraic and geometric combinatorics, and our polytopes share a lot of the same structure
    \item Our polytopes compactify certain submodular function polytopes appearing in Fujishige's work 
\end{enumerate}
\end{comment}

\section{Monotone Path Polytopes and Order Polytopes}\label{sec:mpp}

In this section we show that poset permutahedra arise as monotone path polytopes
of order polytopes.  Let $\Pol \subset \R^n$ be a polytope and $\varphi : \R^n
\to \R$ a linear function that is not constant on $\Pol$. A \Def{monotone path}
on $\Pol$ is the sequence of edges $e_1,\dots,e_m$ along a strictly
$\phi$-increasing path in the graph of $\Pol$ from a minimizer to a maximizer of
$\phi$. Cellular strings generalize monotone paths to faces of
higher dimensions. A \Def{cellular string} is a sequence $(\Fa_{1}, \Fa_{2},
\dots, \Fa_{k})$ of faces of $\Pol$ such that $\Fa_{1}$ and $\Fa_{k}$ contain a
$\varphi$-minimizer and maximizer respectively, and $\Fa_{i} \cap \Fa_{i+1}$ is
the $\varphi$-maximal face of $\Fa_{i}$ and the $\varphi$-minimal face of
$\Fa_{i+1}$ for all $1 \leq i \leq k-1$. Cellular strings are partially ordered
by refinement. The resulting poset is the \Def{Baues poset} of $(\Pol,\phi)$,
whose minimal elements are precisely the monotone paths; see~\cite{CellString}.
Let $\psi$ be a linear function linearly independent of $\phi$. The ordered
sequence of faces of $\Pol$ that maximize the linear functions $\psi + t \phi$
as $t$ ranges from $-\infty$ to $+\infty$ yields a cellular string, called a
\Def{coherent} cellular string. Billera and Sturmfels~\cite{BSFiberPoly} showed
that the subposet of coherent cellular strings is the face poset of a polytope,
the \Def{monotone path polytope} $\MPP{\phi}{\Pol}$. They show that the monotone
path polytope is the Minkowski integral
\[
    \MPP{\phi}{\Pol} \ = \ \int_{\R} P \cap \phi^{-1}(s) \, ds \, .
\]
Note that our definition differs from that in~\cite{BSFiberPoly} by a scaling factor.  For $\Pol = [0,1]^n$
and the linear function $\1(\bx) = x_1 + \cdots + x_n$, we get
$\MPP{\1}{[0,1]^n} = \Pi_{n}- \frac{1}{2}\1$, as in~\cite{BSFiberPoly}.

%\begin{thm}\label{thm:mpp}
%    Let $\poset = ([n],\preceq)$ be a poset. Then
%    $\MPP{\1}{\orderPol{\poset}}  = \Cone_\poset \cap (\perm_n - \frac{1}{2}\1)$ and $\perm_\poset=\MPP{\1}{\orderPol{\poset}}+ \frac{1}{2}\1$.
%    % \raman{Need to sort out the translation issues.}
%\end{thm}
\begin{proof}[Proof sketch of \Cref{thm:mpp}]
    For the proof, we verify
    \begin{align*}
           \MPP{\1}{\orderPol{\poset}}  \ &= \ \int_{\R} \Cone_{\poset} \cap [0,1]^n \cap  \1^{-1}(s) \, ds \\
         \ &= \ \Cone_{\poset} \cap \int_{\R} [0,1]^n \cap  \1^{-1}(s) \, ds 
         \ = \ \Cone_{\poset} \cap \left(\perm_n- \tfrac{1}{2}\1\right) 
         \, .  
    \end{align*}
    Since $- \tfrac{1}{2}\1 + \Cone_{\poset} = \Cone_{\poset}$, this proves the
    claim. Note that proving this sequence of equalities is nontrivial, since in general one cannot pull an intersection with a cone outside of a Minkowski integral. 
\end{proof}

The result yields that the face poset of $\Pi_\poset$ is a subposet of the Baues
poset.  The following lemma, which is of interest in its own
right, implies that all cellular strings of $(\orderPol{\poset},\1)$ are
coherent. A version of this statement had also appeared  as Corollary $3.4.2$
in the PhD Thesis \cite{AlexThesis}. 

\begin{lem}\label{lem:01coherence}
    Let $\Pol$ be a $0/1$-polytope. If for all edges $[\bu,\bv] \subset \Pol$ the nonzero
    entries $\bu-\bv$ are of the same sign, then all cellular strings of $(\Pol,\1)$ are coherent.
\end{lem}

Recall from~\cite{OrderPolytopes} that $\orderPol{\poset}$ is a $0/1$-polytope
with vertices corresponding to indicator vectors $\be_\fil \in \{0,1\}^n$ of
\Def{filters} $\fil$ of $\poset$. The collection of filters of $\poset$ ordered
by inclusion is the \Def{Birkhoff lattice} $\filters{\poset}$ and $\1(\be_\fil)
= |\fil|$ is the rank of $\fil$ in $\filters{\poset}$. Two filters $\fil,\fil'$
correspond to the endpoints of an edge of $\orderPol{\poset}$ if and only if,
say, $\fil \subseteq \fil'$ and $\fil' \setminus \fil$ is a connected poset.
Hence all cellular strings of $(\orderPol{\poset},\1)$ are coherent.  In
particular, the order complex of the face lattice of
$\MPP{\1}{\orderPol{\poset}}$ is a simplicial sphere.  Theorem~2.1
of~\cite{ZonotopeCoherence} implies that all cellular strings of
$(\orderPol{\poset},\phi)$ are coherent, provided $\phi$ induces the same
orientation on the graph of $\orderPol{\poset}$ as $\1$. This is the case if
$\phi$ is positive on $\R^n_{\ge0}$. This then yields \Cref{thm:all_coh}.
% \sophie{not sure, I can follow this argument}

\section{Faces of Poset Permutahedra}

It follows from \Cref{thm:all_coh} that the vertices of $\Pi_\poset$ correspond to 
$\1$-monotone paths on $\orderPol{\poset}$, which in turn correspond to chains
\[
    \emptyset \ = \ 
    \fil_0 \ \subset \ 
    \fil_1 \ \subset \ 
    \cdots \ \subset \ 
    \fil_k \ = \ \poset
\]
of filters of $\poset$ such that the induced undirected subgraph of the Hasse
diagram of $\poset$ given by restricting to $\fil_{i} \setminus \fil_{i-1}$ is
connected for all $i \in [k]$, that we denote by $\fil_\bullet$.  We denote the
collection of such chains by $\chains{\poset}$ and call these \Def{connected
chains}.  This is an accessible set system within the order complex of
$\filters{\poset}$ but not a simplicial subcomplex. From
\cite[Theorem~5.3]{BSFiberPoly} we deduce the vertex set of $\Pi_\poset$. For $A
\subseteq [n]$, we write $A^c = [n]\setminus A$ for the complement.

\begin{thm}\label{thm:vertices}
    The vertices of $\Pi_\poset$ are in bijection to connected chains of filters
    $\fil_\bullet$ in $\poset$. For $\fil_\bullet$, the corresponding vertex is
    \[
        \Psi(\fil_\bullet) \ = \ 
\frac{1}{2}\sum_{i=1}^{l}
         \left(\lvert\fil^c_{i}\rvert+\lvert \fil^c_{i-1}\rvert+1 \right)\, \be_{\fil_{i} \setminus
         \fil_{i-1}} \, .
    \]
\end{thm}

Two dimensional faces of $0/1$-polytopes are either triangles or
quadrilaterales. For order polytopes  $\orderPol{\poset}$, they correspond to filters $\fil \subset \fil'$ of $\poset$
such that $\fil' \setminus \fil$ has at most two connected components. From the
monotone path polytope perspective, edges of $\Pi_\poset$ correspond to cellular 
strings $\Fa_1,\dots,\Fa_k$ in $\orderPol{\poset}$ such that $\Fa_i$ is a $2$-face for precisely one $i\in\{1,\dots,k\}$ and $\Fa_j$ are edges for all $j \neq i$. 

\begin{thm}\label{thm:edges} 
    Let $\Pi_\poset$ be a poset permutahedron and $\fil_\bullet, \fil_{\bullet}' \in
    \chains{\poset}$ be a pair of connected chains of filters with the length of $\fil_{\bullet}$ at least the length of $\fil_{\bullet}'$. Then $\Psi(\fil_\bullet)$ and $\Psi(\fil'_\bullet)$  are adjacent if and only if there is an  $1 \le i <
    k$ such that:
    \begin{compactenum}
        \item  $\fil_{i+1} \setminus \fil_{i-1}$ is connected and $\fil'_\bullet$ is
\hfill (\Def{Coarsening edges})
            \[
    \fil'_{\bullet} = \fil_0 \ \subset \ 
    \cdots \ \subset \ 
            \fil_{i-1} \ \subset \ 
            \fil_{i+1} \ \subset \ 
    \cdots \ \subset \ 
    \fil_k  \, . 
            \]
    % Then the corresponding edge direction is
    % $((n+1)/2,\dots,(n+1)/2)$
    % $(1, (n+2)/2, \dots, (n+2)/2)$ 
    % $\emptyset \subset \{1\} \subseteq [n]$
    
    Then we have 
    % \todo{check this!!}
    % \begin{equation*}
    % \Psi(\fil_\bullet)+\tfrac 1 2\left(\left(\lvert\fil_{i+1}\rvert - \lvert\fil_{i}\rvert \right) \be_{\fil_i\setminus\fil_{i-1}} + \left(\lvert\fil_{i-1}\rvert - \lvert\fil_{i}\rvert \right) \be_{\fil_{i+1}\setminus\fil_{i}}\right)\, =\Psi(\fil'_\bullet).
    % \end{equation*}
     \begin{equation*}
    \Psi(\fil'_\bullet)-\Psi(\fil_\bullet)=\tfrac 1 2\left(\left(\lvert\fil_{i}\rvert - \lvert\fil_{i+1}\rvert \right) \be_{\fil_{i-1}\setminus\fil_{i}} + \left(\lvert\fil_{i-1}\rvert - \lvert\fil_{i}\rvert \right) \be_{\fil_{i+1}\setminus\fil_{i}}\right)\, .
    \end{equation*}
    
        \item $\fil_{i+1} \setminus \fil_{i-1}$ consists of two connected components and
            $\fil'_\bullet$ is 
\hfill (\Def{Swapping edges})
            \[ \fil_{\bullet}' =
    \fil_0 \ \subset \ 
    \cdots \ \subset \ 
            \fil_{i-1} \ \subset \ ( 
            \fil_{i-1} \cup (\fil_{i+1}\setminus \fil_i)) \ \subset \ 
            \fil_{i+1} \ \subset \ 
    \cdots \ \subset \ 
    \fil_k  \, . 
            \]
            % Then the corresponding edge direction is
             Then we have  \begin{equation*}
    \Psi(\fil_\bullet')- \Psi(\fil_\bullet)=\left(\lvert\fil_{i}\rvert-\lvert \fil_{i+1}\rvert\right)\be_{{\fil_{i}} \setminus \fil_{i-1}}
          + \left(\lvert \fil_{i}\rvert-\lvert {\fil_{i-1}}\rvert\right)\be_{\fil_{i+1} \setminus {\fil_{i}}},.
    \end{equation*}
    \end{compactenum}
\end{thm}
% From \autoref{thm:vertices} and \autoref{thm:edges} one can compute the edge directions explicitly.
To determine the facets of $\Pi_\poset$ it suffices by \Cref{thm:mpp,thm:all_coh} to
determine the coarsest, nontrivial cellular strings.  We denote the cover relations of a poset
$\poset$ by $a \cov b$.

\begin{thm}\label{thm:coarse_strings}
    The coarsest nontrivial cellular strings of $(\orderPol{\poset},\1)$ are of the following two forms:
    \begin{compactenum}
        \item $(\Fa_1)$, where $\Fa_1$ is a facet of the order polytope $\orderPol{\poset}$ corresponding to a cover relation $a \cov b$.
        \item  $(\Fa_{1}, \Fa_{2})$, where $\Fa_1$, $\Fa_2$ are faces of $\orderPol{\poset}$ and there exists a filter $\fil$ in $\poset$ such that all vertices in $\Fa_{1}$ correspond to filters contained in $\fil$  and 
        % is the face of filters contained in $\fil$ 
        and all vertices in $\Fa_{2}$ correspond to filters containing~$\fil$.
    \end{compactenum}
\end{thm}

The proof of \Cref{thm:coarse_strings} makes use of the following two properties
of order polytopes.  First, for any nonempty face $\Fa \subseteq
\orderPol{\poset}$, there is a unique vertex that maximizes $\1(\bx)$. Second,
for any two filters $\fil \subseteq \fil'$ there is a unique face $\Fa \subseteq
\orderPol{\poset}$ whose vertices are in bijection to the interval
$[\fil,\fil']$ in the Birkhoff lattice of $\poset$. 

For $n \ge 1$ define the submodular set function $f_n$ by  $f_n(S) :=
\binom{n+1}{2} - \binom{n-|S|+1}{2}$ for $S \subseteq [n]$.  Moreover, for $S
\subseteq [n]$, let $\1_S$ be the linear function given by $\1_S(\bx) := \sum_{i
\in S} x_i$. 

\begin{cor}\label{cor:facets} 
    Let $\poset = ([n],\preceq)$ be a poset. A point $\bx \in \R^n$ is contain in $\Pi_\poset$ if
    and only if 
    \begin{align*}
        x_a \ &\le \ x_b & \text{ for all cover relations } a \cov b \\
        \1_\fil(x) \ &\le \ f_n(\fil) & \text{ for all proper, nonempty filters } \fil \subset \poset \\
        \1(x) \ &= \ f_n([n]) = \tbinom{n+1}{2} \, . 
    \end{align*}
    The inequality description is irredundant.
\end{cor}
% \Cref{thm:coarse_strings} also makes the vertex-facet-incidences explicit.
% \alex{The vertex-facet incidences aren't really explicit but can be derived from
% Theorem 9. Perhaps we should say them explicitly?} 
From \autoref{thm:coarse_strings} and \autoref{cor:facets} we can also derive explicit vertex-facet incidences for the poset permutahedron $\perm_\poset$.
% 
\begin{cor}\label{thm:vertfacet} A vertex given by the connected chain of filters  $\emptyset = \fil_0 \subset \fil_1\subset \cdots \subset \fil_k  = \poset$ is contained in the facets corresponding to
\begin{compactenum}
    \item the proper nonempty filters $\fil_{1}, \dots, \fil_{k-1}$ and
    \item cover relations $a \cov b$ such that  $a,b \in \fil_{i}\setminus\fil_{i-1}$ for some $i \in [k]$ with.
\end{compactenum}
% the proper nonempty filters $\fil_{1}, \dots, \fil_{k-1}$ and in the facets corresponding to cover relations $a \cov b$ such that there exists some $i \in [k]$
% with $a,b \in \fil_{i}\setminus\fil_{i-1}$.
% \begin{align*}
%     \{(a,b): a \cov b \text{ and there exists some }  i \in [k] \text{ such that } a,b \in \fil_{i}\setminus\fil_{i-1}\}\,.
% \end{align*}
\end{cor}

Applying this
characterization together with a counting argument enables us to
characterize the simple poset permutahedra. 

\begin{thm}\label{thm:simple}
    A poset permutahedron $\Pi_\poset$ is a simple polytope if and only if the undirected Hasse diagram of $\poset$ is a (not necessarily rooted) forest.
\end{thm}
 
%\ \\ \hrule \ \\

\section{Subdivision, Volumes and Integer Points} \label{sec:subdivvolip} 
We view a linear extension $L$ of $\poset$ as a refinement of $\preceq$ to a
total order $[n]$ and we collect the linear extensions in $\linex{\poset}$. For
$L \in \linex{\poset}$ it is well known that $\orderPol{L}$ is a unimodular
simplex contained in $\orderPol{\poset}$ and that $\{ \orderPol{L} : L \in
\linex{\poset} \}$ is a triangulation of $\orderPol{\poset}$. This generalizes
to poset permutahedra.

\begin{thm}\label{thm:subdivs}
    For any poset $\poset$, the set $\{\Pi_L : L \in
    \linex{\poset}\}$ is a subdivision of $\Pi_\poset$.
\end{thm}

Note that this is immediate from the initial definition we give for the poset permutahedron in Equation~\eqref{eq:defposetpermutahedron}  but is nonobvious from its equivalent formulation as a fiber polytope. If $\poset$ is the antichain on $n$ elements, then the symmetric group acts
simply transitively on $\linex{\poset}$ and shows that any two $\Pi_L$ are
isometric. In particular $\vol(\Pi_L) = \frac{1}{n!} \vol \Pi_n$. The volume of
$\Pi_n$ is famously known to be the number of spanning trees of the complete
graph on $n$ nodes. This yields the following: 

\begin{cor}\label{cor:volumes}
        For a poset $\poset$ on $[n]$, the volume of $\perm_{\poset}$ is
        $\frac{|\linex{\poset}|}{n!}n^{n-2}$. In particular, the probability
        that a random point of $\perm_{n}$ is in $\perm_{\poset}$ is precisely
        the probability that a random permutation is a linear extension of
        $\poset$.
\end{cor}


A \Def{score sequence} is an integer sequence $0\leq s_1\leq \dots \leq s_n\leq
n-1$ that is a possible  result of an $n$-person round-robin tournament in which
a single point is awarded to the winner of a match. 
Equivalently, a score
sequence is a reordering of the \Def{indegree sequence} of a tournament, that
is, a directed complete graph on $n$ nodes.
For $n=2$ the only score sequence is $0\leq 1$ and
for $n=3$ we have two score sequences: $0\leq1\leq2$ and $1\leq1\leq1$. 
A \Def{score vector} is a tuple of
integers $\bt = (t_1, \dots, t_n)$, where $t_i$ records the number of points that
team $i$ wins during the tournament.
For $n=2$ there are two score vectors: $(0,1)$ and $(1,0)$;
for $n=3$ we have $7$ score vectors: $(1,1,1)$ and  the six permutations of $(0,1,2)$. 

If we define $\alpha_{ij} \in \{-1,1\}$ for $1
\le i < j \le n$ by $\alpha_{ij} = 1$ if $j$ wins the match between $i$ and $j$ and $-1$ otherwise, then
the score vector $\bt$ is 
% \sophie{the equation is not correct, $t$ should be integral}
\[
    \bt \ = \ \frac{1}{2}\left((n-1) \1 + \sum_{i < j} \alpha_{ij} (\be_j - \be_i)\right) \, .
\]
Thus, the collection of score vectors are the integer points in the projection
of $\{-1,1\}^{\binom{n}{2}}$ with respect to the projection that sends the standard
basis vector $\be_{ij}$ to $\be_j - \be_i$. This is the permutahedron $\Pi_n$ up to
the translation by $ \1$. The characterization of the defining facets
of the convex hull of score vectors is due to
Landau~\cite{landau_dominance_1953}. The score sequences are the lattice points
in $\Pi_\chain - \1$, where $\chain$ is a chain poset. 
By \autoref{thm:subdivs}, for general posets $\poset$ we have that the $\poset$-score vectors are the integer points in the poset permutahedron $\Pi_\poset - \1$.
 
\autoref{thm:score} for chain posets follows  from \cite{moon_extension_1963}, \autoref{thm:subdivs} implies the result for every poset permutahedron.
Combinatorially we can get this result by 
considering complete directed graphs with $m$ directed edges between any pair of
nodes.

Decomposing every such multi-tournament for $2m$ into $m$
tournaments with two directed edges between any pair of nodes, shows the integer decomposition property (\ref{it:IDP}) from the
introduction. 
Note that for this to work in general we need the integer point in the second dilate of the poset permutahedron: for the chain poset on two elements we only have one integer point $(0,1)$ in the first dilate.

% \raman{If we need the OEIS footnote, then we should make it more prominent.}\footnote{{
%  The On-Line Encyclopedia of Integer Sequences (OEIS)  entries
% \href{https://oeis.org/A000571}{A000571}, \href{https://oeis.org/A007747}{A007747}, \href{https://oeis.org/A047729}{A047729}-\href{https://oeis.org/A047731}{A047731}, and \href{https://oeis.org/A047733}{A047733}-\href{https://oeis.org/A047737}{A047737}.}}

\section{Partitioned Permutahedra}\label{sec:specialcase}

In \cite{PartitionedPermutahedra}, Horiguchi, Masuda, Shareshian, and Song
defined \textbf{partitioned permutahedra} with motivation coming from
combinatorial algebraic geometry.  To define these polyhedra, they define a
linear halfspace for each $k \in [n-1]$ given by 
\[
    H(k) \ := \ \{\bx \in \R^n: x_k \leq x_{k+1} \} \, .
\]
For each subset $K \subseteq [n-1]$, they define the \Def{partitioned
permutahedron} via
\[
    \Pi_{n}(K) = \Pi_{n} \cap \bigcap_{k \in K} H(k). 
\]
For every such subset $K \subseteq [n-1]$, we associate the poset $\poset_K =
([n],\preceq)$ with cover relations are given by $i \cov i+1$ if $i \in K$. The
following follows directly from our definition of poset permutahedra.
\begin{prop}
    For every $K \subseteq [n-1]$, we have $\Pi_n(K) = \Pi_{\poset_K}$. 
\end{prop}

Geometrically $\orderPol{\poset_K}$ is a product of simplices for which cellular
strings are easy to describe. In particular, \Cref{thm:vertices},
\Cref{cor:facets}, and \Cref{thm:coarse_strings} recover the results on
vertices, facets, and incidences in~\cite{PartitionedPermutahedra}.


\begin{cor}
    Partitioned permutahedra are simple polytopes.
\end{cor}
This follows directly from the observation that $\poset_K$ is a disjoint union of chains and \Cref{thm:simple}.
This follows also as a consequence of Proposition 4.5 in \cite{PartitionedPermutahedra}  .


Proposition 7.4 in~\cite{PartitionedPermutahedra} shows that the $h$-vector of $\Pi(W)$ is
the descent statistic restricted to the permutations $\sigma$ of $[n]$ with
$\sigma^{-1}(i) - \sigma^{-1}(i+1) \leq 1$ for all $i \in K$. The set of these
permutations is denoted by $W(K)$. This is shown by applying results on the
cohomology of Hessenberg varieties. We sketch a simple combinatorial proof
using the geometry of poset permutahedra.

\begin{figure}
    \centering
\begin{minipage}{.32\textwidth}
\centering
    \begin{tikzpicture}[scale = .5]
    \draw[black, thick] (0,0) -- (0,8);
    \draw[black, thick] (4,0) -- (4,8);
    % \draw[green, thick] (0,0) -- (2,-3);
    % \draw[green, thick] (0,0) -- (4,-4);
    % \draw[green,thick] (2,2) -- (8,-1);
    % \draw[green,thick] (2,2) -- (8,0);
    \draw (0,0) node[red, circle, fill, scale =.5] {};
    \draw (0,2) node[red, circle, fill, scale =.5] {};
    \draw (0,4) node[red, circle, fill, scale =.5] {};
    \draw (0,6) node[red, circle, fill, scale =.5] {};
    \draw (0,8) node[red, circle, fill, scale =.5] {};
    \draw (-3,0) node {$1 = \sigma(3)$};
    \draw (-3,2) node {$2 = \sigma(2)$};
    \draw (-3,4) node {$3= \sigma(1)$};
    \draw (-3,6) node {$4 = \sigma(5)$};
    \draw (-3,8) node {$5 = \sigma(4)$};
    \draw (4,0) node[violet, circle, fill, scale =.5] {};
    \draw (4,2) node[violet, circle, fill, scale =.5] {};
    \draw (4,4) node[violet, circle, fill, scale =.5] {};
    \draw (4,6) node[blue, circle, fill, scale =.5] {};
    \draw (4,8) node[blue, circle, fill, scale =.5] {};
    \draw [blue, very thick,domain=0:180] plot ({4 + cos(\x)}, {8 - 3*sin(\x)});
    \draw [violet, very thick,domain=0:180] plot ({4 + 1.5*cos(\x)}, {8 - 9*sin(\x)});
\end{tikzpicture}
\end{minipage}\hfill%
\begin{minipage}{.67\textwidth}
     \caption{Pictured is an illustration of the bijection $g$ used in the proof sketch of \autoref{thm:partitionedpermutahedra}
    % explained in the proof sketch of \autoref{thm:partitionedpermutahedra} 
    for the permutation $32154$. First consider $\sigma(5) = 4$. Then the smallest filter containing it is $\{4,5\}$. The largest element whose image is not covered is $3$. Since $\sigma(3) = 1$, and the smallest remaining filter containing $1$ is the whole chain. This yields the resulting chain of filters $\{4,5\} \subseteq \{1,2,3,4,5\}$. The descents of $\sigma$ are $\{(1,2), (2,3), (4,5)\}$ and correspond exactly to refining edges, which are all $\omega=(1,2,4,8,16)$-improving.}
    \label{fig:permbijection}
\end{minipage}
\end{figure}
\begin{proof}[Proof sketch of \Cref{thm:partitionedpermutahedra}]
    Recall that we can compute the $h$-polynomial of a simple polytope the
    following way (see, e.g., \cite[Chapter~VI.6]{barvinok}): We first choose an
    edge-generic linear functional $\omega\colon\R^n\to \R$, which induces an
    acyclic orientation on the graph of the polytope $\Pol$. If $\outdeg(\bv)$ denotes
    the out-degree of the vertex $\bv$, i.e., the number $\omega$-improving
    neighbors, then 
    \[ 
        h_{\Pol}(x) \ = \ \sum_{\bv} x^{\outdeg(\bv)}\,.
    \]
    In order to prove the stated expression for the $h$-polynomial, we define a
    bijection $g$ between connected chains of filters in the poset
    $\poset=[1,k_{1}] \uplus[k_{1}+1, k_{2}] \uplus \dots \uplus [k_{\ell}+1,
    n]$ and $W(K)$. For each $\sigma \in W(K)$, we build $g(\sigma)$ via the
    following algorithm. Initialize the chain of filters $\fil_\bullet = \{
        \fil_0 = \emptyset \}$. We write $\bigcup\fil_\bullet = \bigcup_{\fil
    \in \fil_\bullet} \fil$.  While $\bigcup\fil_\bullet \neq [n]$, let $k$ be
    maximal such that $\sigma(k) \notin \bigcup\fil_\bullet$. Let $\fil'$ be the
    unique smallest filter containing $\sigma(k) \cup \bigcup\fil_\bullet$ and
    add $\fil'$ to $\fil_\bullet$. When the process terminates, the
    result will be a connected chain of filters. This is a bijection. See
    \autoref{fig:permbijection} for an illustration.

    
    Let $\omega(\mathbf{x}) = \sum_{i=1}^{n} 2^{i} \mathbf{x}_{i}$.  Then to
    prove the theorem, it suffices to show that the size of the descent set of
    $\sigma$ is precisely the $\omega$-out-degree of the corresponding vertex
    $g(\sigma)$. One can do this directly by applying our characterization of
    edge directions derived from \Cref{thm:edges}.
\end{proof}

We also offer an alternative characterization of the vertices that makes them
efficient to count as a sum of multinomials or via memoization and the
recurrence \[a_{m_{1}, m_{2},\dots,m_{k}} = \sum_{j=1}^{k} \sum_{i=0}^{m_{j}-1}
a_{m_{1}, m_{2}, \dots, m_{j-1}, i, m_{j+1}, \dots, m_{k}}.\] To do this, we
require the notion of a high dimensional rook walk as found in
\cite{HighDimRookWalk}.  Namely, a rook walk in a $m \times n$ grid is any
sequence of moves a rook could take to move from $(0,0)$ to $(m,n)$, where the
rook is only allowed to move to the right or up.  In high dimensions, one can
consider any sequence from $(0,0,\dots,0)$ to $(m_{1}, m_{2}, \dots, m_{n})$
such that at each step one can only increase in a single coordinate at a time. 

\begin{prop}
    For $K \subseteq [n-1]$, the following sets have the same cardinality:
    \begin{compactenum}[\rm i)]
        \item The set of vertices of the partitioned permutahedron $\Pi_{n}(K)$.
        \item The set $W(K) = \{\sigma \in S_{n}: \sigma^{-1}(i) -
            \sigma^{-1}(i+1) \leq 1 \text{ for all } i \in K\}$.
        \item The set of high dimensional rook walks from $(0,0,\dots,0)$ to
            $(k_{1}, k_{2}-k_{1}, k_{3}-k_{2}, \dots, n-k_{\ell})$, where
            $\{k_{1}<  k_{2} < \dots < k_{\ell} < n\} = [n] \setminus K$.
    \end{compactenum}
\end{prop}

        In \cite{HighDimRookWalk}, they studied asymptotics and recurrences for the sequence of high dimensional rook walks from $(0,0,\dots,0)$ to $(n,n,\dots,n)$, and our results give a new combinatorial perspective for arbitrary endpoints. 
        Finally, we note as a corollary of \autoref{cor:volumes}, we can compute the volumes of the partitioned permutahedra:

        \begin{cor}
        The volume of the partitioned permutahedron $\Pi_{n}(K)$ for $K \subseteq [n-1]$ is given 
        \[\frac{n^{n-2}}{n!}\binom{n}{k_{1}, k_{2}-k_{1}, k_{3}-k_{2}, \dots, n-k_{\ell}}\]
        for $\{k_{1} < k_{2} < \dots < k_{\ell} < n\} = [n] \setminus K$.
        \end{cor}
        


\acknowledgements{
We would like to thank Christian Haase for helpful discussions and the anonymous reviewers for useful comments on a previous version.     
}

% \todo{clean up references,}
%% 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}
