Combinatorics of Generalized Parking-Function PolytopesShow others and affiliations
2025 (English)In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444Article in journal (Refereed) Epub ahead of print
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 , 2025.
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-292025-09-29Bibliographically approved