Discrete & Computational Geometry Mathematics

Combinatorics of Generalized Parking-Function Polytopes

Margaret M. Bayer, Steffen Borgwardt, Teressa Chambers, Spencer Daugherty, Aleyah Dawkins, Danai Deligeorgaki, Hsin-Chieh Liao, Tyrrell McAllister, Angela Morrison, Garrett Nelson, Andrés R. Vindas-Meléndez
Springer Nature · 2025-09-12 · DOI 10.1007/s00454-025-00770-1

Abstract

Abstract For $${\textbf {b}}=(b_1,\dots ,b_n)\in \mathbb {Z}_{>0}^n$$ b = ( b 1 , ⋯ , b n ) ∈ Z > 0 n , a $${\textbf {b}}$$ b -parking function is defined to be a sequence $$(\beta _1,\dots ,\beta _n)$$ ( β 1 , ⋯ , β n ) of positive integers whose nondecreasing rearrangement $$\beta '_1\le \beta '_2\le \cdots \le \beta '_n$$ β 1 ′ ≤ β 2 ′ ≤ ⋯ ≤ β n ′ satisfies $$\beta '_i\le b_1+\cdots + b_i$$ β i ′ ≤ b 1 + ⋯ + b i . The $${\textbf {b}}$$ b -parking-function polytope $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) is the convex hull of all $${\textbf {b}}$$ b -parking functions of length n in $$\mathbb {R}^n$$ R n . Geometric properties of $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) were previously explored in the specific case where $${\textbf {b}}=(a,b,b,\dots ,b)$$ b = ( a , b , b , ⋯ , b ) and were shown to generalize those of the classical parking-function polytope. In this work, we study $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) in full generality. We present a minimal inequality and vertex description for $$\mathfrak {X}_{n}({\textbf {b}})$$ X n ( b ) , prove it is a generalized permutahedron, and study its h -polynomial. Furthermore, we investigate $$\mathfrak {X}_{n}({\textbf {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.

Read at publisher →