
\documentclass[finalversion]{FPSAC2023}
\articlenumber{64}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{MainTheorem1}{\cref{thm:pasmverts}}
\newtheorem*{MainTheorem2}{\cref{pasmfacets}}
\newtheorem*{MainTheorem3}{\cref{thm:permuto_ineq}}
\newtheorem*{MainTheorem4}{\cref{permutofacets}}
\newtheorem*{MainTheorem5}{\cref{chain-face-lattice}}
\newtheorem*{MainTheorem6}{\cref{pasm-proj}}
\newtheorem*{PasmFaceLatticeThm}{\cref{thm:pasm_facelattice}}
\newtheorem*{Volthm}{\cref{ppermvol1}}
\newtheorem*{CorSSYT}{\cref{cor:SSYT}}
\newtheorem*{CorGT}{\cref{cor:GT}}
\newtheorem*{CorFT}{\cref{cor:FT}}
\newtheorem*{Cor5}{\cref{cor:prorow}}
\newtheorem*{Cor6}{\cref{cor:cartesian}}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{oproblem}[theorem]{Open~Problem}
\newtheorem*{Volconj1}{\cref{conj:volPPerm}}
\newtheorem*{Faceconj}{\cref{mn-chain-face}}
\newtheorem*{Volconj2}{\cref{ppermvol2}}
\theoremstyle{definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}
\theoremstyle{remark}
\newcommand{\da}{\hs{-2pt}\downarrow}
\newcommand{\zba}{\bar{z}}
\newcommand{\fI}{{\mathfrak I}}
\newcommand{\fR}{{\mathfrak R}}
\newcommand{\Ih}{\hat{I}}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\ble}{\begin{lem}}
\newcommand{\ele}{\end{lem}}
\newcommand{\bth}{\begin{thm}}
\renewcommand{\eth}{\end{thm}}
\newcommand{\bpr}{\begin{prop}}
\newcommand{\epr}{\end{prop}}
\newcommand{\bco}{\begin{cor}}
\newcommand{\eco}{\end{cor}}
\newcommand{\bcon}{\begin{conj}}
\newcommand{\econ}{\end{conj}}
\newcommand{\bde}{\begin{defn}}
\newcommand{\ede}{\end{defn}}
\newcommand{\bex}{\begin{exa}}
\newcommand{\eex}{\end{exa}}
\newcommand{\barr}{\begin{array}}
\newcommand{\earr}{\end{array}}
\newcommand{\btab}{\begin{tabular}}
\newcommand{\etab}{\end{tabular}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand{\bal}{\begin{align*}}
\newcommand{\bce}{\begin{center}}
\newcommand{\ece}{\end{center}}
\newcommand{\bpi}{\begin{picture}}
\newcommand{\epi}{\end{picture}}
\newcommand{\bpp}{\begin{picture}}
\newcommand{\epp}{\end{picture}}
\newcommand{\bfi}{\begin{figure} \begin{center}}
\newcommand{\efi}{\end{center} \end{figure}}
\newcommand{\bprf}{\begin{proof}}
\newcommand{\eprf}{\end{proof}\medskip}
\newcommand{\bma}{\mbox{\boldmath $a$}}
\newcommand{\bmb}{\mbox{\boldmath $b$}}
\newcommand{\bmk}{\mbox{\boldmath $k$}}
\newcommand{\bml}{\mbox{\boldmath $l$}}
\newcommand{\bmn}{\mbox{\boldmath $n$}}
\newcommand{\bbC}{{\mathbb C}}
\newcommand{\bbF}{{\mathbb F}}
\newcommand{\bbM}{{\mathbb M}}
\newcommand{\bbn}{{\mathbb n}}
\newcommand{\bbP}{{\mathbb P}}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\bbR}{{\mathbb R}}
\newcommand{\bbS}{{\mathbb S}}
\newcommand{\bbZ}{{\mathbb Z}}
\newcommand{\cA}{\mathcal{ A}}
\newcommand{\cAB}{\mathcal{ AB}}
\newcommand{\cAD}{\mathcal{ AD}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cBC}{\mathcal{ BC}}
\newcommand{\cC}{\mathcal{ C}}
\newcommand{\cD}{\mathcal{ D}}
\newcommand{\cDB}{\mathcal{ DB}}
\newcommand{\cE}{\mathcal{ E}}
\newcommand{\cF}{\mathcal{F} }
\newcommand{\cG}{\mathcal{ G}}
\newcommand{\cH}{\mathcal{ H}}
\newcommand{\cI}{\mathcal{ I}}
\newcommand{\cIF}{\mathcal{ IF}}
\newcommand{\cJ}{\mathcal{ J}}
\newcommand{\cK}{\mathcal{ K}}
\newcommand{\cL}{\mathcal{ L}}
\newcommand{\cm}{\mathcal{ m}}
\newcommand{\cM}{\mathcal{ M}}
\newcommand{\cn}{\mathcal{ n}}
\newcommand{\cnBC}{\mathcal{ nBC}}
\newcommand{\cO}{\mathcal{ O}}
\newcommand{\cP}{{\mathcal{P}}}
\newcommand{\cPD}{\mathcal{ PD}}
\newcommand{\cQ}{\mathcal{ Q}}
\newcommand{\cR}{\mathcal{ R}}
\newcommand{\cRF}{\mathcal{ RF}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{ T}}
\newcommand{\cTb}{\ol\mathcal{ T}}
\newcommand{\cV}{\mathcal{ V}}
\newcommand{\cW}{\mathcal{ W}}
\newcommand{\cX}{\mathcal{ X}}
\newcommand{\cY}{\mathcal{ Y}}
\newcommand{\cZ}{\mathcal{ Z}}
\newcommand{\df}{\dot{f}}
\newcommand{\dF}{\dot{F}}
\newcommand{\fg}{{\mathfrak g}}
\newcommand{\fG}{{\mathfrak G}}
\newcommand{\fgt}{\tilde{\mathfrak g}}
\newcommand{\fgl}{{\mathfrak gl}}
\newcommand{\fL}{{\mathfrak L}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\fsl}{{\mathfrak sl}}
\newcommand{\at}{\tilde{a}}
\newcommand{\ct}{\tilde{c}}
\newcommand{\dt}{\tilde{d}}
\newcommand{\pt}{\tilde{p}}
\newcommand{\Bt}{\tilde{B}}
\newcommand{\Gt}{\tilde{G}}
\newcommand{\Ht}{\tilde{H}}
\newcommand{\Kt}{\tilde{K}}
\newcommand{\nt}{\tilde{n}}
\newcommand{\St}{\tilde{S}}
\newcommand{\Xt}{\tilde{X}}
\newcommand{\alt}{\tilde{\alpha}}
\newcommand{\bet}{\tilde{\beta}}
\newcommand{\rht}{\tilde{\rho}}
\newcommand{\Pit}{\tilde{\Pi}}
\newcommand{\tal}{\tilde{\alpha}}
\newcommand{\tbe}{\tilde{\beta}}
\newcommand{\tPi}{\tilde{\Pi}}
\newcommand{\ab}{\ol{a}}
\newcommand{\Ab}{\ol{A}}
\newcommand{\Bb}{\ol{B}}
\newcommand{\cb}{\ol{c}}
\newcommand{\Cb}{{\ol{C}}}
\newcommand{\db}{\ol{d}}
\newcommand{\Db}{\ol{D}}
\newcommand{\eb}{\ol{e}}
\newcommand{\Eb}{\ol{E}}
\newcommand{\fb}{\ol{f}}
\newcommand{\Fb}{\ol{F}}
\newcommand{\Gb}{\ol{G}}
\newcommand{\Hb}{\ol{H}}
\newcommand{\ib}{\ol{\imath}}
\newcommand{\Ib}{\ol{I}}
\newcommand{\jb}{\ol{\jmath}}
\newcommand{\Jb}{\ol{J}}
\newcommand{\kb}{\ol{k}}
\newcommand{\Kb}{\ol{K}}
\newcommand{\nb}{\ol{n}}
\newcommand{\pb}{\ol{p}}
\newcommand{\Pb}{\ol{P}}
\newcommand{\Phib}{\ol{\Phi}}
\newcommand{\Qb}{\ol{Q}}
\newcommand{\rb}{\ol{r}}
\newcommand{\Rb}{\ol{R}}
\newcommand{\Sb}{\ol{S}}
\newcommand{\tb}{\ol{t}}
\newcommand{\Tb}{\ol{T}}
\newcommand{\Ub}{\ol{U}}
\newcommand{\Wb}{\ol{W}}
\newcommand{\xb}{\ol{x}}
\newcommand{\Xb}{\ol{X}}
\newcommand{\yb}{\ol{y}}
\newcommand{\Yb}{\ol{Y}}
\newcommand{\zb}{\ol{z}}
\newcommand{\Zb}{\ol{Z}}
\newcommand{\pib}{\ol{\pi}}
\newcommand{\sib}{\ol{\si}}
\newcommand{\degb}{\ol{\deg}}
\newcommand{\vj}{\vec{\jmath}}
\newcommand{\vr}{\vec{r}}
\newcommand{\vv}{\mathbf{v}}
\newcommand{\ww}{\mathbf{w}}
\newcommand{\uu}{\mathbf{u}}
\newcommand{\vw}{\vec{w}}
\newcommand{\ttab}{\{t\}}
\newcommand{\stab}{\{s\}}
\newcommand{\RR}{\mathbb{R}}

