A flow polytope of a finite directed acyclic graph 
and net-flow vector 
is the convex
polytope of nonnegative network flows having
excess outflow 
at each graph vertex 
:
 |
Nonemptiness requires 
.
Acyclicity ensures boundedness when the set is nonempty. For a directed
graph with a directed graph cycle, the corresponding
nonnegative flow set can instead be unbounded. For the directed
graph with graph edges 
, 
, and 
and net flow 
, the flow polytope is the line segment given by 
and 
for 
.
For 
,
the zigzag directed graph on 1, 2, ..., 
has graph edges 
and 
whenever their endpoints lie in that range. Its unit-flow
polytope, with net flow 
,
is integrally equivalent to the order polytope
of the alternating partially ordered set
on 
elements with relations 
(Brunner and Hanusa 2026).
Brunner and Hanusa (2026, Theorem 5) study the integrally equivalent unit-flow polytope of a contracted zigzag directed graph.
They show that the dual graph of its length-reverse-length
triangulation embeds as a subgraph
of an integer grid graph. Its dual has one graph
vertex for each maximal simplex, with two vertices
adjacent when the simplices share a codimension-one face. They also characterize adjacency using integer flows
and conjecture that two proposed statistics recover its 
-polynomial, the numerator
in its Ehrhart polynomial generating function.
For an integral flow polytope of dimension 
with Ehrhart polynomial 
, this numerator satisfies
 |
