Braun & McElroy (2025) — volume inequalities for flow polytopes of full directed acyclic graphs.
Combinatorial information in \(\FGa\)
Faces
Faces of flow polytopes
Theorem (Hille (2003))
The faces of \(\FGa\) are of the form \(\mathcal{F}_H(\ba)\) where \(H\) is an \(\ba\)-effective subgraph of \(G\).
Corollary
The vertices of \(\FGa\) correspond to \(\ba\)-effective spanning trees of \(G\).
Corollary — Unit netflow
When \(\ba = \e_0 - \e_n\), the vertices of \(\FG\) are routes.
The oruga graph \(\mathrm{oru}(3)\), \(\ba = \e_0 - \e_3\):
Face poset
Faces of \(\mathcal{F}_{\mathrm{oru}(3)}(\e_0-\e_3)\) ordered by inclusion: each face is labelled by its \(\ba\)-effective subgraph (gray edges are absent).
(Normalized) volumes
Volumes of flow polytopes
For certain graphs \(G\) and vectors \(\ba\), the volumes of \(\FGa\) have nice combinatorial formulas.
Theorem (Zeilberger 1999, Conjectured by Chan-Robbins-Yuen and Postnikov-Stanley)
When \(G\) is the complete graph \(K_{n+1}\) and \(\ba=(1,0,\ldots,-1)\), the (normalized) volume of \(\FGa\) (called the Chan–Robbins–Yuen “CRY” polytope) is given by
where \(C_k := \frac{1}{k+1}\binom{2k}{k}\) is the \(k\)-th Catalan number.
Remark
The original description of the CRY polytope is as the face of the Birkhoff polytope (the convex hull of all permutation matrices) whose vertices are the permutation matrices such that \(\pi_{i,j}=0\) for \(j \geq i+2\).
Postnikov and Stanley showed that this polytope is integrally equivalent to \(\mathcal{F}_G(\e_1 - \e_n)\) where \(G = K_{n+1}\) is the complete graph on \(n+1\) vertices.
Other flow polytopes with nice volume formulas
Combinatorial quantities as volumes
Hover any graph to see the volume formula for that family.
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
Enumerating Integer flows to obtain a volume
There are 16 integer flows on \(G\) with netflow \(\mathbf{a}=(0,0,2,1,-3)\) — their count equals \(\vol \FG\).
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.
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
(Abram, Chapelier-Laget, Reutenauer (2020))
Non-twisted framing
Twisted framing
\(\nu\)-Tamari lattice, principal order ideals \(I(\nu)\) in Young's lattice
For any framed digraph \((G, F)\), the framing order \(\mathrm{DKK}(G, F)\) is a lattice.
Other notable examples of framing lattices include:
• Boolean lattice
• \(c\)-Cambrian
[Reading]
• alt \(\nu\)-Tamari
[Ceballos, Chenevière]
• cross Tamari
[Bell, Ceballos]
• Grassmann Tamari
[Santos, Stump, Welker]
• grid Tamari
[McConville]
• \((\varepsilon, I, J)\)-Cambrian
[Pilaud]
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
Supporting families of permutation flows: a zoo of combinatorial objects!
Combinatorics of permutation flows
\[\begin{array}{ c c c c c c c }
\mathrm{Cliques} & \!\!\longrightarrow\!\! & \mathrm{Vines}& \!\!\longrightarrow\!\!
& \mathrm{Groves} & \!\!\longrightarrow\!\!
& \mathrm{Permutation\, Flows}\\
&&&&&&\\
\mathcal{C} & \mapsto & \mathcal{V} & \mapsto & \Gamma & \mapsto & \pi
\end{array}\]
A zoo of combinatorial objects
CliqueVineGroveLabeled grovePermutation flow
click to advance · ⌘/ctrl+click to go back · drag to pan · scroll to zoom
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
Permutation flow shuffles
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