\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\LHS}{LHS}
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\Pyr}{Pyr}
\DeclareMathOperator{\Conv}{ConvexHull}
\DeclareMathOperator{\RHS}{RHS}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\spa}{span}
\DeclareMathOperator{\Supp}{Supp}
\DeclareMathOperator{\sus}{susp}
\DeclareMathOperator{\simp}{\Delta}
\DeclareMathOperator{\vol}{Vol}
\DeclareMathOperator{\nvol}{nVol}
\DeclareMathOperator{\ehr}{Ehr}
\newcommand{\e}{\textbf{e}}
\newcommand{\ds}{\displaystyle}

%% define your title in the usual way
\title[Partial Permutohedra]{Partial Permutohedra}

\author[R. E. Behrend, F. Castillo, A. Chavez, A. Diaz-Lopez, L. Escobar, P. Harris, E. Insko]{Roger E. Behrend\thanks{\href{mailto:behrendr@cardiff.ac.uk}{behrendr@cardiff.ac.uk}. Roger E. Behrend was partially supported by Leverhulme Trust Grant RPG-2019-083.}\addressmark{1},
 Federico Castillo\thanks{\href{mailto:federico.castillo@mat.uc.cl}{federico.castillo@mat.uc.cl}. Federico Castillo was partially supported by  FONDECYT Grant 1221133.}\addressmark{2},
 Anastasia Chavez\thanks{\href{mailto:amc59@stmarys-ca.edu}{amc59@stmarys-ca.edu}.}\addressmark{3},
 Alexander Diaz-Lopez\thanks{\href{mailto:alexander.diaz-lopez@villanova.edu}{alexander.diaz-lopez@villanova.edu}.}\addressmark{4},
 Laura Escobar\thanks{\href{mailto:laurae@wustl.edu}{laurae@wustl.edu}. Laura Escobar was partially supported by NSF Grant DMS-1855598 and NSF CAREER Grant DMS-2142656.}\addressmark{5},
 Pamela Harris\thanks{\href{mailto:peharris@uwm.edu}{peharris@uwm.edu}. Pamela Harris was partially supported by a Karen Uhlenbeck EDGE Fellowship.}\addressmark{6},
\and Erik Insko\thanks{\href{mailto:einsko@fgcu.edu}{einsko@fgcu.edu}. }\addressmark{7}
}

