Pith. Sign in

REVIEW

Total positivity, Grassmannians, and networks

PaperPDF from arXiv

data files

ReviewThe objections and verdict, as JSON Paper breakdownThe authors' claims, conditions and measurements, as JSON Signed receiptProof this review has not been altered
X Bluesky LinkedIn Reddit Hacker News
Alexander Postnikov

Combinatorics · Submitted 27 Sep 2006 · 43 references

Pith's verdict: The framework is the real contribution and it holds up; the posted draft is unfinished in a few load-bearing places, most notably an empty proof box for Proposition 11.7.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on October 29, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

  1. T0 AI review An AI read the paper and answered a fixed list of questions.
  2. T1 Audit Automatic checks that the references and files the paper relies on exist and match.
  3. T2 Compute The paper's code or calculations re-run with the same results.
  4. T3 Formal statement The claims written out in a formal math language a computer can read.
  5. T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 13 minor · Ask about this paper · The compiled record · Read the full review →
Challenge this review Comment (0) Read on arXiv ↗
Cite ▾
arXiv IDmath/0609764 (version 1)
Pith ID2EGMSAZF, Pith's permanent record of this paper and its review
CitationAlexander Postnikov. "Total positivity, Grassmannians, and networks." arXiv:math/0609764 (2006). https://pith.science/paper/2EGMSAZF
Cite this reviewBibTeX for Pith's review of this paper
Claim paper

Why Pith says this

Highlight any text to comment on it.

Referee report

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Planar networks with positive edge weights, read only at their boundary, sweep out exactly the points of the Grassmannian whose Plücker coordinates are all nonnegative — and the pieces of that sweep are counted by 0/1 fillings of Young-diag

The reading

Take a disk with $n$ labelled boundary points, wire up a directed graph inside it, and give every edge a positive weight. Sum the weights of all directed paths from each boundary source to each boundary sink, with a sign correction for paths that wind around, and you get a table of numbers that can be read as a point of the Grassmannian $Gr_{k,n}$. The paper's central claim is that this construction is exactly onto: every point of the Grassmannian with all Plücker coordinates nonnegative arises this way, and conversely every network lands in that set. It goes further and says the network's combinatorial shape alone determines which piece of that space it fills, that the pieces are indexed by simple 0/1 fillings of Young diagrams called $Â$-diagrams, and that the path sums give subtraction-free (no minus signs anywhere) coordinates on each piece. If this holds, a question about matrices and positivity becomes a question about drawing graphs, and a whole family of combinatorial objects — decorated permutations, plabic graphs, alternating strand diagrams, Grassmann necklaces — turn out to be different names for the same cell. That is what makes the paper worth reading: it proposes a dictionary, not just a theorem.

What carries the argument

Two mechanisms carry the argument. The first is a loop-erased-path generalization of the Lindström–Gessel–Viennot lemma, needed because the networks may contain directed cycles and because sources and sinks may interlace arbitrarily. Instead of an alternating sum over path families, which would have cancelling terms, the paper cancels the negative contributions by an involution that switches the tails of two paths at their first intersection, and rewrites each maximal minor as a sum over non-self-intersecting path families divided by products of the form $1 + Â_{C Â Cyc} x_C$, one factor per vertex of each path. This is what makes every minor a subtraction-free rational expression in the edge weights, hence nonnegative at positive weights, hence the containment $Meas(Net_{k,n}) Â G^{tnn}_{k,n}$. The second is the $Â$-diagram, which converts an arbitrary echelon matrix into a filling of a Young diagram by a recursive procedure: read off the coefficients expressing the first dependent column in terms of the earlier ones, record blocked zeros as all-zero rows, and strip a column at each step. The $Â$-property is precisely the condition that makes this recursion invertible, so the map from tableaux to networks is a bijection onto the cell and the diagram labels the cell.

Extended reading notes

Core claim

