Ehrhart polynomials of partial permutohedra

This is the authors' abstract. We don't add key points for this paper.

For positive integers m and n, the partial permutohedron P(m,n) is a certain integral polytope in Rᵐ, which can be defined as the convex hull of the vectors from \0,1,…,n\ᵐ whose nonzero entries are distinct. For $n=m-1$, P(m,m-1) is (after translation by (1,…,1)) the polytope Pₘ of parking functions of length m, and for n≥ m, P(m,n) is combinatorially equivalent to an m-stellohedron. The main result of this paper is an explicit expression for the Ehrhart polynomial of P(m,n) for any m and n with n≥ m-1. The result confirms the validity of a conjecture for this Ehrhart polynomial in arXiv:2207.14253, and the $n=m-1$ case also answers a question of Stanley regarding the number of integer points in Pₘ. The proof of the result involves transforming P(m,n) to a unimodularly equivalent polytope in Rᵐ⁺¹, obtaining a decomposition of this lifted version of P(m,n) with n≥ m-1 as a Minkowski sum of dilated coordinate simplices, applying a result of Postnikov for the number of integer points in generalized permutohedra of this form, observing that this gives an expression for the Ehrhart polynomial of P(m,n) with n≥ m-1 as an edge-weighted sum over graphs (with loops and multiple edges permitted) on m labelled vertices in which each connected component contains at most one cycle, and then applying standard techniques for the enumeration of such graphs.