Combinatorics of generalized parking-function polytopes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913262165032960 |
|---|---|
| author | Bayer, Margaret M. Borgwardt, Steffen Chambers, Teressa Daugherty, Spencer Dawkins, Aleyah Deligeorgaki, Danai Liao, Hsin-Chieh McAllister, Tyrrell Morrison, Angela Nelson, Garrett Vindas-Meléndez, Andrés R. |
| author_facet | Bayer, Margaret M. Borgwardt, Steffen Chambers, Teressa Daugherty, Spencer Dawkins, Aleyah Deligeorgaki, Danai Liao, Hsin-Chieh McAllister, Tyrrell Morrison, Angela Nelson, Garrett Vindas-Meléndez, Andrés R. |
| contents | For $\mathbf{b}=(b_1,\dots,b_n)\in \mathbb{Z}_{>0}^n$, a $\mathbf{b}$-parking function is defined to be a sequence $(β_1,\dots,β_n)$ of positive integers whose nondecreasing rearrangement $β'_1\leq β'_2\leq \cdots \leq β'_n$ satisfies $β'_i\leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07387 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Combinatorics of generalized parking-function polytopes Bayer, Margaret M. Borgwardt, Steffen Chambers, Teressa Daugherty, Spencer Dawkins, Aleyah Deligeorgaki, Danai Liao, Hsin-Chieh McAllister, Tyrrell Morrison, Angela Nelson, Garrett Vindas-Meléndez, Andrés R. Combinatorics 05A10, 05A15, 05A19, 52B05, 52B11, 52B15, 52B20, 52B40, For $\mathbf{b}=(b_1,\dots,b_n)\in \mathbb{Z}_{>0}^n$, a $\mathbf{b}$-parking function is defined to be a sequence $(β_1,\dots,β_n)$ of positive integers whose nondecreasing rearrangement $β'_1\leq β'_2\leq \cdots \leq β'_n$ satisfies $β'_i\leq 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. |
| title | Combinatorics of generalized parking-function polytopes |
| topic | Combinatorics 05A10, 05A15, 05A19, 52B05, 52B11, 52B15, 52B20, 52B40, |
| url | https://arxiv.org/abs/2403.07387 |