The paper claims an exact correspondence between three worlds. First, planar directed networks with $k$ boundary sources and $n-k$ boundary sinks, weighted positively, together with their boundary measurement matrix. Second, the totally nonnegative Grassmannian $Gr^{tnn}_{k,n}$, the set of $k$-dimensional subspaces of $Â^n$ representable by matrices all of whose maximal minors are $Â¥ 0$. Third, the cell decomposition of that space into the nonnegative parts of matroid strata, $S^{tnn}_M = S_M Â G^{tnn}_{k,n}$, which the paper proves are honest open balls and form a CW-complex. The claim is that the boundary measurement map sends networks onto the whole nonnegative Grassmannian (Theorem 4.8), that fixing the graph fixes one cell and one only (Theorem 4.10), and that for each cell there is an explicit graph — built from a $Â$-diagram, a 0/1 filling of a Young diagram obeying the rule that if a box above and a box to the left of a position are both 1 then the position is 1 — for which the map is a subtraction-free rational parametrization (Theorem 6.5). A separate structural claim is that cells correspond bijectively to decorated permutations, permutations of $n$ letters whose fixed points carry a colour, and that containment of cell closures is governed by a circular Bruhat order on these permutations.

Load-bearing premise

The identification of which cell a given bicolored graph fills rests on Proposition 11.7, and in the manuscript that proposition's proof is printed as an empty box, so the graph-to-cell dictionary is asserted there rather than derived.

Editorial extensions

If this is right

  • Every totally nonnegative point of the Grassmannian has an explicit network realization, so questions about positivity of minors can be answered by counting or cancelling paths in a graph.
  • Each cell $S^{tnn}_M$ is an open ball with a subtraction-free parametrization, which gives a concrete positive-coordinate chart on the cell and identifies its dimension with the number of 1's in the corresponding $Â$-diagram.
  • Cells are classified by decorated permutations, so the topology of the cell decomposition is reduced to combinatorics of permutations with coloured fixed points, and the closure order becomes the circular Bruhat order, with the ordinary Bruhat order appearing as an interval.
  • The gluing of a cell to the lower-dimensional cells in its closure is described by sending edge weights to zero, i.e. by deleting edges from the graph — an analogue of passing to subwords of a reduced decomposition.
  • The square move on plabic graphs is a cluster-type transformation, which links the network parametrizations to cluster algebras and to the chamber ansatz for Plücker coordinates.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the dictionary holds, one could hope to read off the entire matroid of a network without computing any minors, just from the source sets of the perfect orientations of the underlying bicolored graph; the paper states this and uses it, which makes it a natural target for an independent check.
  • The subtraction-free form of the path sums suggests a tropical limit: replacing addition by minimum and multiplication by addition should turn the boundary measurements into piecewise-linear data, which is the route the paper indicates toward string polytopes and Littlewood–Richardson coefficients.
  • Because the cell attached to a graph is determined by a permutation, the construction gives a candidate algorithm for deciding whether two networks produce the same point: reduce both to reduced graphs and compare decorated trip permutations, rather than comparing infinitely many path sums.
  • The reliance on a single technical proposition for the graph-to-cell identification means an independent verification of that step would either confirm the whole dictionary at once or expose which of the downstream classification results need repair.
Original abstract

The aim of this paper is to discuss a relationship between total positivity and planar directed networks. We show that the inverse boundary problem for these networks is naturally linked with the study of the totally nonnegative Grassmannian. We investigate its cell decomposition, where the cells are the totally nonnegative parts of the matroid strata. The boundary measurements of networks give parametrizations of the cells. We present several different combinatorial descriptions of the cells, study the partial order on the cells, and describe how they are glued to each other.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,138 input tokens.

What the abstract itself states, as probabilities: claims first 0.03 · states limitation 0.05 · human participants 0.02 · controlled comparison 0.01 · randomized assignment 0.01 · states quantitative result 0.03 · compares with prior results 0.05 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; .

The aim of this paper is to discuss a relationship between total positivity and planar directed networks. We show that the inverse boundary problem for these networks is naturally linked with the study of the totally nonnegative Grassmannian. We investigate its cell decomposition, where the cells are the totally nonnegative parts of the matroid strata. The boundary measurements of networks give parametrizations of the cells. We present several different combinatorial descriptions of the cells, study the partial order on the cells, and describe how they are glued to each other.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#sentencerolethe authors' own workstates the main conclusionstrength
s0 The aim of this paper is to discuss a relationship between total positivity and planar directed networks. contribution 0.50 0.30 0.07 asserted 0.65
s1 We show that the inverse boundary problem for these networks is naturally linked with the study of the totally nonnegative Grassmannian. result 0.80 0.91 0.44 asserted 1.00
s2 We investigate its cell decomposition, where the cells are the totally nonnegative parts of the matroid strata. contribution 0.97 0.89 0.09 asserted 0.99
s3 The boundary measurements of networks give parametrizations of the cells. result 0.80 0.69 0.15 asserted 1.00
s4 We present several different combinatorial descriptions of the cells, study the partial order on the cells, and describe how they are glued to each other. contribution 0.99 0.94 0.16 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 0.98.