\address{\addressmark{1}School of Mathematics, Cardiff University, Cardiff, UK\\ \addressmark{2}Departamento de Matem\'aticas, Pontificia Universidad Cat\'olica de Chile, Santiago, Chile\\ \addressmark{3}Department of Mathematics and Computer Science, Saint Mary's College of California, Moraga, CA, USA\\ \addressmark{4}Department of Mathematics and Statistics, Villanova University, Villanova, PA, USA\\ \addressmark{5}Department of Mathematics and Statistics, Washington University in St.~Louis, St.~Louis, MO, USA\\ \addressmark{6}Department of Mathematical Sciences, University of Wisconsin Milwaukee, Milwaukee, WI, USA \& Department of Mathematics and Statistics, Williams College, Williamstown, MA, USA\\ \addressmark{7}Department of Mathematics, Florida Gulf Coast University, Fort Myers, FL, USA}

%% 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{Partial permutohedra are lattice polytopes which were recently introduced 
and studied by Heuer and Striker~[arXiv:2012.09901].
For positive integers $m$ and $n$, the partial permutohedron~$\mathcal{P}(m,n)$
is the convex hull of all vectors in $\{0,1,\ldots,n\}^m$ whose nonzero entries are distinct. 
We study the face lattice, volume and Ehrhart polynomial of $\mathcal{P}(m,n)$, 
and our methods and results include the following. For any $m$ and $n$, we obtain a 
bijection between the nonempty faces of $\mathcal{P}(m,n)$ and certain chains of subsets of $\{1,\dots,m\}$, 
thereby confirming a conjecture of Heuer and Striker.
We use this characterization of faces to obtain a closed expression for the $h$-polynomial of~$\mathcal{P}(m,n)$.  For any $m$ and $n$ with $n\ge m-1$, we 
use a pyramidal subdivision of $\mathcal{P}(m,n)$ to establish
a recursive formula for the normalized volume of $\mathcal{P}(m,n)$,
from which we then obtain closed expressions for this volume.
We also use a sculpting 
process (in which $\mathcal{P}(m,n)$ is reached by successively removing certain
pieces from a simplex or hypercube) to obtain closed expressions for the 
Ehrhart polynomial of $\mathcal{P}(m,n)$ with arbitrary $m$ and fixed $n\le 3$, the 
volume of~$\mathcal{P}(m,4)$ with arbitrary $m$, and the Ehrhart polynomial
of $\mathcal{P}(m,n)$ with fixed $m\le4$ and arbitrary $n\ge m-1$.}
%% 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{Lattice polytopes, Ehrhart polynomials, partial permutohedra, generalized permutohedra.}

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

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

\begin{document}

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

\section{Introduction}\label{section:intro}
Computing the volume of a polytope is hard, even when the complete face structure is known~\cite{khachiyan}.
In fact, few exact volume formulas have been discovered in much generality.
Stanley gave a notable volume formula for the regular permutohedron $\Pi(1,2,\dots,m)$, specifically that its normalized volume is $m^{m-2}$~\cite[Example~3.1]{stanley}.
More generally, Postnikov~\cite{postnikov} studied the permutohedron $\Pi(z_1,\ldots,z_m)$ (which is the convex hull of all vectors obtained by permuting the entries of an arbitrary vector $(z_1,\ldots,z_m)$
in~$\RR^m$), as well as a certain class of generalized
permutohedra, and obtained
three distinct formulas for the volume of $\Pi(z_1,\dots,z_m)$~\cite[Theorems~3.1,~5.1 and~17.1]{postnikov}, each one subtle in its own way.

In this paper, we study a related family of polytopes  called \emph{partial permutohedra}, which were introduced recently by Heuer and Striker~\cite{HS}.  For positive integers~$m$ and~$n$, the partial permutohedron~$\cP(m,n)$
is the convex hull of all vectors in $\{0,1,\ldots,n\}^m$ whose nonzero entries are distinct.  These lattice polytopes are anti-blocking versions of certain permutohedra.
We also note that for any $n\ge m$, $\cP(m,n)$ is combinatorially equivalent to the $m$-\emph{stellohedron}
which, for example, has been studied in~\cite[Section 10.4]{PRW} and  has appeared recently in connection with matroid theory~\cite{stellahedron}.

We expand on the work of Heuer and Striker~\cite{HS} by obtaining,
in \cref{thm-faces-chains}, a bijection between the nonempty faces of~$\cP(m,n)$ and certain chains of subsets of $\{1,\dots,m\}$, 
for any~$m$ and~$n$, thus proving Conjecture~5.25 of~\cite{HS}.
This conjecture has also, very recently, been independently proved by Black and Sanyal~\cite[Theorem~6.5]{black2022flag}.
We then use this characterization of the faces of~$\cP(m,n)$ to obtain, 
in \cref{thm-h-vector-bijective},
a closed expression for the $h$-polynomial of $\cP(m,n)$ with any $m$ and $n$.

