Flow polytopes for extensions of bipartite graphs
Benjamin Braun, Kaitlin Bruegge, Robert Davis, Derek Hanely · 2025
Read Flow polytopes for extensions of bipartite graphs by Benjamin Braun, Kaitlin Bruegge, Robert Davis, Derek Hanely (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-26445.txt.
Description
Benjamin Braun, Kaitlin Bruegge, Robert Davis, and Derek Hanely connected flow polytopes to matchings in 2025. A flow polytope collects all unit flows on a directed graph with no cycles; it is a lattice polytope with rich counting theory. The authors start from a two-sided graph whose vertices each touch at least two edges.
From such a graph they build two directed graphs: an extension and a whiskered variant. The normalized volume of the extension's flow polytope equals the number of matchings in the whiskered graph. A finer result matches the polytope's Ehrhart polynomial, which counts lattice points at each scale, to the unsigned matching polynomial. Counting points and counting pairings turn out to be the same problem.
Catalog record
| CREATOR | Benjamin Braun, Kaitlin Bruegge, Robert Davis, Derek Hanely |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-26445