What was examined, and what was not

sources read
  • arXiv listing abstract v1
not examined
  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers
levels run
  • P abstract
not run
  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures
Figure 2. 1: A Young diagram λ and the corresponding subset I(λ) For λ ⊆ (n − k) k , the Schubert cell Ωλ in Grkn is defined as the set of k￾dimensional subspaces V ⊂ R n with prescribed dimensions of intersections with the elements of the opposite coordinate flag: Ωλ := {V ∈ Grkn | dim(V ∩ hei , . . . , eni) = |I(λ) ∩ [i, n]|, for i = 1, . . . , n}, where hei , . . . , eni is the linear span of coordinate vectors. The decomposition of Grrk into Schubert cells can be described using Gaussian elimination. We can think of points in Grkn as nondegenerate k×n-matrices modulo row operations. Recall
Figure 4. 1: A path P with the winding index wind(P) = −1 Let us also give a recursive combinatorial definition of the winding index for a path P with vertices v1, v2, . . . , vl (where v1 and vl are boundary vertices). If the path P has no self-intersections, i.e., all vertices vi in P are different, then wind(P) = 0. Suppose that P has at least one self-intersection. Let us find a cycle in P, that is a segment C with vertices vi , i ∈ [a, b], such that the ver￾tices va, va+1, . . . , vb−1 are distinct and va = vb. Let P˜ be the path with vertices v1, . . . , va, vb+1, . . . , vl , i.e., the…
Figure 5. 1: Crossings, alignments, and misalignments
Figure 6. 2: shows an example of Γ -diagram. Here dots in boxes of the Young diagram indicate that they are filled with 1’s, and empty boxes are assumed to be filled with 0’s. Let us draw the hook for each box with a dot, i.e., two lines going to the right and down from the dotted box. The Γ -property means that every box of the Young diagram located at an intersection of two lines should contain a dot
Figure 7. 1: A piece of the Γ-network NT We claim that for this Γ -tableau T , we have A(NT ) = A. Indeed, the network NT′′ is obtained from NT by removing the d − s internal vertices b ′ s+1, . . . , b′ d ad￾jacent to the boundary sources bs+1, . . . , bd, removing the vertical edges incident to the vertices b ′ i , merging d − s pairs of horizontal edges, erasing the weights xs+1, . . . , xd, removing the sink bd+1, and shifting the labels of the boundary ver￾tices bi , i > d + 1, by one; see
Figure 9. 2: Two types of trivalent vertices in a perfect network Definition 9.2. A perfect network N is a planar directed network, in the sense of Definition 4.1, such that (1) Each internal vertex v either has exactly one incident edge directed away from v (and all other edges directed towards v), or has exactly one incident edge directed towards v (all other edges directed away from v). (2) All boundary vertices bi in N have degree 1. The previous discussion implies the following claim. Proposition 9.3. Any planar directed network can be transformed without chang￾ing the boundary…
Figure 10. 2: Two networks that map to the same point in the Grassmannian Corollary 10.3. Let N and N′ be two perfect networks satisfying conditions of Theorem 10.1. Let I ′ be the source set of N′ . Then the minor ∆I ′ (A(N)) is nonzero and, for any k-subset J ⊂ [n], we have ∆J (A(N ′ )) = ∆J (A(N)) ∆I ′ (A(N)) . We now proceed to proving Theorem 10.1 by first checking two special cases: switching edges in a closed directed cycle and switching edges in a path between two boundary vertices. Remark 10.4. Perfect networks N have the following important property. If we pick a directed closed
Figure 11. 2: Perfect orientations of a plabic graph Let us give two additional combinatorial descriptions of the matroid MG in terms of paths and in terms of matchings. Let us fix a perfect orientation O of G and let I = IO. Define the path matroid Mp G as the set of k-element subsets J ⊂ [n] such that the boundary vertices {bi | i ∈ I \ J} can be connected with the boundary vertices {bj | j ∈ J \ I} by a family of pairwise noncrossing directed paths in the graph G with edge orientation O. Let us say that a plabic graph G is bipartite if any edge in G joins two vertices of different colors…
Figure 12. 6: Dipole reduction (graphs) are move-reduction-equivalent if they can be transformed into the same network (graph) by moves (M1)–(M3) and reductions (R1)–(R3). Theorem 12.1. Let N and N′ be two perfectly orientable plabic networks of the same type (k, n). Then the boundary measurement map Meas maps them into the ˜ same point Meas ˜ (N) = Meas ˜ (N′ ) in the Grassmannian Grkn if and only if the networks N and N′ are move-reduction-equivalent. We will prove this theorem in Section 16. In one direction this claim can be verified by direct calculation. Lemma 12.2. Suppose that a plabic…
Figure 13. 1: Rules of the road for trips in plabic graphs Note that these trips in undirected plabic graphs have nothing to do with paths in directed networks that we used in the definition of the boundary measurements. If two trips pass along the same edge in the same directions then they should be identical. If a trip passes along the same edge twice in the same direction then it is a round-trip. Thus each edge of G belongs to exactly two trips or to one trip with a self-intersection at this edge. Each plabic graph G with n boundary vertices defines the trip permutation πG ∈ Sn such that…
Figure 14. 4: The plabic graph G corresponding to the triple di￾agram T (with a perfect orientation of edges) Lemma 14.6. For each permutation π ∈ Sn there is a monotone triple diagram T with strand permutation πT = π. Corollary 14.7. For any decorated permutation π : there is a reduced plabic graph G with trip permutation π : G = π. Remark 14.8. Note that monotone triple diagrams are quite similar to double wiring diagrams of Fomin-Zelevinsky [FZ1]. Such triple diagrams are obtained by su￾perimposing two usual wiring diagrams formed by all rightwards strands and by all leftward strands. These…
Figure 16. 1: A decorated permutation π : For a matroid M ⊆ [n] k  of rank k on the set [n], let IM = (I1, . . . , In) be the sequence of subsets in [n] such that, for i ∈ [n], Ii is the lexicographically minimal base of M with respect to the shifted linear order <i on [n]. Lemma 16.3. For a matroid M, the sequence IM is a Grassmann necklace. Proof. Let I(M) = (I1, . . . , In). By the cyclic symmetry, it is enough to check that I2 = (I1 \ {1}) ∪ {j} for some j, or I2 = I1. The subset I1 = {i1 < · · · < ik} is the lex minimal base of M (with respect to the usual order on [n]). If i1 6= 1 then
Figure 17. 2: A covering relation π : ⋖ σ : in the circular Bruhat order right” (with respect to the linear order <i on [n]). We may assume that I1 6= I ′ 1 . (Otherwise cyclic shift all elements using the cyclic symmetry of the construction.) Suppose that I1 is obtained from I ′ 1 by switching the elements i1, . . . , is ∈ I ′ 1 with j1, . . . , js, where j1 > i1, . . . , js > is. Let a = π −1 (i1) and b = π −1 (j1). Then a ≤ i1 and b ≥ j1 because j1 belongs to the anti-exceedance set of π : and i1 does not belong to this set. Note that for i ∈ [b + 1, a] cyc, the set Ii contains j1 and does…
Figure 18. 1: Transforming a wiring diagram of w = s1s2s3s1 into a plabic graph G Let us now describe the covering relation ⋖ in the circular Bruhat order using Theorem 18.5. Suppose that the cell S tnn M covers S tnn M′ . Let us pick a reduced contracted plabic graph G such that S tnn M = Image(Meas ˜ G) and G has no leaves and vertices of degree 2. By Theorem 18.5, there is an almost-reduced subgraph H ⊂ G such that S tnn M′ = Image(Meas ˜ H). Note that if H is obtained from G by removing two or more edges, then it number of faces drops by at least 2. By Proposition 17.10, the circular…
Figure 19. 2: A Γ -diagram D and the corresponding permutation uD = 1 4 2 7 3 5 9 6 8 Theorem 19.1. The map D 7→ uD is a bijection between Γ -diagrams of shape λ and permutations u ∈ Sn such that u ≤ wλ in the Bruhat order on Sn. The number of 1’s in D equals ℓ(wλ) − ℓ(uD). Lemma 19.2. Marsh-Rietsch [MR, Lemma 3.5] Let w = si1 · · · sil be a reduced decomposition of a Weyl group element w ∈ W. Then, for any u such that u ≤ w in the Bruhat order, there is unique subset J = {j1 < · · · < js} ⊆ [l] such that u = sij1 · · · sijs and (s ′ i1 s ′ i2 · · · s ′ ia ) sia+1 ≥ s ′ i1 s ′
Figure 20. 2: Rules of the road for Γ-graphs Steingrimsson-Williams [SW] investigated nice properties of this bijection D 7→ π : (G plabic D ) with respect to various statistics on permutations and Γ -diagrams. Let us give a simpler description of the bijection between Γ -diagrams and deco￾rated permutations using the bijection D 7→ uD constructed in Section 19. Let wλ = (w1, . . . , wn) = (˜ik,˜ik−1, . . . ,˜i1, ˜jn−k, ˜jn−k−1, . . . , ˜j1) be the Grass￾mannian permutation associated with λ ⊆ (n − k) k , where I(λ) = {i1 < · · · < ik}, [n] \ I(λ) = {j1 < · · · < jn−k}, and ˜i := n + 1 − i. L
Figure 23. 1: The numbers Nkn of nonnegative cells in Grtnn kn Let Nn = Pn k=0 Nkn be the total number of decorated permutations of size n. Proposition 23.2. The numbers Nn satisfy the recurrence relation Nn = n·Nn−1+ 1, N0 = 1. The exponential generating function for these numbers is P n≥0 Nn x n n! = e x/(1 − x). The sequence Nn appears in [Sloane] with ID number A000522. Let Nkn(q) = Pq dim S tnn M be the generating function for the nonnegative cells S tnn M ⊂ Grtnn kn counted according to their dimension. By Theorem 6.5, we have Nkn(q) = X D q |D| , where the sum is over Γ -di