Our results for the volumes of partial permutohedra include the following.
In \cref{thm:recursion for volume of P(mn)}, we 
use a technique, in which $\cP(m,n)$ is subdivided into certain pyramids, to establish a recursive formula for the normalized volume of $\cP(m,n)$, for any $m$ and $n$ with $n\geq m-1$.
Using this recursion and Stong's computation for a particular case \cite{AMM_solution}, we are then able to prove, in \cref{thm:closedformulav(mn)}, a closed expression for the normalized volume of $\cP(m,n)$ for the case $n\geq m-1$.
For the remaining case $m-1>n$, the combinatorial type of $\cP(m,n)$ depends on both~$m$ and~$n$ 
(whereas for $n\ge m-1$ it depends only on $m$), which suggests that finding a completely general closed formula for the volume in this case is unlikely.

We also compute the Ehrhart polynomial of $\cP(m,n)$ when $m$ or $n$ is small.
One of our main techniques is based on the idea, exploited by algebraists in the days of yore, of completing the (hyper)cube. 
We start with a lattice polytope for which we know the  volume or Ehrhart polynomial, and then carefully remove pieces until we reach the polytope of interest. 
This idea makes itself apparent after analyzing certain expressions, as given in \cref{ex:formulas}, for the normalized volume of $\cP(m,n)$ for small fixed $m$ and any $n\ge m-1$.  These expressions are polynomials in $n$,
with all coefficients negative, except in the leading term which is $m!\,n^m$, the normalized volume of a hypercube in~$\RR^m$ of side-length~$n$.  This suggests that we start with a hypercube from which we can sculpt a partial permutohedron, and this is precisely what we do in \cref{sec:volppn} for the case $n\ge m-1$.  This sculpting approach has been used recently to compute the Ehrhart polynomials of matroid polytopes starting from the hypersimplex. See~\cite{ferroni} for sparse paving matroids, and~\cite{jeremy} for paving matroids.

In \cref{thm_n_fixed}, we provide results for the normalized volume
and Ehrhart polynomial of~$\cP(m,n)$ with arbitrary~$m$ and fixed $n\le4$,
where these are obtained by sculpting $\cP(m,n)$ from a $\binom{n+1}{2}$-dilated standard $m$-simplex $\simp_m=
\{\mathbf{x}\in\RR^m\mid x_i\ge0\text{ for all }i,\;\sum_{i=1}^mx_i\le 1\}$.  For example, we find that the normalized volume of $\cP(m,2)$ is $3^m-3$, thereby confirming Conjecture~5.30 of~\cite{HS}, 
we obtain explicit expressions for the Ehrhart polynomials
of $\cP(m,1)$, $\cP(m,2)$ and $\cP(m,3)$ with arbitrary~$m$,
and we obtain an explicit expression for the normalized volume of~$\cP(m,4)$ with 
arbitrary $m$.

In \cref{thm_m_fixed}, we provide explicit expressions for the
Ehrhart polynomials of \linebreak $\cP(m,n)$ with fixed $m\le 4$ and 
arbitrary $n\geq m-1$, where these are obtained by sculpting $\cP(m,n)$
from a hypercube $[0,n]^m$.

We end, in \cref{conj-Ehr-expl}, by conjecturing a closed expression for the Ehrhart polynomial of $\cP(m,n)$ with $n\geq m-1$ which generalizes our volume and Ehrhart polynomial results for this case.

\section{Faces of partial permutohedra} \label{section:prelim}
\subsection{Description of the partial permutohedron $\cP(m,n)$}
We introduce the partial permutohedron $\cP(m,n)$, for any positive integers $m$ and $n$, using a similar approach to that used by Heuer and Striker~\cite[Section~5]{HS}.

\begin{definition}
Let the \emph{partial permutohedron} \emph{$\cP(m,n)$} be the polytope given by the convex hull of all vectors in $\{0,1,\ldots,n\}^m$ whose nonzero entries are distinct.
\end{definition}

It follows from the definition that~$\cP(m,n)$ is a lattice polytope.
As noted in~\cite[Remark 5.5]{HS}, it has dimension $m$.
From \cite[Proposition 5.7]{HS}, its vertices are the vectors in~$\bbR^m$ with entries of zero in any $m-k$ positions, and with the other $k$ entries being $n,n-1,\ldots,n-k+1$ in any order, where~$k$ ranges from $0$ to $\min(m,n)$.
Its facet description is given in Theorems 5.10 and 5.11 in \cite{HS} as
\begin{multline}
\label{facetdesc}\cP(m,n)\\
=\left\{\mathbf{x}\in\mathbb{R}^m\:\left|\,\begin{array}{rcll}0&\leq& x_i,& \textrm{for all }i\in[m],\\[1.5mm]
\sum_{i\in S} x_i&\leq&\binom{n+1}{2}-\binom{n+1-|S|}{2},&\textrm{for all nonempty }S\subseteq[m]\\&&&\textrm{with }|S|\leq n-1\textrm{ or }|S|=m\end{array}\!\!
\right.\right\},\end{multline}
where the inequalities correspond to distinct facets, and where $\binom{n+1-|S|}{2}$ is taken to be 0 if $n+1-|S|\le1$ (which occurs if $|S|=m\ge n$).  Also, $[m]$ denotes the set $\{1,\ldots,m\}$.

