The volume of a unit flow polytope equals the number of integer flows on the same graph with a different netflow determined by indegrees.
Volume of
is equal to
Integer flows of
Triangulations
Framed digraphs
Definition — Framing
A framing at vertex \(v\) is a choice of linear orders on \(\inu(v)\) and \(\out(v)\).
A framing \(F\) of \(G\) is the collection of framings at every interior vertex. A framed graph is a pair \((G, F)\).
The framing is visualized by the vertical ordering of edges at each vertex:
Non-twisted framing \(F\)
Twisted framing \(F'\)
Coherence of routes
Definition — Coherence
Two routes \(P\) and \(Q\) have a conflict at vertex \(v\) if the prefixes \(Pv, Qv\) have the opposite relative ordering from the suffixes \(vP, vQ\) in the framing at \(v\).
They are coherent if they do not have a conflict at any vertex.
Cliques & the DKK triangulation
Definition — Clique
A clique \(\mathcal{C}\) is a set of routes that are pairwise coherent.
Key insight
\(\mathrm{Cliques}(G,F)\) is a simplicial complex.
The same polytope \(\FG \cong [0,1]^3\) admits different triangulations depending on the framing \(F\).
Understanding the DKK triangulation
\(m = 10\), \(n = 4\), \(d = 6\)
Questions.
(a) Can you compute a maximal clique?
(b) Are these two faces part of a common facet?
The dual structure of the triangulation
What changes in adjacent simplices in the DKK triangulation?
Clique \(\mathcal{C}_1\)
7 pairwise coherent routes
Clique \(\mathcal{C}_2\)
Differs in exactly one route → shared facet
Minimal conflicts & the framing order
Theorem 2.9 (Danilov–Karzanov–Koshevoy (2012))
Two simplices \(\triangle_{\mathcal{C}}, \triangle_{\mathcal{C}'} \in \DKK(G,F)\) share a facet iff their cliques differ in exactly two routes \(P \in \mathcal{C}\), \(Q \in \mathcal{C}'\) with a minimal conflict.
Proposition 2.11
The graph \(\{(\mathcal{C}, \mathcal{C}') \mid \mathcal{C} \lessdot \mathcal{C}'\}\) on \(\SatCliques(G,F)\) is acyclic. Its transitive closure defines a partial order in \(DKK(G, F)\).
\(P\) is descending and
\(Q\) is ascending at \(v\)
The framing order \(P(G, F)\) is the partial order on \(\SatCliques(G, F)\) given by the transitive closure of the cover relation \(\mathcal{C} \lessdot \mathcal{C}'\).
Non-twisted framing on \(\mathrm{oru}(n)\):
\(\mathrm{DKK} \cong\) weak order on \(\mathfrak{S}_n\)
Twisted framing on \(\mathrm{oru}(n)\):
\(\mathrm{DKK} \cong\) lattice of circular permutations
The \(s\)-permutahedron realized via flow polytopes — \(s\)-weak order defined by (Ceballos-Pons) is a lattice
But cliques are hard to work with — how do we work with these lattices?
A new combinatorial model: permutation flows
On \((G, F)\), edges are classified as:
Slack edges \(s_0, s_1, \ldots\)
Split edges \(t_1, t_2, \ldots, t_d\)
Add an inflow half-edge \(x\) at the source. \(\hat{E} = E \cup \{x\}\).
We will assign recursively a word \(\pi(e)\)to each edge and at each vertex \(v\), we will define summary words by concatenating the words \(\pi(e)\) of all the incoming (resp. outgoing) edges gives:
A (saturated) permutation flow on \((G, F)\) is a map \(\pi\colon \hat{E} \to \mathcal{P}_{[0,d]}\) such that:
\(\pi(x) = 0\)
At each vertex \(v\): the outgoing word \(\pi(e'_0)\cdots\pi(e'_j)\) is a shuffle of the incoming word \(\pi(e_0)\cdots\pi(e_i)\) and the word of split edges \(e'_1 e'_2 \cdots e'_j\)
At each split edge \(e'_h\): \(e'_h\) is the first letter of \(\pi(e'_h)\)
The map \(\;\mathrm{SatPermuFlows}(G, F) \;\xrightarrow{\;\sim\;}\; \mathrm{SatCliques}(G, F)\), given by
\(\pi \;\mapsto\; \mathrm{Routes}(\pi)\)
is a bijection.
Key Insight
The idea is to follow the “splits”.
Recovering routes from π
\(\pi\)
\(v_4\!:\; \mathbf{3\;1\;6\;4\;0\;2\;5}\)
\(\mathrm{Routes}(\pi)\)
Saturated permutation flows lift the Lidskii volume formula
The normalized volume of \(\mathcal{F}_G\) is
\(\;\mathrm{vol}\;\mathcal{F}_G = \mathcal{F}_G^{\mathbb{Z}}(\vec{d})\),
the number of lattice points of the flow polytope \(\mathcal{F}_G(\vec{d})\).
Proposition (González D'León, Hanusa, Yip (2025))
For any framed graph \((G, F)\),
\(\mathrm{SatPermuFlows}(G, F) \;\xrightarrow{\;\sim\;}\; \mathcal{F}_G^{\mathbb{Z}}(\vec{d})\),
\(\pi \;\mapsto\; \bigl(\pi(e) - 1\bigr)_{e \in E}\)
is a bijection.
\(\pi\) — Permutation flow
⟶
\(\pi(e) - 1\)
Integer flow — lattice point of \(\mathcal{F}_G(\vec{d})\)
\(\vec{d} = (0,\, 1,\, 2,\, 1,\, {-4})\)
The weak order
A poset structure on \(\mathrm{SatPermuFlows}(G, F)\)
Definition — Ascent
An ascent in \(\pi\) is a pair \((e, t)\) where
\(e\) appears just before \(t\) in some \(\pi(e')\), and \(v\) is the rightmost vertex where this occurs for \(e\).
Definition — Descent
A descent in \(\pi\) is a pair \((t, e)\) where
on all edges to the right of \(v\) which contain \(t\), the substring “\(te\)” appears together.
Key Insight
Ascents are rightmost splits.
\(\pi\)
Ascents: \((5,2)\), \((6,1)\).
Descent: \((6,4)\). Note: \((4,2)\) is not an ascent since \(2\) splits further right.
Raising and lowering operators — \(R_t\) and \(L_t\)
\(\pi = 3\;1\;6\;4\;0\;2\;5\)
\(R_5(\pi) = 3\;1\;6\;4\;0\;5\;2\)
\(R_6(\pi) = 3\;6\;1\;4\;0\;2\;5\)
\(L_6(\pi) = 3\;1\;4\;6\;0\;2\;5\)
The oruga example
Step-by-step construction of the framing order — planar vs. twisted framing
Planar framing
Twisted framing
The weak order \(\mathcal{W}(G, F)\) on permutation flows
Theorem (González D'León, Hanusa, Yip (2025))
\(R_t\) are covering relations, whose transitive closure
defines a poset structure on \(\mathrm{SatPermuFlows}(G, F)\).
Definition
We call this poset the (right) weak order
\(\mathcal{W}_{(G,F)}\) on \(\mathrm{SatPermuFlows}(G, F)\).
Theorem (González D'León, Hanusa, Yip (2025))
\(\mathcal{W}_{(G,F)} \;\cong\; \text{Framing lattice on } \mathrm{DKK}(G, F).\)
The \(h^*\)-polynomial of \(\mathcal{F}_G\) is \(A_{(G,F)}(t)\).
Idea of the Proof. We show that any linear extension \(\mathcal{C}_1, \ldots, \mathcal{C}_s\) of the saturated cliques in \(W(G,F)\) gives a shelling.
\(\displaystyle h^*_{\mathcal{F}_G}(t)=h_{\mathrm{DKK}(G,F)}(t) = \sum_{i=1}^{s} t^{\,|\mathcal{R}(\mathcal{C}_i)|}
= \sum_{i=1}^{s} t^{\,\text{# elements covered by } \mathcal{C}_i}
= \sum_{i=1}^{s} t^{\,\mathrm{des}(\pi_i)}.\)
Corollary
\(h^*\) is independent of the framing, so
\(A_{(G,F)}(t) = A_{(G,F')}(t)\).
Definition
The \(G\)-Eulerian polynomial \(A_{G}(t)\) is defined as \(A_{(G,F)}(t)\) for any framing \(F\) of \(G\).
Faces of \(\mathrm{DKK}(G,F)\) in terms of permutation flows
Faces of DKK(G,F): non-saturated permutation flows
A general triangulation of \(\mathcal{F}_G(\mathbf{a})\) when \(\mathbf{a}\) has \(a_n < 0\) as the only negative entry: Permutation flow triangulations!
Framed augmented digraphs
The Pitman-Stanley polytope
Cliques of route matchings
Permutation flow shuffles
A permutation flow triangulation of the Pitman-Stanley polytope
The permutation flow triangulation
Theorem (González D'León, Hanusa, Yip (2025))
Let \((\hat{G},\hat{F})\) be a framed \(\mathbf{a}\)-augmented graph of \(G\). The set
Let \(\mathbf{a}\) be such that \(a_i \ge 0\) for \(i = 0, \dots, n-1\) and \(a_n < 0\). The normalized volume of the flow polytope \(\mathcal{F}_G(\mathbf{a})\) is
