pith. sign in

arxiv: 2507.12684 · v2 · submitted 2025-07-16 · 🧮 math.CO

Framing Triangulations and Framing Posets of Planar DAGs with Nontrivial Netflow Vectors

Jonah Berggren This is my paper

Pith reviewed 2026-05-19 03:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords flow polytopesplanar DAGsunimodular triangulationframingsposet structurenetflow vectorscombinatorial indexinglattice generalization
0
0 comments X

The pith

Framings of planar DAGs with multiple sources and sinks induce unimodular triangulations of their flow polytopes and poset structures on the maximal simplices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends the known construction of framing-induced regular unimodular triangulations from flow polytopes of single-source single-sink DAGs to the more general setting of planar DAGs that may have several sources, several sinks, and arbitrary netflow vectors. It shows that framings continue to index the simplices of a unimodular triangulation and that the dual graph of this triangulation carries a poset structure that generalizes the lattice property found in the one-source-one-sink case. A sympathetic reader cares because explicit triangulations and posets supply combinatorial control over the geometry of these polytopes, which appear in network-flow problems and polyhedral combinatorics.

Core claim

The space of unit flows on a directed acyclic graph (DAG) with one source and one sink is known to admit regular unimodular triangulations induced by framings of the DAG. The dual graph of any of these triangulations may be given the structure of the Hasse diagram of a lattice, generalizing many variations of the Tamari lattice and the weak order. We extend this theory to flow polytopes of DAGs which may have multiple sources, multiple sinks, and nontrivial netflow vectors under certain planarity conditions. We construct a unimodular triangulation of such a flow polytope indexed by combinatorial data and give a poset structure on its maximal simplices generalizing the strongly planar one-sou

What carries the argument

Framings of the planar DAG, which supply the combinatorial data that both index the simplices of the unimodular triangulation of the flow polytope and define the covering relations of the poset on those maximal simplices.

If this is right

  • The flow polytope admits a regular unimodular triangulation whenever the DAG satisfies the planarity conditions.
  • The maximal simplices of the triangulation are indexed directly by the combinatorial data of the framings.
  • The dual graph of the triangulation carries a poset structure that reduces to the known lattice when the DAG has a single source and single sink.
  • The construction applies to flow polytopes with arbitrary netflow vectors at the sources and sinks.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The explicit indexing by framings may supply a route to volume formulas or Ehrhart polynomials for these flow polytopes that were previously unavailable.
  • Similar framing constructions could be tested on other classes of polytopes that arise from directed graphs with conservation laws.
  • The generalized poset may be compared with existing lattice structures on triangulations of other polytopes to reveal shared recursive or enumerative properties.

Load-bearing premise

The stated planarity conditions on the DAG are enough to guarantee that framings still produce a unimodular triangulation whose dual graph admits a poset structure generalizing the single-source single-sink case.

What would settle it

A concrete planar DAG with at least two sources or two sinks for which some framing produces a collection of simplices that either fails to cover the flow polytope, overlaps in positive volume, or yields a dual graph whose covering relations do not form the desired poset.

Figures

Figures reproduced from arXiv: 2507.12684 by Jonah Berggren.

