Combinatorics of Generalized Parking-Function PolytopesShow others and affiliations
2026 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 76, no 1, p. 339-377Article in journal (Refereed) Published
Abstract [en]
For b=(b1,⋯,bn)∈Z>0n, a b-parking function is defined to be a sequence (β1,⋯,βn) of positive integers whose nondecreasing rearrangement β1′≤β2′≤⋯≤βn′ satisfies βi′≤b1+⋯+bi. The b-parking-function polytope Xn(b) is the convex hull of all b-parking functions of length n in Rn. Geometric properties of Xn(b) were previously explored in the specific case where b=(a,b,b,⋯,b) and were shown to generalize those of the classical parking-function polytope. In this work, we study Xn(b) in full generality. We present a minimal inequality and vertex description for Xn(b), prove it is a generalized permutahedron, and study its h-polynomial. Furthermore, we investigate Xn(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.
Place, publisher, year, edition, pages
Springer Nature , 2026. Vol. 76, no 1, p. 339-377
Keywords [en]
Building set, h-polynomial, Parking functions, Permutahedron, Polymatroid
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-370607DOI: 10.1007/s00454-025-00770-1ISI: 001571572300001Scopus ID: 2-s2.0-105015781766OAI: oai:DiVA.org:kth-370607DiVA, id: diva2:2001922
Note
QC 20250929
Not duplicate with DiVA 1958622
2025-09-292025-09-292026-06-26Bibliographically approved