In \cite[Theorem~5.27]{HS}, it is shown that $\cP(m,n)$ is a projection of the partial permutation polytope $\mathrm{PPerm}(m,n)$ (or polytope of $m\times n$ doubly substochastic matrices), which can be defined as the convex hull in~$\RR^{mn}$ of all $m\times n$ matrices in which each entry is in $\{0,1\}$ and each row and column contains at most one~1.
We remark that $\mathrm{PPerm}(m,n)$ can be regarded as the
matching polytope of the complete bipartite graph~$K_{m,n}$,
and it is thus of interest in the context of combinatorial optimization
(see, for example, \cite[Chapters~18 and 25]{Schrijver}).
The polytope $\mathrm{PPerm}(m,m)$ was studied by Kohl, Olsen and Sanyal \cite[Section 5]{kohl2020unconditional}.

\subsection{The faces of $\cP(m,n)$}
The whole face structure of $\cP(m,n)$ 
was conjectured in \cite[Conjecture 5.25]{HS}, and we prove this conjecture in \cref{thm-faces-chains}.
Recently, this was independently proved by Black and Sanyal~\cite[Theorem~6.5]{black2022flag} in the context of monotone path polytopes of polymatroids.
To characterize the faces of $\cP(m,n)$, we need some further definitions,
as follows.

\begin{definition}\label{def-Boolean}
The \emph{Boolean lattice} $\mathcal{B}_m$ is the poset consisting of subsets $A\subseteq[m]$, ordered by
inclusion, where $A\in\mathcal{B}_m$ has rank $|A|$, the cardinality of $A$. A \emph{chain} $C$ in $\mathcal{B}_m$
is a nonempty ordered collection $C= (A_1\subsetneq A_2\subsetneq\cdots\subsetneq A_\ell)$ of subsets $A_i\in \mathcal{B}_m$. We say that a rank $i$ is
\emph{missing} from a chain $C$ in~$\mathcal{B}_m$ if there is no subset of rank $i$ in $C$ and there is a subset of rank greater than $i$ in $C$.
\end{definition}

\begin{definition}
Let $\mathcal{C}(m,n)$ denote the set of all chains $(A_1\subsetneq \cdots\subsetneq A_\ell)$ in $\mathcal{B}_m$ which satisfy the following:
\begin{itemize}
\item If $A_1\neq\varnothing$, then $|A_\ell\setminus A_1|\le n-1$.
\item If $A_1=\varnothing$ and $\ell\geq2$, then $|A_\ell\setminus A_2|\le n-1$.
\end{itemize}
\end{definition}

Our theorem for the face structure of $\cP(m,n)$, with any $m$ and $n$, is as follows.

\begin{theorem}\label{thm-faces-chains}
Given a chain $C=(A_1\subsetneq \cdots\subsetneq A_\ell)$ in $\mathcal{C}(m,n)$, let $\cF_C$ be the intersection of $\cP(m,n)$ with the following hyperplanes:
\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
\item $\{\mathbf{x}\in\bbR^m \mid x_i=0\}$, for all $i\in[m]\setminus A_\ell$.
\item $\left\{\mathbf{x}\in\bbR^m\,\middle |\, \sum_{i\in A_\ell\setminus A_j} x_i=\binom{n+1}{2}-\binom{n+1-|A_\ell\setminus A_{j}|}{2}\right\}$, for all $2\le j\le \ell-1$,
and also for $j=1$ unless $A_1=\varnothing$ and $|A_\ell|\ge n$.
\item $\left\{\mathbf{x}\in\bbR^m\,\middle |\,\sum_{i=1}^mx_i=\binom{n+1}{2}\right\}$, if $A_1=\varnothing$ and $|A_\ell|\ge n$.
\end{enumerate}
Then the following is a bijection:
\begin{align*}
\mathcal{C}(m,n)&\longrightarrow \{\text{nonempty faces of } \cP(m,n)\},\\
C&\longmapsto \cF_C.
\end{align*}
Moreover, this bijection maps chains with $k$ missing ranks to faces of dimension $k$,
for each $k=0,\ldots,m$.
\end{theorem}
Our proof of \cref{thm-faces-chains} involves verifying directly 
that the stated mapping is well-defined, injective and surjective. 

\subsection{The $h$-polynomial of $\cP(m,n)$}
We now consider the $h$-polynomial of $\cP(m,n)$.
Given a $d$-dimensional polytope $P$ and $0\le i\le d$, let $f_i(P)$ denote the number of $i$-dimensional faces of $P$.
The $f$-\emph{polynomial} of~$P$ is then defined as $f_P(t)=\sum_{i=0}^df_i(P)\,t^i$, and
the $h$-\emph{polynomial} of~$P$ is defined as $h_P(t)=f_P(t-1)$.  

Since Eulerian polynomials will play a role in the $h$-polynomial of $\cP(m,n)$, we proceed to introduce them.
For a positive integer $m$, let $A_m(t)$ denote the Eulerian polynomial for~$\mathfrak{S}_m$, i.e., $A_m(t)=\sum_{i=0}^{m-1}A(m,i)\,t^i$,
where the Eulerian number $A(m,i)$ is the number of permutations in~$\mathfrak{S}_m$ with exactly $i$ descents. Also, let $A(0,i)=\delta_{0,i}$ and $A_0(t)=1$.  

Our theorem for the $h$-polynomial of $\cP(m,n)$, with any $m$ and $n$, is as follows.

