Combinatorics of generalized parking-function polytopes

Abstract

For $\mathbf{b}=(b_1,\dots ,b_n)\in {\mathbb{Z}}_{>0}^n$, a $\mathbf{b}$-parking function is defined to be a sequence $({\beta }_1,\dots ,{\beta }_n)$ of positive integers whose nondecreasing rearrangement ${\beta }_1^{\prime }\le {\beta }_2^{\prime }\le \cdots \le {\beta }_n^{\prime }$ satisfies ${\beta }_i^{\prime }\le b_1+\cdots +b_i$. The $\mathbf{b}$-parking-function polytope ${\mathfrak{X}}_n(\mathbf{b})$ is the convex hull of all $\mathbf{b}$-parking functions of length $n$ in ${\mathbb{R}}^n$. Geometric properties of ${\mathfrak{X}}_n(\mathbf{b})$ were previously explored in the specific case where $\mathbf{b}=(a,b,b,\dots ,b)$ and were shown to generalize those of the classical parking-function polytope. In this work, we study ${\mathfrak{X}}_n(\mathbf{b})$ in full generality. We present a minimal inequality and vertex description for ${\mathfrak{X}}_n(\mathbf{b})$, prove it is a generalized permutahedron, and study its $h$-polynomial. Furthermore, we investigate ${\mathfrak{X}}_n(\mathbf{b})$ through the perspectives of building sets and polymatroids, allowing us to identify its combinatorial types and obtain bounds on its combinatorial and circuit diameters.

27 pages, 4 figures, Comments welcomed!