Vertices of the monotone path polytopes of hypersimplicies
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912665396314112 |
|---|---|
| author | Poullot, Germain |
| author_facet | Poullot, Germain |
| contents | The monotone path polytope of a polytope $P$ encapsulates the combinatorial behavior of the shadow vertex rule (a pivot rule used in linear programming) on $P$. Computing monotone path polytopes is the entry door to the larger subject of fiber polytopes, for which explicitly computing examples remains a challenge. We first give a detailed presentation on how to construct monotone path polytopes.
Monotone path polytopes of cubes and simplices have been known since the seminal article of Billera and Sturmfels. We extend these results to hypersimplices by linking this problem to the combinatorics of lattice paths. Indeed, we give a combinatorial model which describes the vertices of the monotone path polytope of the hypersimplex $Δ(n, 2)$ (for any generic direction). With this model, we give a precise count of these vertices, and furthermore count the number of coherent monotone paths on $Δ(n, 2)$ according to their lengths.
We prove that some of the results obtained also hold for hypersimplices $Δ(n, k)$ for $k\geq 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14102 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Vertices of the monotone path polytopes of hypersimplicies Poullot, Germain Combinatorics 52B05, 52B11, 52B12 The monotone path polytope of a polytope $P$ encapsulates the combinatorial behavior of the shadow vertex rule (a pivot rule used in linear programming) on $P$. Computing monotone path polytopes is the entry door to the larger subject of fiber polytopes, for which explicitly computing examples remains a challenge. We first give a detailed presentation on how to construct monotone path polytopes. Monotone path polytopes of cubes and simplices have been known since the seminal article of Billera and Sturmfels. We extend these results to hypersimplices by linking this problem to the combinatorics of lattice paths. Indeed, we give a combinatorial model which describes the vertices of the monotone path polytope of the hypersimplex $Δ(n, 2)$ (for any generic direction). With this model, we give a precise count of these vertices, and furthermore count the number of coherent monotone paths on $Δ(n, 2)$ according to their lengths. We prove that some of the results obtained also hold for hypersimplices $Δ(n, k)$ for $k\geq 2$. |
| title | Vertices of the monotone path polytopes of hypersimplicies |
| topic | Combinatorics 52B05, 52B11, 52B12 |
| url | https://arxiv.org/abs/2411.14102 |