Back to Search Start Over

Volume inequalities for flow polytopes of full directed acyclic graphs

Authors :
Braun, Benjamin
McElroy, James Ford
Publication Year :
2024

Abstract

Given a finite directed acyclic graph, the space of non-negative unit flows is a lattice polytope called the flow polytope of the graph. We consider the volumes of flow polytopes for directed acyclic graphs on $n+1$ vertices with a fixed degree sequence, with a focus on graphs having in- and out-degree two on every internal vertex. When the out-degree of the source is three and the number of vertices is fixed, we prove that there is an interchange operation on the edge set of these graphs that induces a partial order on the graphs isomorphic to a Boolean algebra. Further, we prove that as we move up through this partial order, the volumes of the corresponding flow polytopes weakly decrease. Finally, we show that each such graph is strongly planar and we provide an alternative interpretation of our results in the context of linear extensions for posets that are bipartite non-crossing trees.<br />Comment: revised final section for clarity

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2405.02433
Document Type :
Working Paper