Combinatorics of Generalized Parking-Function Polytopes

Abstract For {b}= (b₁, , bₙ) Z>₀ⁿ b = (b 1, ⋯, b n) ∈ Z > 0 n, a {b} b -parking function is defined to be a sequence (₁, , ₙ) (β 1, ⋯, β n) of positive integers whose nondecreasing rearrangement '₁ '₂ 'ₙ β 1 ′ ≤ β 2 ′ ≤ ⋯ ≤ β n ′ satisfies 'ᵢ b₁+ + bᵢ β i ′ ≤ b 1 + ⋯ + b i. The {b} b -parking-function polytope X₍ ({b}) X n (b) is the convex hull of all {b} b -parking functions of length n in Rⁿ R n. Geometric properties of X₍ ({b}) X n (b) were previously explored in the specific case where {b}= (a, b, b, , b) b = (a, b, b, ⋯, b) and were shown to generalize those of the classical parking-function polytope. In this work, we study X₍ ({b}) X n (b) in full generality. We present a minimal inequality and vertex description for X₍ ({b}) X n (b), prove it is a generalized permutahedron, and study its h -polynomial. Furthermore, we investigate X₍ ({b}) X n (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.