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

CREATORBenjamin Braun, Kaitlin Bruegge, Robert Davis, Derek Hanely
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-26445

Browse the full library · About the Tower of Babel