\begin{theorem}\label{thm-h-vector-bijective}
The $h$-polynomial of $\cP(m,n)$ is 
\begin{equation}
h_{\cP(m,n)}(t)=1+\sum_{i=0}^{n-1}\;\sum_{j=1}^{m-i}\binom{m}{i}\,A_i(t)\:t^j.
\end{equation}
This is equivalent to the recurrence relation and initial condition
\begin{equation}\label{eq-h-poly-rec}h_{\cP(m,n+1)}(t)=h_{\cP(m,n)}(t)+\binom{m}{n}\,A_n(t)\sum_{i=1}^{m-n}t^i,\quad h_{\cP(m,1)}(t)=\sum_{i=0}^mt^i.\end{equation}
\end{theorem}
Our proof of \cref{thm-h-vector-bijective} uses the characterization
of faces provided by \cref{thm-faces-chains} to verify~\eqref{eq-h-poly-rec}.

\section{Volume of $\cP(m,n)$ with $n\geq m-1$} \label{sec:volppm}
Let $v(m,n)$ denote the normalized volume of $\cP(m,n)$.
Heuer and Striker~\cite[Figure 6]{HS} used SageMath to compute~$v(m,n)$ for $m,n\leq 7$.  
In this section, we consider $v(m,n)$ for $n\geq m-1$.
The first result is a recursive formula, and is proved by subdividing $\cP(m,n)$ into pyramids, for which
the apex is the origin and the base is a facet that does not
contain the origin.  The same method was used to obtain \cref{thm:recursion for volume of P(mn)} for the case $n=m-1$ in~\cite[Theorem~4.1]{AW} and~\cite[Problem~12191]{AMM_solution}.

\begin{theorem}\label{thm:recursion for volume of P(mn)}
For any $m$ and $n$ with $n\geq m-1$,  the normalized volume of $\cP(m,n)$ is given recursively by
\begin{equation}
\label{eq:recursion1}
v(m,n) = (m-1)!\,\sum_{k=1}^m k^{k-2}\,\frac{v(m-k,n-k)}{(m-k)!}\left (kn-\binom{k}{2}\right)\binom{m}{k},
\end{equation}
with the initial condition $v(0,n)=1$.
\end{theorem}
 
\begin{example}\label{ex:formulas}
For $1\le m\le 7$ and $n\ge m-1$, \cref{thm:recursion for volume of P(mn)} gives the following expressions for $v(m,n)$:
{\small
\begin{equation*}
\begin{array}{@{}l@{\;\,}r@{\;\,}r@{\;\,}r@{\;\,}r@{\;\,}r@{\;\,}r@{\;\,}r@{\;\,}r@{}}
v(1,n)=&&n,&&&&&&\\
v(2,n)=&-1&&+2n^2,&&&&&\\
v(3,n)=&-6 &-9n&&+6n^3,&&&&\\
v(4,n)=&-54 &-96n&-72n^2&&+24n^4,&&&\\
v(5,n)=&-840&-1350n &-1200n^2&-600n^3&&+120n^5,&\\
v(6,n)=&-21150 &-30240n&-24300n^2&-14400n^3&-5400n^4&&+720n^6,\\
v(7,n)=&- 782460&- 1036350n&- 740880n^2& - 396900n^3& - 176400n^4& - 52920n^5& &+5040n^7.
\end{array}\end{equation*}}
Note that the expression $v(2,n)=2n^2-1$ was obtained in~\cite[Theorem~5.29]{HS}.
\end{example}

Using the recursion of~\eqref{eq:recursion1}, and building on ideas from \cite{AW} and~\cite[Problem~12191]{AMM_solution}, we are able to obtain the following explicit expressions for $v(m,n)$.

\begin{theorem}\label{thm:closedformulav(mn)}
For any $m$ and $n$ with $n\geq m-1$, the normalized volume of $\cP(m,n)$ is explicitly
\begin{equation}\label{eq:vmn}
v(m,n)=-\frac{m!}{2^m}\sum_{0\le i\le k\le m}\binom{m}{k}\,\binom{k}{i}\,(2i-3)!!\,(2n)^{m-k},\end{equation}
or equivalently
\begin{equation}\label{thm:closedformulav(m,n)2}v(m,n)=-\frac{m!}{2^m}\,\sum_{i=0}^m\,\binom{m}{i}(2i-3)!!\,(2n+1)^{m-i}.\end{equation}
\end{theorem}

\begin{remark}
We note that, by regarding $n$ as fixed and
defining $V(m,n)$ to be the RHS of~\eqref{eq:vmn}
or~\eqref{thm:closedformulav(m,n)2} for any nonnegative integer $m$
(with the restriction $n\geq m-1$ no longer applying)
we have the
generating function expression
\begin{equation}\label{thm:closedformulav(m,n)3}
\sum_{m=0}^\infty\frac{V(m,n)\,z^m}{(m!)^2}=
\sqrt{1-z}\,e^{(n+1/2)z}.
\end{equation}
Furthermore, by defining $W(m,n)=V(m,n)/m!$, we have
the simple recurrence relation
\begin{equation}\label{eq-vol-rec}W(m,n)=(m+n-1)\,W(m-1,n)-(m-1)(n+1/2)\,W(m-2,n),\end{equation}
with initial conditions $W(0,m)=1$ and $W(1,m)=n$.
\end{remark}

\section{The Ehrhart polynomial of some partial permutohedra}\label{sec:volppn}
We now shift our focus to the computation of the Ehrhart polynomial
of $\cP(m,n)$ for small fixed values of $m$ or $n$.