Figure 1
Figure 1. Figure 1: A strongly planar balanced DAG with its unit flow polytope and maximal layering-cliques. moves may be given directions so that if K and L are adjacent maximal layering-cliques, then L is either an up-rotation, up-shuffle, up-realignment, down-rotation, down-shuffle, or down-realignment of K. In the latter three cases we write L ≺ K. Theorem B. The transitive closure of these relations is a poset structure … view at source ↗
Figure 2
Figure 2. Figure 2: A framed DAG, its two maximal cliques, and its framing￾triangulated flow polytope. Definition 2.7. If K is a clique of (G, F), then a (K-)clique combination of G is a linear combination X p∈K apI(p), where each ap ≥ 0. It is positive if each ap > 0, and unit if P p∈K ap = 1. The set of unit flows arising as (necessarily unit) K-clique combinations is the clique simplex ∆1(K). Theorem 2.8 ([10, Theorem 1]).… view at source ↗
Figure 3
Figure 3. Figure 3: Three examples of pairs (Γ, a) which fail to be strongly planar. Netflows are labelled in blue; vertices with no blue label have netflow 0. 3. Strongly Planar and Balanced DAGs We start this section by defining strongly planar DAGs with netflows (Γ, a). These give the class of flow polytopes which we will triangulate in this paper. We will then use some reduction steps to show that it suffices to triangula… view at source ↗
Figure 4
Figure 4. Figure 4: Reducing to the strongly planar balanced case. Vertices are drawn as black letters (or symbols); on the top, netflow is labelled in blue. 3.4. Reducing to the strongly planar balanced case. The goal of this paper is to give unimodular triangulations for the flow polytopes of strongly planar pairs (Γ, a). We now show that it will suffice to give unimodular triangulations for flow polytopes of strongly plana… view at source ↗
Figure 5
Figure 5. Figure 5: A different way to reduce to the strongly planar balanced case. Define the netflow vector a ′ on Γ′ by (a ′ )i =    1 i is a source −1 i is a sink 0 else. It is immediate by construction that every decontracted edge of Γ′ can be contracted, and that these contractions do not affect the flow polytope Fa′(Γ′ ) up to unimodular equivalence. Moreover, contracting all decontracted edges retrieves the DAG Γ… view at source ↗
Figure 6
Figure 6. Figure 6: The two-point extension of a strongly planar balanced DAG. of pairwise compatibility on layerings which induces the desired triangulation. Our proofs will use the two-point extension Γ obtained from Γ by adding a community source and a ˆ community sink vertex to Γ. The two-point extension will allow us to apply the triangulation results of Danilov, Karzanov, and Koshevoy [10] in the unit one-source-one-sin… view at source ↗
Figure 7
Figure 7. Figure 7: On the left is a route p of Γ and on the right is the corresponding route ˆp of Γ. ˆ Lemma 4.4. The map F 7→ Fˆ is a bijection from nonnegative flows on Γ to nonnegative layered flows on Γˆ. If F has strength S, then Fˆ has strength (m × S). Proof. It is immediate that if F is a nonnegative flow on Γ then Fˆ is a nonnegative flow on Γ, and that the map ˆ F 7→ Fˆ is injective. Moreover, given any layered fl… view at source ↗
Figure 8
Figure 8. Figure 8: A strongly planar balanced DAG with a layering in magenta (right) and the corresponding unit flow in blue (left). is trivial, so we assume that Fˆ is not the zero vector. Let S ∈ Z>0 such that Fˆ(α) = S for any source or sink edge α, so that Fˆ is a strength-(mS) flow of Γ. ˆ By Theorem 2.8, the flow Fˆ gives rise to a unique clique Kˆ of P Γ and a decomposition ˆ Fˆ = pˆ∈Kˆ apˆI(ˆp), where each coefficien… view at source ↗
Figure 9
Figure 9. Figure 9: The relation ≺ is not transitive on layerings. We now argue injectivity of J . Suppose that p and q are two layerings such that J (p) = J (q). Since p is a layering, the routes {p1, . . . , pm} of Γ are compatible, hence the routes {pˆ1, . . . , pˆm} of Γ are compatible; then ˆ Pm i=1 I(ˆpi) is a clique combination for J (p). Similarly, Pm i=1 I(ˆqi) is a clique combination for J (q) = J (p). Then the uniq… view at source ↗
Figure 10
Figure 10. Figure 10: From the top maximal layering-clique is shown a down-shuffle, down-rotation, and down-realignment. K at a layering p ∈ K, we say that L is a down-mutation of K at p. We similarly refer to up-mutations of K. 6. The Framing Poset We now define the framing poset, which is a partial order on maximal layering-cliques of a strongly planar balanced DAG Γ (and hence, simplices of its framing triangulation). 6.1. … view at source ↗
Figure 11
Figure 11. Figure 11: A DAG whose framing poset is not a lattice. 6.3. Relations to one-source-one-sink framing triangulations. Recall the definition of a planar-framed DAG in Section 3.2. In particular, if a strongly planar balanced DAG Γ has one source and one sink, then the embedding of Γ induces a planar framing FP of Γ. In this case, a layering is merely a route and our compatibility of layerings amounts to compatibility … view at source ↗
Figure 12
Figure 12. Figure 12: A DAG of a non-unit flow polytope, its reduction to a unit flow polytope, and the framing poset [PITH_FULL_IMAGE:figures/full_fig_p030_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The framing poset of the unit flow polytope of a non-connected strongly planar balanced DAG. Example 6.9. Consider the strongly planar balanced DAG Γ of [PITH_FULL_IMAGE:figures/full_fig_p030_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: A non-planar balanced DAG whose unit flow polytope admits no lattice triangulation. 7. Obstacles to Extending Beyond the Strongly Planar Case One may wonder if some of our results may be extended past the strongly planar case. The following example is a reasonably small balanced DAG whose unit flow polytope admits no lattice triangulation. Example 7.1. Let Γ be the complete bipartite graph K3,3, shown in … view at source ↗
read the original abstract

The space of unit flows on a directed acyclic graph (DAG) with one source and one sink is known to admit regular unimodular triangulations induced by framings of the DAG. The dual graph of any of these triangulations may be given the structure of the Hasse diagram of a lattice, generalizing many variations of the Tamari lattice and the weak order. We extend this theory to flow polytopes of DAGs which may have multiple sources, multiple sinks, and nontrivial netflow vectors under certain planarity conditions. We construct a unimodular triangulation of such a flow polytope indexed by combinatorial data and give a poset structure on its maximal simplices generalizing the strongly planar one-source-one-sink case.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript extends the theory of framing-induced regular unimodular triangulations of flow polytopes from DAGs with one source and one sink to planar DAGs with multiple sources, multiple sinks, and nontrivial netflow vectors under certain planarity conditions. It constructs a unimodular triangulation indexed by combinatorial data (framings) and equips the dual graph of the triangulation with a poset structure on its maximal simplices that generalizes the strongly planar one-source-one-sink case.

Significance. If the central claims hold, the work supplies a combinatorial generalization of lattice structures such as the Tamari lattice to a wider family of flow polytopes, with potential implications for volumes, Ehrhart theory, and algebraic combinatorics. The explicit indexing by framings and the poset construction on maximal simplices are concrete strengths that could support independent verification or further applications.

major comments (2)
  1. [Abstract and §3] Abstract, final paragraph and §3: the claim that the stated planarity conditions on the DAG suffice to guarantee a unimodular triangulation for nontrivial netflow vectors a = (a1,…,ak,−b1,…) is load-bearing. With multiple sources/sinks the flow-conservation equations at internal vertices differ from the single-source case, so the argument that framings still produce simplices of normalized volume 1 (and that their union covers the polytope without gaps or overlaps) must be checked explicitly against the altered linear dependencies; the abstract supplies no proof sketch for this step.
  2. [§4] §4, construction of the triangulation: the indexing rule by framings is presented as purely combinatorial, yet the simplices are defined inside a polytope whose facet inequalities depend on the integer values in the netflow vector. It is not shown that the determinant of each maximal simplex remains ±1 with respect to the ambient lattice independently of those values; a concrete example with a non-unit netflow vector would clarify whether the unimodularity is preserved or requires additional restrictions.
minor comments (2)
  1. [Notation and §2] The notation for netflow vectors and the precise definition of 'strongly planar' could be introduced with a small running example before the general statements.
  2. [Figures] A figure showing a planar DAG with two sources, two sinks, and an explicit nontrivial netflow vector would help readers visualize the extension from the one-source case.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and positive evaluation of the significance of our work. We address the major comments point by point below, and we will incorporate clarifications and an example in the revised manuscript.

read point-by-point responses

  1. Referee: Abstract, final paragraph and §3: the claim that the stated planarity conditions on the DAG suffice to guarantee a unimodular triangulation for nontrivial netflow vectors is load-bearing. With multiple sources/sinks the flow-conservation equations at internal vertices differ from the single-source case, so the argument that framings still produce simplices of normalized volume 1 must be checked explicitly against the altered linear dependencies; the abstract supplies no proof sketch for this step.

    Authors: We agree that the abstract does not contain a proof sketch and that the extension to nontrivial netflows requires careful verification of the linear dependencies. In Section 3, we establish that the planarity conditions ensure the framing-induced simplices have normalized volume 1 by generalizing the incidence matrix arguments from the single-source case, accounting for the modified flow conservation at internal vertices. To strengthen the presentation, we will revise the abstract to briefly note this key generalization and add an explicit remark or lemma in §3 that directly addresses the difference in equations and confirms the covering without gaps or overlaps. revision: yes

  2. Referee: §4, construction of the triangulation: the indexing rule by framings is presented as purely combinatorial, yet the simplices are defined inside a polytope whose facet inequalities depend on the integer values in the netflow vector. It is not shown that the determinant of each maximal simplex remains ±1 with respect to the ambient lattice independently of those values; a concrete example with a non-unit netflow vector would clarify whether the unimodularity is preserved or requires additional restrictions.

    Authors: The construction in §4 defines the simplices combinatorially via framings, and the proof demonstrates that their vertices form a unimodular basis in the lattice of flows, with the determinant being ±1 due to the planarity condition which prevents netflow-dependent dependencies from arising in the relevant submatrices. Nevertheless, we acknowledge that an explicit example would enhance clarity. In the revised version, we will add a concrete example of a planar DAG with a nontrivial netflow vector (e.g., netflow (2, -2)) and compute the corresponding simplex to verify the determinant explicitly. revision: yes

Circularity Check

0 steps flagged

No circularity: construction is a self-contained combinatorial generalization

full rationale

The paper extends framing triangulations from one-source-one-sink DAGs to planar multi-source/multi-sink cases with nontrivial netflows by defining framings combinatorially and asserting they induce unimodular triangulations whose duals carry a poset structure. No equations, definitions, or steps reduce the claimed triangulation or poset to fitted parameters, self-referential inputs, or unverified self-citations; the planarity conditions and combinatorial indexing are presented as independent extensions of prior flow-polytope results. The derivation remains self-contained against external combinatorial benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that planarity is enough to carry the framing construction forward; no free parameters or new postulated entities are mentioned in the abstract.

axioms (1)
  • domain assumption Planarity of the DAG is sufficient for framings to induce a unimodular triangulation whose dual carries a lattice structure.
    Invoked in the final sentence of the abstract to justify the extension.

pith-pipeline@v0.9.0 · 5646 in / 1316 out tokens · 46102 ms · 2026-05-19T03:43:00.895930+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Kostant partitions functions and flow polytopes.Transform

    Welleda Baldoni and Mich` ele Vergne. Kostant partitions functions and flow polytopes.Transform. Groups, 13(3-4):447–469, 2008

    work page 2008

  2. [2]

    Triangulations of flow polytopes, ample framings, and gentle algebras.Selecta Math

    Matias von Bell, Benjamin Braun, Kaitlin Bruegge, Derek Hanely, Zachery Peterson, Khrystyna Ser- hiyenko, and Martha Yip. Triangulations of flow polytopes, ample framings, and gentle algebras.Selecta Math. (N.S.), 30(3):Paper No. 55, 34, 2024

    work page 2024

  3. [3]

    Framing lattices and flow polytopes.S´ em

    Matias von Bell and Cesar Ceballos. Framing lattices and flow polytopes.S´ em. Lothar. Combin., 91B:Art. 98, 12, 2024

    work page 2024

  4. [4]

    Gonz´ alez D’Le´ on, Francisco A

    Matias von Bell, Rafael S. Gonz´ alez D’Le´ on, Francisco A. Mayorga Cetina, and Martha Yip. A uni- fying framework for theν-Tamari lattice and principal order ideals in Young’s lattice.Combinatorica, 43(3):479–504, 2023

    work page 2023

  5. [5]

    M. K. Bennett and G. Birkhoff. Two families of Newman lattices.Algebra Universalis, 32(1):115–144, 1994

    work page 1994

  6. [6]

    Flows on gentle algebras.arXiv preprint, 2025

    Jonah Berggren. Flows on gentle algebras.arXiv preprint, 2025

    work page 2025

  7. [7]

    Wilting theory of flow polytopes.S´ em

    Jonah Berggren and Khrystyna Serhiyenko. Wilting theory of flow polytopes.S´ em. Lothar. Combin., 91B:Art. 21, 12, 2024

    work page 2024

  8. [8]

    Volume inequalities for flow polytopes of full directed acyclic graphs.arXiv preprint, 2024

    Benjamin Braun and James Ford McElroy. Volume inequalities for flow polytopes of full directed acyclic graphs.arXiv preprint, 2024

    work page 2024

  9. [9]

    On linear intervals in the altν-Tamari lattices.Comb

    Cesar Ceballos and Cl´ ement Chenevi` ere. On linear intervals in the altν-Tamari lattices.Comb. Theory, 4(2):Paper No. 18, 31, 2024. 32

    work page 2024

  10. [10]

    Danilov, Alexander V

    Vladimir I. Danilov, Alexander V. Karzanov, and Gleb A. Koshevoy. Coherent fans in the space of flows in framed graphs. In24th International Conference on Formal Power Series and Algebraic Combina- torics (FPSAC 2012), volume AR ofDiscrete Math. Theor. Comput. Sci. Proc., pages 481–490. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012

    work page 2012

  11. [11]

    Toric matrix Schubert varieties and their polytopes.Proc

    Laura Escobar and Karola M´ esz´ aros. Toric matrix Schubert varieties and their polytopes.Proc. Amer. Math. Soc., 144(12):5081–5096, 2016

    work page 2016

  12. [12]

    Gonz´ alez D’Le´ on, Alejandro H

    Rafael S. Gonz´ alez D’Le´ on, Alejandro H. Morales, Eva Philippe, Daniel Tamayo Jim´ enez, and Martha Yip. Realizing thes-permutahedron via flow polytopes.S´ em. Lothar. Combin., 91B:Art. 60, 12, 2024

    work page 2024

  13. [13]

    Morales, and Karola M´ esz´ aros

    Ricky Ini Liu, Alejandro H. Morales, and Karola M´ esz´ aros. Flow polytopes and the space of diagonal harmonics.Canad. J. Math., 71(6):1495–1521, 2019

    work page 2019

  14. [14]

    Lattice structure of grid-Tamari orders.J

    Thomas McConville. Lattice structure of grid-Tamari orders.J. Combin. Theory Ser. A, 148:27–56, 2017

    work page 2017

  15. [15]

    Karola M´ esz´ aros and Alejandro H. Morales. Volumes and Ehrhart polynomials of flow polytopes.Math. Z., 293(3-4):1369–1401, 2019

    work page 2019

  16. [16]

    Morales, and Jessica Striker

    Karola M´ esz´ aros, Alejandro H. Morales, and Jessica Striker. On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope.Discrete Comput. Geom., 62(1):128–163, 2019

    work page 2019

  17. [17]

    Karola M´ esz´ aros and Avery St. Dizier. From generalized permutahedra to Grothendieck polynomials via flow polytopes.Algebr. Comb., 3(5):1197–1229, 2020

    work page 2020

  18. [18]

    Cambrian lattices.Adv

    Nathan Reading. Cambrian lattices.Adv. Math., 205(2):313–353, 2006. Department of Mathematics, University of Kentucky, Lexington, KY, United States Email address:jrberggren@uky.edu 33

    work page 2006