Showing 17 of the paper's 23 figures. See all figures in the PDF ↗ Figures reproduced from arXiv:math/0609764 by the authors.

References
How later papers used it

241 later papers cite it

Evidence: substantial. 236 of the citing papers share no author with it, and 40 of those carry a confident label from Pith's citation classifier.

Pith read 39 of the 946 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

Builds on it 2 of 11 papers with this label
Uses its method or tool 10 of 27 papers with this label
How the literature uses it

246 arXiv papers cite this in 992 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 535 sentences without a confident label

Contests it 3 papers
  • [ref] [There is a typo in the entries of the matrix $B$ in [ref] .] For an $n ×n$ real matrix $A = (a_i,j)$, consider the $n ×2n$ matrix $B = ψ(A)$, where [equation] For each pair $(I,J)$ with $I,J ⊆[n]$ and $|I| = |J|$, define the set [equation] Then we have $Δ_I,J(A) = Δ_[n],K(B)$.

    Dyck Paths and Positroids from Unit Interval Orders · Background and Notation · contest 0.81

  • In Section [ref], we expose a major difficulty of lifting the theory of plabic networks to the cylinder: Postinikov's results (Section 10 of [ref] ) regarding changing the orientation of edges of a plabic network do not hold.

    Plabic R-matrices · Introduction · contest 0.83

  • [ref] [There is a typo in the entries of the matrix $B$ in [ref] .] If $A ∈Mat_d,m()$ and $B = ϕ_d,m(A)$, then [equation] for all $I ⊆[d]$ and $J ⊆[m]$ satisfying $|I| = |J|$.

    Positroids Induced by Rational Dyck Paths · The Positroid Induced by a Rational Dyck Path · contest 0.88

Builds on it 14 papers
Uses its method or tool 28 papers
Compares with it 17 papers
Cites it as support 5 papers
  • This follows from the fact that positroid cells are in bijection with Postnikov diagrams $ [ref] $ up to geometric exchange, which are in bijection with reduced tilings up to tiling equivalence.

    Parametrizing positroid cells using bicolored tilings · Parametrising positroid cells · 0.98

  • Theorem [ref](2) ( [ref] ) immediately implies flip-connectivity.

    Positive Grassmannian and polyhedral subdivisions · Grassmannian graphs as duals of polyhedral subdivisions induced by projections of hypersimplices · 0.97

  • By [ref] , since the cell decompositions of $_k,n^≥0$ given by Postnikov and Rietsch coincide, and the Richardson cell $_w_0w,w_0t^>0$ of the complete flag variety $_n^≥0$ projects to the positroid cell of $_k,n^≥0$ indexed by $[w_0w,w_0t]$, then $P$ is the $k$-th constituent of the flag positroid associated to any point in $_w_0w,w_0t^>0$.

    Flag positroid pipe dreams · Flag positroids and flag positroid pipe dreams · 0.97

Cites it as background 188 papers

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.