\subsection{Ehrhart polynomials}
We begin by recalling some basic facts about Ehrhart polynomials.
For a lattice polytope $\mathcal{P}\subseteq \mathbb{R}^m$, the function $|t\,\mathcal{P}\cap\mathbb{Z}^m|$ 
of a positive integer variable~$t$ (where~$t\,\mathcal{P}$
denotes the $t$-th dilate $\{t\,\mathbf{x}\mid\mathbf{x}\in\cP\}$ of~$\cP$) is known to 
agree with a polynomial $\ehr(\mathcal{P})\in\mathbb{Q}[t]$ of degree $\dim(\mathcal{P})$, called the \emph{Ehrhart polynomial} of~$\cP$.
Furthermore, the coefficient of the leading term of $\ehr(\mathcal{P})$ is the relative volume of~$\cP$,
where this is a normalized volume if $\cP$ is non-full-dimensional, see \cite[Corollary 3.20]{beck2007computing}.
For the polytopes $\cP(m,n)$ considered here, the 
normalized volume is $m!$ times the relative volume.
		
\subsection{The sculpting strategy}
All of our remaining proofs follow the same sculpting strategy. We start with a well-known polytope and remove other known polytopes by adding inequalities, until we obtain the desired 
polytope $\cP(m,n)$.	
More precisely, to compute the volume or Ehrhart polynomial of $\cP(m,n)$, we  create a sequence of lattice polytopes $\cP_1,\dots,\cP_k=\cP(m,n)$, where~$\cP_1$ is either the $\binom{n+1}{2}$-dilated standard $m$-simplex $\binom{n+1}{2}\simp_m$ (in \cref{thm_n_fixed}) or the $m$-cube $[0,n]^m$ of side-length~$n$ (in \cref{thm_m_fixed}).  We then obtain $\cP_{i+1}$ from $\cP_i$ by adding inequalities to $\cP_i$, i.e., by taking an intersection of~$\cP_i$ with closed halfspaces, and thus removing some pieces from $\cP_i$.

A simple example which illustrates this idea is as follows.
\begin{example}
\cref{fig:32exploded} shows the partial permutohedron $\cP(3,2)=
\{\mathbf{x}\in\RR^3\mid 0\le x_i\le 2\text{ for all }i\in[3],\;x_1+x_2+x_3\le3\}$ as the $3$-dilated standard $3$-simplex
$3\simp_3$, from which three copies of the standard $3$-simplex $\simp_3$
have been removed.  
\begin{figure}[ht]
\centering
\includegraphics[height=2in]{32.png}
\caption{Illustration of $P(3,2)$ as $3\simp_3$, from which three copies of $\simp_3$ have been removed.}
\label{fig:32exploded}
\end{figure}
\end{example}

Further illustrations of the sculpting process are given in
\cref{fig:33exploded} (for $\cP(3,3)$) and \cref{fig:thm:p3n} (for $\cP(3,n)$ with $n\ge2$).

\subsection{New results}\label{sec:pmproofs}
We have the following formulas for $\cP(m,n)$ with 
arbitrary $m$ and $n\le4$. 
The expression for $v(m,2)$ was conjectured in \cite[Conjecture 5.30]{HS}.
Our sculpting methods become harder as $n$ grows, and for $\cP(m,4)$ we have only computed the volume.

\begin{theorem}\label{thm_n_fixed}
The following statements are true.
\hfill
\begin{enumerate}
\item For any $m$, $\cP(m,1)$ is the standard $m$-simplex~$\Delta_m$,
and so $\cP(m,1)$ has Ehrhart polynomial $\ehr(\cP(m,1))=\binom{t+m}{m}$ and normalized volume $v(m,1)=1$.
\item For any $m$, the Ehrhart polynomial of $\cP(m,2)$ is 
\begin{equation}\label{eq:pm2}\ehr(\cP(m,2))=\binom{3t+m}{m}-m\binom{t+m-1}{m},\end{equation}
and thus, taking $m!$ times the coefficient of $t^m$ in~$\ehr(\cP(m,2))$,
the normalized volume of $\cP(m,2)$ is 
\begin{equation*}v(m,2)=3^m-m.\end{equation*}
\item For any $m$, the Ehrhart polynomial of $\cP(m,3)$ is
\begin{multline}
\label{eq:ehrpm3}
\ehr(\cP(m,3))
=\binom{6t+m}{m}-m\binom{3t+m-1}{m}\\
-\binom{m}{2}\left(\binom{t+m-1}{m}+(m-2)\binom{t+m-2}{m}\right),
\end{multline}
and thus, taking $m!$ times the coefficient of $t^m$ in~$\ehr(\cP(m,3))$,
the normalized volume of $\cP(m,3)$ is 
\begin{equation*}v(m,3)= 6^m-m\,3^m-(m-1)\binom{m}{2}.\end{equation*}
\item For any $m$, the normalized volume of $\cP(m,4)$ is
\begin{equation}
\label{eq:Pm4}
v(m,4)=10^m-m\,6^m-\frac{m(m-1)(m-3)}{6}\,3^m-(3m^2-6m+1)\binom{m}{3}.
\end{equation}
\end{enumerate}
\end{theorem}

\begin{figure}[ht]
\centering
\includegraphics[height=2in]{33.png}
\caption{The sculpting of $\cP(3,3)$ (in the center), as used in our proof of~\eqref{eq:ehrpm3} with $m=3$.}
\label{fig:33exploded}
\end{figure}
Having calculated $v(m,n)$ for $n\le4$, an obvious open problem remains.
\begin{oproblem}
Find $v(m,n)$ for all $m,n$ with $n>4$.
\end{oproblem}

