On the $f$-vectors of flow polytopes for the complete graph
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_ | 1866929512293335040 |
|---|---|
| author | Dugan, William T. |
| author_facet | Dugan, William T. |
| contents | The Chan-Robbins-Yuen polytope ($CRY_n$) of order $n$ is a face of the Birkhoff polytope of doubly stochastic matrices that is also a flow polytope of the directed complete graph $K_{n+1}$ with netflow $(1,0,0, \ldots , 0, -1)$. The volume and lattice points of this polytope have been actively studied, however its face structure has received less attention. We give generating functions and explicit formulas for computing the $f$-vector by using Hille's (2003) result bijecting faces of a flow polytope to certain graphs, as well as Andresen-Kjeldsen's (1976) result that enumerates certain subgraphs of the directed complete graph. We extend our results to flow polytopes of the complete graph having arbitrary (non-negative) netflow vectors and recover the $f$-vector of the Tesler polytope of Mészáros--Morales--Rhoades (2017). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15519 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the $f$-vectors of flow polytopes for the complete graph Dugan, William T. Combinatorics 05C21, 52B05, 05A15 (Primary) 05A19, 06A07, 52B20 (Secondary) The Chan-Robbins-Yuen polytope ($CRY_n$) of order $n$ is a face of the Birkhoff polytope of doubly stochastic matrices that is also a flow polytope of the directed complete graph $K_{n+1}$ with netflow $(1,0,0, \ldots , 0, -1)$. The volume and lattice points of this polytope have been actively studied, however its face structure has received less attention. We give generating functions and explicit formulas for computing the $f$-vector by using Hille's (2003) result bijecting faces of a flow polytope to certain graphs, as well as Andresen-Kjeldsen's (1976) result that enumerates certain subgraphs of the directed complete graph. We extend our results to flow polytopes of the complete graph having arbitrary (non-negative) netflow vectors and recover the $f$-vector of the Tesler polytope of Mészáros--Morales--Rhoades (2017). |
| title | On the $f$-vectors of flow polytopes for the complete graph |
| topic | Combinatorics 05C21, 52B05, 05A15 (Primary) 05A19, 06A07, 52B20 (Secondary) |
| url | https://arxiv.org/abs/2409.15519 |