Generalized parking function polytopes

Abstract

A classical parking function of length $n$ is a list of positive integers $(a_1,a_2,\dots ,a_n)$ whose nondecreasing rearrangement $b_1\le b_2\le \cdots \le b_n$ satisfies $b_i\le i$. The convex hull of all parking functions of length $n$ is an $n$-dimensional polytope in ${\mathbb{R}}^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in (Amanbayeva and Wang 2022) in response to a question posed in (Stanley 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of $\mathbf{x}$-parking functions for $\mathbf{x}=(a,b,\dots ,b)$, which we refer to as $\mathbf{x}$-parking function polytopes. We explore connections between these $\mathbf{x}$-parking function polytopes, the Pitman-Stanley polytope, and the partial permutahedra of (Heuer and Striker 2022). In particular, we establish a closed-form expression for the volume of $\mathbf{x}$-parking function polytopes. This allows us to answer a conjecture of (Behrend et al. 2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

29 pages, 3 figures, comments welcome!

Cited by in corpus (1)

• Combinatorics of generalized parking-function polytopes