We now return to $\cP(m,n)$ in the case $n\geq m-1$.
It follows from Postnikov's results on generalized permutohedra \cite{postnikov}, and an interpretation of partial permutohedra as certain generalized permutohedra, that in this case
$\ehr(\cP(m,n))$ is a polynomial in $n$ of degree~$m$ and that $\cP(m,n)$ is Ehrhart positive (i.e., that each coefficient of $\ehr(\cP(m,n))$,
as a polynomial in $t$, is positive).
We obtain explicit expressions for the Ehrhart polynomial of $\cP(m,n)$ for fixed $m\le 4$ and 
arbitrary $n\geq m-1$, from which this Ehrhart positivity can also be easily verified.

\begin{theorem}\label{thm_m_fixed}
The following statements are true.
\hfill
\begin{enumerate}
\item For $m=1$ and any $n$, $\cP(1,n)$ is the line segment $[0,n]$,
and so the Ehrhart polynomial of $\cP(1,n)$ is 
\begin{equation}\label{eq:ehrp1n}
\ehr(\cP(1,n))=nt+1.\end{equation}
\item For $m=2$ and any $n$, the Ehrhart polynomial of $\cP(2,n)$ is 
\begin{equation}\label{eq:ehrp2n}
\ehr(\cP(2,n))=(n^2-1/2)\,t^2+(2n-1/2)\,t+1,
\end{equation}
where this can be obtained, as a simple application of the sculpting process, 
by constructing $\cP(2,n)$ as a square $[0,n]^2$, from which a
half-open triangle 
\[
\textrm{ConvexHull}(\{(n-1,n),\,(n,n),\allowbreak\,(n,n-1)\})\setminus \textrm{ConvexHull}(\{(n-1,n),\,(n,n-1)\})
\]
has been removed.
\item For any $n\geq 2$, the Ehrhart polynomial of $\cP(3,n)$ is
\begin{multline}\label{eq:ehrp3n}
\ehr(\cP(3,n))\\=
\left(n^3-3n/2-1\right)t^3+\left(3n^2-3n/2-3/2\right)t^2+\left(3n-3/2\right)t+1.\end{multline}
\item For any $n\geq3$, the Ehrhart polynomial of $\cP(4,n)$ is
\begin{multline}
\label{eq:ehrp4n}
\ehr(\cP(4,n))=\left(n^4-3n^2-4n-9/4\right)t^4+\left(4n^3-3n^2-6n-5/2\right)t^3\\
+\left(6n^2-6n-9/4\right)t^2+\left(4n-3\right)t+1.
\end{multline}
\end{enumerate}
\end{theorem}

\begin{figure}[ht]
\centering
\includegraphics[height=1.8in]{cube3steps.jpg}
\caption{The sculpting of $\cP(3,n)$, as used in our proof of~\eqref{eq:ehrp3n}.}
\label{fig:thm:p3n}
\end{figure}

\section{Further directions}\label{sec-further}
The expressions in~\eqref{thm:closedformulav(m,n)2} 
and~\eqref{eq:ehrp1n}--\eqref{eq:ehrp4n} lead us to the following 
conjecture of a completely explicit formula for $\ehr(\cP(m,n))$ with
any $n\ge m-1$.
\begin{conjecture}\label{conj-Ehr-expl}
We conjecture that, for any~$m$ and~$n$ with $n\ge m-1$, the Ehrhart polynomial of~$\cP(m,n)$ is explicitly
\begin{multline}\label{eq-Ehr-expl1}
\ehr(\cP(m,n))\\
=\frac{1}{2^m}\sum_{i=0}^{\lfloor m/2\rfloor}\sum_{j=2i}^m(-1)^{i+1}\,\binom{m}{m-j,\,j-2i,\,i,\,i}\,i!\:(2j-4i-3)!!\:t^{j-i}\,(2nt+t+2)^{m-j}.\end{multline}
In terms of generating functions, we have
\begin{equation}\label{eq-Ehr-expl2}
\sum_{m=0}^\infty\frac{E(m,n,t)\,(2z)^m}{m!}=
\sqrt{1-2tz}\,e^{(2nt+t+2)z-tz^2},
\end{equation}
where $E(m,n,t)$ is the RHS of~\eqref{eq-Ehr-expl1} 
for any nonnegative integer $m$, with $n$ and $t$ fixed.
\end{conjecture}

\cref{conj-Ehr-expl} can be seen to generalize \cref{thm:closedformulav(mn)}. Specifically, since
$v(m,n)/m!$ is the leading coefficient of $\ehr(\cP(m,n))$, as a polynomial in~$t$, and since the degree of this polynomial is~$m$
(as $\dim\cP(m,n)=m$), it follows that $v(m,n)/m!$ is given by $\lim_{T\to0}\bigl(T^m\,\ehr(\cP(m,n))|_{t=1/T}\bigr)$.
Now~\eqref{eq-Ehr-expl2} gives
\begin{equation*}
\sum_{m=0}^\infty\frac{E(m,n,1/t)\,(2tz)^m}{m!}
=\sqrt{1-2z}\,e^{(2n+1+2t)z-tz^2},
\end{equation*}
and taking $t\to0$ on both sides
then gives~\eqref{thm:closedformulav(m,n)3}.  

It can
also easily be checked that~\eqref{eq-Ehr-expl1} reproduces the expressions~\eqref{eq:ehrp1n}--\eqref{eq:ehrp4n} for $\ehr(\cP(m,n))$ with $m\le4$ and $n\ge m-1$.

\acknowledgements{The authors thank Spencer Backman, Jessica Striker and
Shaun Sullivan for helpful exchanges.
We thank the American Institute of Mathematics for research support through a SQuaRE grant. }

\printbibliography

\end{document}
