The positive Dressian equals the positive tropical Grassmannian

Abstract

The Dressian and the tropical Grassmannian parameterize abstract and realizable tropical linear spaces; but in general, the Dressian is much larger than the tropical Grassmannian. There are natural positive notions of both of these spaces – the positive Dressian, and the positive tropical Grassmannian (which we introduced roughly fifteen years ago in [J. Algebraic Combin. 22 (2005), pp. 189–210]) – so it is natural to ask how these two positive spaces compare. In this paper we show that the positive Dressian equals the positive tropical Grassmannian. Using the connection between the positive Dressian and regular positroidal subdivisions of the hypersimplex, we use our result to give a new “tropical” proof of da Silva’s 1987 conjecture (first proved in 2017 by Ardila-Rincón-Williams) that all positively oriented matroids are realizable. We also show that the finest regular positroidal subdivisions of the hypersimplex consist of series-parallel matroid polytopes, and achieve equality in Speyer’s $f$-vector theorem. Finally we give an example of a positroidal subdivision of the hypersimplex which is not regular, and make a connection to the theory of tropical hyperplane arrangements.

1. Introduction

The tropical Grassmannian, first studied in HKT06KT06SS04, is the space of realizable tropical linear spaces, obtained by applying the valuation map to Puisseux-series valued elements of the usual Grassmannian. Meanwhile the Dressian is the space of tropical Plücker vectors $P = \{P_I\}_{I \in {[n] \choose k}}$, first studied by Andreas Dress, who called them valuated matroids. Thinking of each tropical Plücker vector $P$ as a height function on the vertices of the hypersimplex $\Delta _{k,n}$, one can show that the Dressian parameterizes regular matroid subdivisions $\mathcal{D}_P$ of the hypersimplex Kap93Spe08, which in turn are dual to the abstract tropical linear spaces of the first author Spe08.

There are positive notions of both of the above spaces. The positive tropical Grassmannian, introduced by the authors in SW05, is the space of realizable positive tropical linear spaces, obtained by applying the valuation map to Puisseux-series valued elements of the totally positive Grassmannian PosLus94. The positive Dressian is the space of positive tropical Plücker vectors, and it was recently shown to parameterize the regular positroidal subdivisions of the hypersimplex LPW20AHLS20.⁠¹

¹

Although this result did not appear in the literature until recently, it was anticipated by various people including the first author, Nick Early Ear19a, Felipe Rincón, Jorge Olarte.

✖

In general, the Dressian $\operatorname {Dr}_{k,n}$ is much larger than the tropical Grassmannian $\operatorname {Trop}Gr_{k,n}$ – for example, the dimension of the Dressian $\operatorname {Dr}_{3,n}$ grows quadratically is $n$, while the dimension of the tropical Grassmannian $\operatorname {Trop}Gr_{3,n}$ is linear in $n$ HJJS08. However, the situation for their positive parts is different. The first main result of this paper is the following, see Theorem 3.9.

Theorem.

The positive tropical Grassmannian $\operatorname {Trop}^+Gr_{k,n}$ equals the positive Dressian $\operatorname {Dr}^+_{k,n}$.⁠²

²

Our result was announced in LPW20, Theorem 9.6, and subsequently appeared in the independent work AHLS20.

✖

We give several interesting applications of Theorem 3.9. The first application is a new proof of the following 1987 conjecture of da Silva, which was proved in 2017 by Ardila, Rincón and the second author ARW17, using the combinatorics of positroid polytopes.

Theorem (ARW17).

Every positively oriented matroid is realizable.

Reformulating this statement in the language of Postnikov’s 2006 preprint Pos, da Silva’s conjecture says that every positively oriented matroid is a positroid. We give a new proof of this statement, using Theorem 3.9, which we think of as a “tropical version” of da Silva’s conjecture. Interestingly, although the definitions of positively oriented matroid and positroid don’t involve tropical geometry at all, there does not seem to be an easy way to remove the tropical geometry from our proof without making it significantly longer.

There are two natural fan structures on the Dressian: the Plücker fan, and the secondary fan, which were shown in OPS19 to coincide. Our second application of Theorem 3.9 is a description of the maximal cones in the positive Dressian, or equivalently, the finest regular positroidal subdivisions of the hypersimplex. The following result appears as Theorem 6.6.

Theorem.

Let $P$ be a positive tropical Plücker vector, and consider the corresponding regular positroidal subdivision $\mathcal{D}_P$. The following statements are equivalent:

(1)

$\mathcal{D}_P$ is a finest subdivision.

(2)

Every facet of $\mathcal{D}_P$ is the matroid polytope of a series-parallel matroid.

(3)

Every octahedron in $\mathcal{D}_P$ is subdivided.

It was shown by the first author in Spe09 that if $P$ is a tropical Plücker vector corresponding to a realizable tropical linear space, $\mathcal{D}_P$ has at most $\frac{(n-c-1)!}{(k-c)!(n-k-c)!(c-1)!}$ interior faces of dimension $n-c$, with equality if and only if all facets of $\mathcal{D}_P$ correspond to series-parallel matroids. We refer to this result as the $f$-vector theorem. Combining this result with Theorem 6.6 gives the following elegant result (see Corollary 6.7):

Corollary.

Every finest positroidal subdivision of $\Delta _{k,n}$ achieves equality in the $f$-vector theorem. In particular, such a positroidal subdivision has precisely ${n-2 \choose k-1}$ facets (top-dimensional polytopes).

Most of our paper concerns the regular positroidal subdivisions of $\Delta _{k,n}$, which are precisely those induced by positive tropical Plücker vectors. However, it is also natural to consider the set of all positroidal subdivisions of $\Delta _{k,n}$, whether or not they are regular. In light of the various nice realizability results for positroids, one might hope that all positroidal subdivisions of $\Delta _{k,n}$ are regular. However, this is not the case. In Section 7, we construct a nonregular positroidal subdivision of $\Delta _{3,12}$, based off a standard example of a nonregular mixed subdivision of $9 \Delta _2$. We also make a connection to the theory of tropical hyperplane arrangements and tropical oriented matroids AD09Hor16.

It is interesting to note that the positive tropical Grassmannian and the positive Dressian have recently appeared in the study of scattering amplitudes in $\mathcal{N}=4$ SYM DFGK19AHHLT19HP19Ear19bLPW20AHLS20, and in certain scalar theories CEGM19BC19. In particular, the second author together with Lukowski and Parisi LPW20 gave striking evidence that the positive tropical Grassmannian $\operatorname {Trop}^+Gr_{k+1,n}$ controls the regular positroidal subdivisions of the amplituhedron $\mathcal{A}_{n,k,2} \subset Gr_{k,k+2}$, which was introduced by Arkani-Hamed and Trnka AHT14 to study scattering amplitudes in $\mathcal{N}=4$ SYM.

The structure of this paper is as follows. In Section 2 we review the notion of the positive Grassmannian and its cell decomposition, as well as matroid and positroid polytopes. In Section 3, after introducing the notions of the (positive) tropical Grassmannian and (positive) Dressian, we show that the positive tropical Grassmannian equals the positive Dressian. We review the connection between the positive tropical Grassmannian and positroidal subdivisions in Section 4, then give a new proof in Section 5 that every positively oriented matroid is realizable. We give several characterizations of finest positroidal subdivisions of the hypersimplex in Section 6, and show that such subdivisions achieve equality in the $f$-vector theorem. Then in Section 7, we construct a nonregular positroidal subdivision of $\Delta _{3,12}$, and make a connection to the theory of tropical hyperplane arrangements and tropical oriented matroids AD09Hor16. We end our paper with an appendix (Section 8), which reviews some of Postnikov’s technology Pos for studying positroids.

2. The positive Grassmannian and positroid polytopes

Definition 2.1.

The (real) Grassmannian $Gr_{k,n}$ (for $0\le k \le n$) is the space of all $k$-dimensional subspaces of $\mathbb{R}^n$. An element of $Gr_{k,n}$ can be viewed as a $k\times n$ matrix of rank $k$ modulo invertible row operations, whose rows give a basis for the $k$-dimensional subspace.

Let $[n]$ denote $\{1,\dots ,n\}$, and $\binom{[n]}{k}$ denote the set of all $k$-element subsets of $[n]$. Given $V\in Gr_{k,n}$ represented by a $k\times n$ matrix $A$, for $I\in \binom{[n]}{k}$ we let $p_I(V)$ be the $k\times k$ minor of $A$ using the columns $I$. The $p_I(V)$ do not depend on our choice of matrix $A$ (up to simultaneous rescaling by a nonzero constant), and are called the Plücker coordinates of $V$.

2.1. The positive Grassmannian and its cells

Definition 2.2 (Pos, Section 3).

We say that $V\in Gr_{k,n}$ is totally nonnegative (respectively, totally positive) if $p_I(V)\ge 0$ (resp. $p_I(V) > 0$) for all $I\in \binom{[n]}{k}$. The set of all totally nonnegative $V\in Gr_{k,n}$ is the totally nonnegative Grassmannian $Gr_{k,n}^{\geq 0}$ and the set of all totally positive $V$ is the totally positive Grassmannian $Gr_{k,n}^{>0}$. For $M\subseteq \binom{[n]}{k}$, let $S_{M}$ be the set of $V\in Gr_{k,n}^{\geq 0}$ with the prescribed collection of Plücker coordinates strictly positive (i.e. $p_I(V)>0$ for all $I\in M$), and the remaining Plücker coordinates equal to zero (i.e. $p_J(V)=0$ for all $J\in \binom{[n]}{k}\setminus M$). If $S_M\neq \emptyset$, we call $M$ a positroid and $S_M$ its positroid cell.

Each positroid cell $S_{M}$ is indeed a topological cell Pos, Theorem 6.5, and moreover, the positroid cells of $Gr_{k,n}^{\ge 0}$ glue together to form a CW complex PSW09.

As shown in Pos, the cells of $Gr_{k,n}^{\geq 0}$ are in bijection with various combinatorial objects, including decorated permutations $\pi$ on $[n]$ with $k$ anti-excedances, $\vcenter{\img[][6pt][7pt][{\scalebox{-1}[1]{\text{L}}}]{Images/imgd1f0ece8d595253204b01ba52077910b.svg}}$-diagrams $D$ of type $(k,n)$, and equivalence classes of reduced plabic graphs $G$ of type $(k,n)$. In Section 8 we review these objects and give bijections between them. This gives a canonical way to label each positroid by a decorated permutation, a $\vcenter{\img[][6pt][7pt][{\scalebox{-1}[1]{\text{L}}}]{Images/imgd1f0ece8d595253204b01ba52077910b.svg}}$-diagram, and an equivalence class of plabic graphs; we will correspondingly refer to positroid cells as $S_{\pi }$, $S_D$, etc.

2.2. Matroid and positroid polytopes

In what follows, we set $e_I \coloneq \sum _{i \in I} e_i \in \mathbb{R}^n$, where $\{e_1, \dotsc , e_n\}$ is the standard basis of $\mathbb{R}^n$.

Definition 2.3.

Given a matroid $M=([n],\mathcal{B})$, the (basis) matroid polytope $\Gamma _M$ of $M$ is the convex hull of the indicator vectors of the bases of $M$:

$$\begin{equation*} \Gamma _M \coloneq \operatorname {convex}\{e_B \mid B \in \mathcal{B}\} \subset \mathbb{R}^n. \end{equation*}$$

The dimension of a matroid polytope is determined by the number of connected components of the matroid. Recall that a matroid which cannot be written as the direct sum of two nonempty matroids is called connected.

Proposition 2.4 (Oxl11).

Let $M$ be a matroid on $E$. For two elements $a, b \in E$, we set $a \sim b$ whenever there are bases $B_1, B_2$ of $M$ such that $B_2 = (B_1 - \{a\}) \cup \{b\}$. The relation $\sim$ is an equivalence relation, and the equivalence classes are precisely the connected components of $M$.

Proposition 2.5 (BGW03).

For any matroid, the dimension of its matroid polytope is $\dim \Gamma _M = n-c$, where $c$ is the number of connected components of $M$.

Recall that any full rank $k\times n$ matrix $A$ gives rise to a matroid $M(A)=([n],\mathcal{B})$, where $\mathcal{B} = \{I \in \binom{[n]}{k} \ \vert \ p_I(A) \neq 0\}$. Positroids are the matroids $M(A)$ associated to $k\times n$ matrices $A$ with maximal minors all nonnegative. We call the matroid polytope $\Gamma _M$ associated to a positroid a positroid polytope.

3. The positive tropical Grassmannian equals the positive Dressian

In this section we review the notions of the tropical Grassmannian, the Dressian, the positive tropical Grassmannian, and the positive Dressian. The main theorem of this section is Theorem 3.9, which says that the positive tropical Grassmannian equals the positive Dressian.

Definition 3.1.

Given $e=(e_1,\dots ,e_N) \in \mathbb{Z}^N_{\geq 0}$, we let $\mathbf{x}^e$ denote $x_1^{e_1} \dots x_N^{e_N}$. Let $E \subset \mathbb{Z}^N_{\geq 0}$. For $f = \sum _{e\in E} f_e \mathbf{x}^e$ a nonzero polynomial, we denote by $\operatorname {Trop}(f) \subset \mathbb{R}^N$ the set of all points $(X_1,\dots , X_N)$ such that, if we form the collection of numbers $\sum _{i=1}^N e_i X_i$ for $e$ ranging over $E$, then the minimum of this collection is not unique. We say that $\operatorname {Trop}(f)$ is the tropical hypersurface associated to $f$.

In our examples, we always consider polynomials $f$ with real coefficients. We also have a positive version of Definition 3.1.

Definition 3.2.

Let $E=E^+ \sqcup E^- \subset \mathbb{Z}^N_{\geq 0}$, and let $f$ be a nonzero polynomial with real coefficients which we write as $f = \sum _{e\in E^+} f_e \mathbf{x}^e - \sum _{e\in E^-} f_e \mathbf{x}^e$, where all of the coefficients $f_e$ are nonnegative real numbers. We denote by $\operatorname {Trop}^+(f) \subset \mathbb{R}^N$ the set of all points $(X_1,\dots , X_N)$ such that, if we form the collection of numbers $\sum _{i=1}^N e_i X_i$ for $e$ ranging over $E$, then the minimum of this collection is not unique and furthermore is achieved for some $e\in E^+$ and some $e\in E^-$. We say that $\operatorname {Trop}^+(f)$ is the positive part of $\operatorname {Trop}(f)$.

The Grassmannian $Gr_{k,n}$ is a projective variety which can be embedded in projective space $\mathbb{P}^{\binom{[n]}{k}-1}$, and is cut out by the Plücker ideal, that is, the ideal of relations satisfied by the Plücker coordinates of a generic $k \times n$ matrix. These relations include the three-term Plücker relations, defined below.

Definition 3.3.

Let $1<a<b<c<d\leq n$ and choose a subset $S \in \binom{[n]}{k-2}$ which is disjoint from $\{a,b,c,d\}$. Then $p_{Sac} p_{Sbd} = p_{Sab} p_{Scd}+p_{Sad} p_{Sbc}$ is a three-term Plücker relation for the Grassmannian $Gr_{k,n}$. Here $Sac$ denotes $S \cup \{a,c\}$, etc.

Definition 3.4.

Given $S, a, b, c, d$ as in Definition 3.3, we say that the tropical three-term Plücker relation holds if

•

$P_{Sac}+P_{Sbd} = P_{Sab}+P_{Scd} \leq P_{Sad}+P_{Sbc}$ or

•

$P_{Sac}+P_{Sbd} = P_{Sad}+P_{Sbc} \leq P_{Sab}+P_{Scd}$ or

•

$P_{Sab}+P_{Scd} = P_{Sad}+P_{Sbc} \leq P_{Sac}+P_{Sbd}$.

And we say that the positive tropical three-term Plücker relation holds if either of the first two conditions above holds.

Definition 3.5.

The tropical Grassmannian $\operatorname {Trop}Gr_{k,n} \subset \mathbb{R}^{\binom{[n]}{k}}$ is the intersection of the tropical hypersurfaces $\operatorname {Trop}(f)$, where $f$ ranges over all elements of the Plücker ideal. The Dressian $\operatorname {Dr}_{k,n} \subset \mathbb{R}^{\binom{[n]}{k}}$ is the intersection of the tropical hypersurfaces $\operatorname {Trop}(f)$, where $f$ ranges over all three-term Plücker relations.

The tropical Grassmannian $\operatorname {Trop}Gr_{k,n}$, first studied in SS04HKT06KT06, parameterizes tropicalizations of ordinary linear spaces, defined over the field of generalized Puisseux series $\mathbb{K}$ in one variable $t$, with real exponents. More formally, recall that there is a valuation $\operatorname {val}_{\mathbb{K}}: \mathbb{K} \setminus \{0\} \to \mathbb{R}$, given by $\operatorname {val}_{\mathbb{K}}(c(t)) = \alpha _0$ if $c(t) = \sum c_{\alpha _m} t^{\alpha _m}$, where the lowest order term is assumed to have non-zero coefficient $c_{\alpha _0} \neq 0$. Then $P$ lies in the tropical Grassmannian $\operatorname {Trop}Gr_{k,n}$ if and only if there is an element $A = A(t) \in Gr_{k,n}(\mathbb{K})$ whose Plücker coordinates have valuations given by $P=\{P_I\}$ (see Pay09Pay12 for a proof). We will call elements of $\operatorname {Trop}Gr_{k,n}$ realizable tropical linear spaces. The tropical Grassmannian is a proper subset of the Dressian,⁠³ which parameterizes what one might call abstract tropical linear spaces. Moreover, the Dressian has a natural fan structure, whose cones correspond to the regular matroidal subdivisions of the hypersimplex Kap93, Spe08, Proposition 2.2, see Theorem 4.2. Note that the Dressian $Dr_{k,n}$ is the subset of $\mathbb{R}^{[n]\choose k}$ where the tropical three-term Plücker relations hold.

³

Also called the tropical pre-Grassmannian in SS04 and named in HJJS08 for Andreas Dress’ work on valuated matroids.

✖

Definition 3.6.

The positive tropical Grassmannian $\operatorname {Trop}^+Gr_{k,n} \subset \mathbb{R}^{\binom{[n]}{k}}$ is the intersection of the positive tropical hypersurfaces $\operatorname {Trop}^+(f)$, where $f$ ranges over all elements of the Plücker ideal. The positive Dressian $\operatorname {Dr}^+_{k,n} \subset \mathbb{R}^{\binom{[n]}{k}}$ is the intersection of the positive tropical hypersurfaces $\operatorname {Trop}^+(f)$, where $f$ ranges over all three-term Plücker relations.

The positive tropical Grassmannian was introduced by the authors fifteen years ago in SW05, and was shown to parameterize tropicalizations of ordinary linear spaces that lie in the totally positive Grassmannian (defined over the field of Puiseux series). The positive tropical Grassmannian lies inside the positive Dressian, which controls the regular positroidal subdivisions of the hypersimplex LPW20, see Theorem 4.3. Note that the positive Dressian $Dr^+_{k,n}$ is the subset of $\mathbb{R}^{[n]\choose k}$ where the positive tropical three-term Plücker relations hold.

Definition 3.7.

We say that a point $\{P_I\}_{I\in \binom{[n]}{k}}\in \mathbb{R}^{\binom{[n]}{k}}$ is a (finite) tropical Plücker vector if it lies in the Dressian $\operatorname {Dr}_{k,n}$, i.e. for every three-term Plücker relation, it lies in the associated tropical hypersurface. And we say that $\{P_I\}_{I\in \binom{[n]}{k}}$ is a positive tropical Plücker vector, if it lies in the positive Dressian $\operatorname {Dr}^+_{k,n}$, i.e. for every three-term Plücker relation, it lies in the positive part of the associated tropical hypersurface.

Example 3.8.

For $Gr_{2,4}$, there is only one Plücker relation, $p_{13} p_{24} = p_{12} p_{34}+p_{14} p_{23}$. We have that $\operatorname {Trop}Gr_{2,4} = \operatorname {Dr}_{2,4} \subset \mathbb{R}^{\binom{[4]}{2}}$ is the set of points $(P_{12}$, $P_{13}$, $P_{14}$, $P_{23}$, $P_{24}$, $P_{34})\in \mathbb{R}^6$ such that

•

$P_{13}+P_{24} = P_{12}+P_{34} \leq P_{14}+P_{23}$ or

•

$P_{13}+P_{24} = P_{14}+P_{23} \leq P_{12}+P_{34}$ or

•

$P_{12}+P_{34} = P_{14}+P_{23} \leq P_{13}+P_{24}$.

And $\operatorname {Dr}^+_{2,4} = \operatorname {Trop}^+Gr_{2,4} \subset \mathbb{R}^{\binom{[4]}{2}}$ is the set of points $(P_{12}, P_{13}, P_{14}, P_{23}, P_{24}, P_{34})\in \mathbb{R}^6$ such that

•

$P_{13}+P_{24} = P_{12}+P_{34} \leq P_{14}+P_{23}$ or

•

$P_{13}+P_{24} = P_{14}+P_{23} \leq P_{12}+P_{34}$$\lozenge$

In general, the Dressian $\operatorname {Dr}_{k,n}$ is much larger than the tropical Grassmannian $\operatorname {Trop}Gr_{k,n}$ – for example, the dimension of the Dressian $\operatorname {Dr}_{3,n}$ grows quadratically is $n$, while the dimension of the tropical Grassmannian $\operatorname {Trop}Gr_{3,n}$ is linear in $n$ HJJS08. However, the situation for their positive parts is different. The main result of this section is the following.

Theorem 3.9.

The positive tropical Grassmannian $\operatorname {Trop}^+Gr_{k,n}$ equals the positive Dressian $\operatorname {Dr}^+_{k,n}$.

Theorem 3.9 was recently announced in LPW20. It subsequently appeared in independent work of AHLS20.

Before proving Theorem 3.9, we review some results from SW05 which allow one to compute positive tropical varieties.

Remark 3.10.

In Section 8 we describe many parametrizations of cells of $(Gr_{k,n})_{\geq 0}$, which were given by Postnikov using plabic graphs. SW05, Proposition 2.5 says that if one has a subtraction-free rational map $f$ which surjects onto the positive part $V^+(J)$ of a variety (for example a cluster chart), then the tropicalization of this map surjects onto the positive tropical part $\operatorname {Trop}^+V(J)$ of the variety. Therefore we can tropicalize each parameterization $\Phi _G$ from Theorem 8.8 – to obtain a parameterization of a positive tropical positroid variety (in particular, $\operatorname {Trop}^+Gr_{k,n}$). More specifically, we tropicalize $\Phi _G$ by replacing the positive parameters $x_{\mu }$ (with $\prod _\mu x_{\mu } = 1$) with real parameters $X_{\mu }$ (with $\sum _{\mu } X_{\mu } = 0$) – and replacing products with sums and sums with minimums in the expressions for flow polynomials. Then SW05, Proposition 2.5 say that this tropicalized map $\operatorname {Trop}\Phi _G$ gives a parameterization of $\operatorname {Trop}^+ Gr_{k,n}$.

For the proof of Theorem 3.9 it is convenient to use one particular plabic graph (corresponding to the directed graph $\operatorname {Web}_{k,n}$ from SW05, Section 3), see Figure 1.

Applying Theorem 8.8 to the graph from Figure 1, we have the following result.

Theorem 3.11.

Label the faces of $G_0\coloneq Web_{k,n}$ by indices $\mu$ and let $\mathcal{P}_{k,n}$ denote the collection of indices. Define the weight $\operatorname {wt}(w)$ of a path $w$ in $Web_{k,n}$ to be the product of parameters $x_{\mu }$ where $\mu$ ranges over all face labels to the left of a path. Define the weight of a flow (i.e. a collection of nonintersecting paths) to be the product of the weights of its paths. Let $p_J^{G_0} = \sum _F \operatorname {wt}(F)$ where $F$ ranges over all flows from $\{1,2,\dots ,k\}$ to $J$. Then the map $\Phi \coloneq \Phi _{G_0}$ sending $(x_{\mu })_{\mu \in \mathcal{P}_{k,n}} \in (\mathbb{R}_{>0})^{k(n-k)}$ to the collection of flow polynomials $\{p_J^{G_0}\}_{J\in {[n]\choose k}}$ is a homeomorphism from $(\mathbb{R}_{>0})^{k(n-k)}$ to the totally positive Grassmannian $(Gr_{k,n})_{>0}$ (realized in its Plücker embedding).

In the case of the graph $G_0 = \operatorname {Web}_{k,n}$, we obtain the following parameterization of $\operatorname {Trop}^+ Gr_{k,n}$.

Theorem 3.12.

Label the faces of $Web_{k,n}$ by indices $\mu$ as before. Define the weight $\operatorname {Wt}(w)$ of a path $w$ in $Web_{k,n}$ to be the sum of parameters $X_{\mu }$ where $\mu$ ranges over all face labels to the left of a path. Define the weight of a flow (i.e. a collection of nonintersecting paths) to be sum of the weights of its paths. Let $P_J^{G_0} = \min _F \operatorname {Wt}(F)$ where $F$ ranges over all flows from $\{1,2,\dots ,k\}$ to $J$. Then the map $\operatorname {Trop}\Phi _G= \operatorname {Trop}\Phi _{G_0}$ sending $(X_{\mu })_{\mu \in \mathcal{P}_{k,n}} \in (\mathbb{R})^{k(n-k)}$ to the collection of tropical flow polynomials $\{P_J^{G_0}\}_{J\in {[n]\choose k}}$ is a bijection from $\mathbb{R}^{k(n-k)}$ to the tropical positive Grassmannian $\operatorname {Trop}^+ Gr_{k,n}$ (realized in its Plücker embedding).

In the case of $G_0 = \operatorname {Web}_{k,n}$, we can easily invert the maps $\Phi \coloneq \Phi _{G_0}$ and $\operatorname {Trop}\Phi = \operatorname {Trop}\Phi _{G_0}$. This was done in SW05; we review the construction here. First, given $i$ and $j$ labeling horizontal and vertical wires of $\operatorname {Web}_{k,n}$ (i.e. $1 \leq i \leq k$ and $k+1 \leq j \leq n$), let

$$\begin{equation*} K(i,j)\coloneq \{1,2,\dots ,i-1\} \cup \{i+j-k,i+j-k+1,\dots ,j-1,j\}. \end{equation*}$$

If $(i,j)$ does not correspond to a region of $\operatorname {Web}_{k,n}$, set $K(i,j)\coloneq [k]$.

Definition 3.13.

Let $p = \{p_K\}_{K\in {[n]\choose k}}\in \mathbb{R}_{>0}^{[n]\choose k}$. Then for $i$ and $j$ labeling horizontal and vertical wires of $\operatorname {Web}_{k,n}$ (i.e. $1 \leq i \leq k$ and $k+1 \leq j \leq n$), we define

$$\begin{equation*} \Psi (p)_{(i,j)}\coloneq \frac{p_{K(i,j)} p_{K(i+1,j-2)} p_{K(i+2,j-1)}}{p_{K(i,j-1)} p_{K(i+1,j)}p_{K(i+2,j-2)}}. \end{equation*}$$

We likewise define the tropical version. Let $P = \{P_K\}_{K\in {[n]\choose k}}\in \mathbb{R}^{[n]\choose k}$.

$$\begin{multline} \operatorname {Trop}\Psi (P)_{(i,j)} = \left( P_{K(i,j)} + P_{K(i+1,j-2)} + P_{K(i+2,j-1)} \right)\\ - \left( P_{K(i,j-1)} + P_{K(i+1,j)} + P_{K(i+2,j-2)} \right). \end{multline}$$

Definition 3.13 gives a way to label each face of $\operatorname {Web}_{k,n}$ by a (tropical) Laurent monomial in (tropical) Plücker coordinates. This is shown in Figure 2.

Proposition 3.14.

The maps $\Phi : \mathbb{R}_{>0}^{k(n-k)} \to Gr^+_{k,n}$ and $\Psi : Gr^+_{k,n} \to \mathbb{R}_{>0}^{k(n-k)}$ are inverses.

Proposition 3.15 (SW05, Corollary 3.5 and its proof).

The maps $\operatorname {Trop}\Phi : \mathbb{R}^{k(n-k)} \to \operatorname {Trop}^+ Gr_{k,n}$ and $\operatorname {Trop}\Psi : \operatorname {Trop}^+ Gr_{k,n}\to \mathbb{R}^{k(n-k)}$ are inverses.

Lemma 3.16.

The collection of Plücker coordinates $\mathcal{C} = \{p_{K(i,j)} \ \vert \ 1 \leq i \leq k, k+1 \leq j \leq n\}$ form a cluster for the cluster algebra structure Sco06 on (the affine cone over the) Grassmannian $Gr_{k,n}$. We call this the corectangles cluster. In particular, this collection of Plücker coordinates is algebraically independent, and all other Plücker coordinates can be written as Laurent polynomials with positive coefficients in the Plücker coordinates from the collection.

Proof.

Note that for each $i$ and $j$ as above, $K(i,j)$ is a $k$-element subset of $[n]$. Moreover, if we identify Young diagrams contained in a $k \times (n-k)$ rectangle with the labels of the vertical steps in the length-$n$ lattice path taking unit steps south and west from $(k,n-k)$ to $(0,0)$, then the elements $K(i,j)$ precisely correspond to the Young diagrams $\lambda$ whose complementary Young diagram is a rectangle. It is not hard to see that the collection $\{K(i,j)\}$ is a maximal weakly separated set collection OPS15, and hence form a cluster for the cluster algebra structure Sco06.

■

Example 3.17.

Figure 2 depicts the map $\operatorname {Trop}\Psi$. Since $\operatorname {Trop}\Phi$ and $\operatorname {Trop}\Psi$ are inverses, this example shows how to express each of the variables $X_{ij}$ (as shown in Figure 1) in terms of the tropical Plücker coordinates $\mathcal{C} = \{P_{K(i,j)} \ \vert \ 1 \leq i \leq k, k+1 \leq j \leq n\}$. Note moreover that if we choose a normalization in tropical projective space (e.g. where $P_{123}=0$), then we can solve for the tropical Plücker coordinates in $\mathcal{C}$ in terms of the $X_{ij}$’s. For example, comparing Figure 1 and Figure 2, we see that if $P_{123}=0$, then $P_{124}-P_{123} = P_{124} = X_{34}$, $P_{134}-P_{124} = X_{24}$, so $P_{134} = X_{34}+X_{24}$, etc. In this example we see that from the collection $\{X_{ij}\}$ together with the normalization $P_{123}=0$, we can uniquely determine the Plücker coordinates $\{124, 125, 134, 145\} \cup \{123, 234, 345, 456, 156, 126\}$. As in Lemma 3.16, this collection of Plücker coordinates is a cluster for the cluster algebras structure on the Grassmannian.$\lozenge$

It is easy to generalize Example 3.17, obtaining the following result.

Lemma 3.18.

The map $\operatorname {Trop}\Psi$ sending $\mathcal{C} = \{P_{K(i,j)} \ \vert \ 1 \leq i \leq k, k+1 \leq j \leq n\}$ (with the convention that $P_{12\dots k} = 0$) to $\{\operatorname {Trop}\Psi (P)_{(i,j)}\}$ is an injective map from $\mathbb{R}^{k(n-k)}$ to $\mathbb{R}^{k(n-k)}$.

Proof of Theorem 3.9.

To prove Theorem 3.9, we must show that every point in the positive Dressian also lies in the positive tropical Grassmannian. We will consider any tropical Plücker vector $P=\{P_K\}_{K\in {[n]\choose k}} \in \operatorname {Dr}^+_{k,n}$, with the normalization $P_{12\dots k} = 0$, and compute $Q\coloneq (\operatorname {Trop}\Phi ) \circ (\operatorname {Trop}\Psi )(P)$. This will give an (a priori new) realizable tropical Plücker vector in $\operatorname {Trop}^+ Gr_{k,n}$. We must show that $Q= P$.

Recall that the map $\operatorname {Trop}\Psi$ depends only on the tropical Plücker coordinates in $\mathcal{C} = \{P_{K(i,j)} \ \vert \ 1 \leq i \leq k, k+1 \leq j \leq n\}$, mapping them to $\{\operatorname {Trop}\Psi (P)_{(i,j)}\}$. Moreover from Lemma 3.18, $\operatorname {Trop}\Psi$ is an injective map from $\mathbb{R}^{k(n-k)}$ to $\mathbb{R}^{k(n-k)}$. Therefore, since $\operatorname {Trop}\Psi$ and $\operatorname {Trop}\Phi$ are inverses, we have that $Q_{K(i,j)} = P_{K(i,j)}$ for all $K(i,j)$ with $1 \leq i \leq k$ and $k+1 \leq j \leq n$. But now from Lemma 3.16, the collection $\{P_{K(i,j)}\}$ is a cluster for the cluster structure on $Gr_{k,n}$. And by OS17, all Plücker clusters can be obtained from each via three-term Plücker relations. Since every Plücker coordinate lies in a Plücker cluster OPS15, the three-term Plücker relations alone (which we know are satisfied since $P\in \operatorname {Dr}^+_{k,n}$) determine all the other values $P_K$ and $Q_K$ for $K \in {[n] \choose k}$, so we must have $P_K = Q_K$ for all $K \in {[n]\choose k}$. Therefore $P=K$ and we are done.

■

Remark 3.19.

One may generalize Theorem 3.9 and its proof to any positroid cell, using the $\vcenter{\img[][6pt][7pt][{\scalebox{-1}[1]{\text{L}}}]{Images/imgd1f0ece8d595253204b01ba52077910b.svg}}$-network associated to a positroid cell and the inverse map from Tal11.

4. The positive tropical Grassmannian and positroidal subdivisions

Recall that $\Delta _{k,n}$ denotes the $(k,n)$-hypersimplex, defined as the convex hull of the points $e_I$ where $I$ runs over $\binom{[n]}{k}$. Consider a real-valued function $\{I\} \mapsto P_I$ on the vertices of $\Delta _{k,n}$. We define a polyhedral subdivision $\mathcal{D}_P$ of $\Delta _{k,n}$ as follows: consider the points $(e_I, P_I)\in \Delta _{k,n} \times \mathbb{R}$ and take their convex hull. Take the lower faces (those whose outwards normal vector have last component negative) and project them back down to $\Delta _{k,n}$; this gives us the subdivision $\mathcal{D}_P$. We will omit the subscript $P$ when it is clear from context. A subdivision obtained in this manner is called regular.

Remark 4.1.

A lower face $F$ of the regular subdivision defined above is determined by some vector $\lambda = (\lambda _1,\dots ,\lambda _n,-1)$ whose dot product with the vertices of the $F$ is maximized. So if $F$ is the matroid polytope of a matroid $M$ with bases $\mathcal{B}$, this is equivalent to saying that $\lambda _{i_1} + \dots + \lambda _{i_k}-P_I = \lambda _{j_1} + \dots + \lambda _{j_k}-P_J > \lambda _{h_1} + \dots + \lambda _{h_k} - P_H$ for any two bases $I,J \in \mathcal{B}$ and $H\notin \mathcal{B}$.

Given a subpolytope $\Gamma$ of $\Delta _{k,n}$, we say that $\Gamma$ is matroidal if the vertices of $\Gamma$, considered as elements of $\binom{[n]}{k}$, are the bases of a matroid $M$, i.e. $\Gamma = \Gamma _M$.

The following result is originally due to Kapranov Kap93; it was also proved in Spe08, Proposition 2.2.

Theorem 4.2.

The following are equivalent.

•

The collection $\{P_I\}_{I \in \binom{[n]}{k}}$ is a tropical Plücker vector.

•

The one-skeleta of $\mathcal{D}_P$ and $\Delta _{k,n}$ are the same.

•

Every face of $\mathcal{D}_P$ is matroidal.

Given a subpolytope $\Gamma$ of $\Delta _{k,n}$, we say that $\Gamma$ is positroidal if the vertices of $\Gamma$, considered as elements of $\binom{[n]}{k}$, are the bases of a positroid $M$, i.e. $\Gamma = \Gamma _M$. The positroidal version of Theorem 4.2 was recently proved in LPW20, and independently in AHLS20.

Theorem 4.3.

The following are equivalent.

•

The collection $\{P_I\}_{I \in \binom{[n]}{k}}$ is a positive tropical Plücker vector.

•

Every face of $\mathcal{D}_P$ is positroidal.

It follows from Theorem 4.3 that the regular subdivisions of $\Delta _{k+1,n}$ consisting of positroid polytopes are precisely those of the form $\mathcal{D}_P$, where $P=\{P_I\}$ is a positive tropical Plücker vector.

5. A new proof that positively oriented matroids are realizable

In 1987, da Silva dS87 conjectured that every positively oriented matroid is realizable. Reformulating this statement in the language of Postnikov’s 2006 preprint Pos, her conjecture says that every positively oriented matroid is a positroid. In 2017, da Silva’s conjecture was proved by Ardila, Rincón and the second author ARW17, using the combinatorics of positroid polytopes. In this section we will give a new proof of the conjecture, using our Theorem 3.9, which we think of as a “tropical version” of da Silva’s conjecture.

Recall that an oriented matroid of rank $k$ on $[n]$ can be specified by its chirotope, which is a function from $[n]^k$ to $\{ -, 0, + \}$ obeying certain axioms BLVS+99. If $M$ is a full rank $k \times n$ real matrix, the function taking $(i_1, i_2, \ldots , i_k)$ to the sign of the minor using columns $(i_1, i_2, \dots , i_k)$ is a chirotope, and the realizable oriented matroids are precisely the chirotopes occurring in this way. Thus, if $M$ represents a point of the totally nonnegative Grassmannian, then $M$ gives a chirotope $\chi$ with $\chi (i_1, i_2, \ldots , i_k) \in \{ 0, + \}$ for $1 \leq i_1 < i_2 < \cdots < i_k \leq n$.

We define a positively oriented matroid to be a chirotope $\chi : [n]^k \to \{ -,0, + \}$ such that $\chi (i_1, i_2, \ldots , i_k) \in \{ 0, + \}$ for $1 \leq i_1 < i_2 < \cdots < i_k \leq n$. Since every positroid gives rise to a positively oriented matroid, to prove da Silva’s conjecture, we need to verify that every positively oriented matroid comes from a positroid, or in other words, is realizable.

Theorem 5.1 (ARW17, Theorem 5.1).

Let $M$ be a positively oriented matroid of rank $k$ on the ground set $[n]$. Then $M$ is realizable.

Before proving Theorem 5.1, we need the following lemma, which was implicit in Spe08, Section 4.

Lemma 5.2.

Suppose that $P = \{P_I\}$ lies in the tropical Grassmannian $\operatorname {Trop}Gr_{k,n}$. Then every face of the matroidal subdivision $\mathcal{D}_P$ of $\Delta _{k,n}$ corresponds to a realizable matroid.

Proof.

Let $\Gamma _M$ be a face of $\mathcal{D}_P$, and let $\mathcal{B}$ denote the bases of the matroid $M$. Adding an affine linear function to $P$, we may assume that $P_I$ is $0$ for $I \in \mathcal{B}$; convexity then implies that $P_I > 0$ for $I \not \in \mathcal{B}$.

Since $P$ lies in the tropical Grassmannian, we can choose a $\mathbb{K}$-valued $k \times n$ matrix $A = A(t)$ whose Plücker coordinates have valuations given by $P=\{P_I\}$ (see the discussion following Definition 3.5). But now if we set $t=0$, then the matrix $A(0)$ has Plücker coordinates which are nonzero for $I\in \mathcal{B}$ and zero for $I\notin \mathcal{B}$. Therefore $M$ is a realizable matroid.

■

Proof of Theorem 5.1.

We first use the matroid $M$ to construct a point of the Dressian, following the method of Spe08, Proposition 4.4 Namely, let $\rho _M$ be the rank function of the matroid $M$, and for $I \in \binom{[n]}{k}$, set $P_I = - \rho _M(I)$. Then Spe08, Proposition 4.4 implies that $P\coloneq \{P_I\}_{I \in {[n] \choose k}}$ is a point of the Dressian, and that the matroid polytope $\Gamma _M$ is a face of the subdivision $\mathcal{D}_P$.

Using the fact that $M$ is positively oriented, we will show that $P$ is in fact a point of the positive Dressian. Indeed, consider any $(k-2)$-element subset $S$ of $[n]$ and any $a<b<c<d$ in $[n] \setminus S$. We need to show that

$$\begin{equation*} P_{Sac}+P_{Sbd} = \min (P_{Sab}+P_{Scd}, P_{Sad}+P_{Sbc}), \end{equation*}$$

or equivalently, that

$$\begin{equation*} \rho _M(Sac)+\rho _M(Sbd) = \max (\rho _M(Sab)+\rho _M(Scd), \rho _M(Sad)+\rho _M(Sbc)). \end{equation*}$$

Let $M'$ be the matroid $(M/S)|_{\{ a,b,c,d \}}$ on the ground set $\{ a,b,c,d \}$. For $x$, $y\in \{a,b,c,d \}$, we have $\rho _M(Sxy) = \rho _M(S) + \rho _{M'}(xy)$. Thus, we need to show that

$$\begin{equation} \rho _{M'}(ac) + \rho _{M'}(bd) = \max (\rho _{M'}(ab) + \rho _{M'}(cd), \rho _{M'}(bc)+\rho _{M'}(ad)). {\tag{5.3}} \end{equation}$$

Now we claim that $M'$, being a minor of a positively oriented matroid, is itself a positively oriented matroid. It is easy to verify that the dual of a positively oriented matroid is again a positively oriented matroid, and moreover, ARW17, Lemma 4.11 showed that positively oriented matroids are closed under restriction. An analogous proof shows that positively oriented matroids are closed under contraction. This verifies the claim.

It now remains to verify 5.3 for all positively oriented matroids on four elements, which is routine.

We now know that $P=\{P_I\}$ lies in the positive Dressian, so Theorem 3.9 shows that $P$ is in the positive tropical Grassmannian. But now by Lemma 5.2, this implies that every face of the matroidal subdivision $\mathcal{D}_P$ of $\Delta _{k,n}$ corresponds to a realizable matroid. In particular, we have $P_I \leq 0$ with equality if and only if $I$ is a basis of $M$, so $\Gamma _M$ is a face of $\mathcal{D}_P$, and we have shown that $\Gamma _M$ is realizable.

■

Interestingly, although the definitions of “positively oriented matroid” and “positroid” don’t involve tropical geometry at all, there does not seem to be a way to remove the tropical geometry from our proof without making it significantly longer.

6. Finest positroidal subdivisions of the hypersimplex

In this section we show that finest positroidal subdivisions of the hypersimplex $\Delta _{k,n}$ achieve equality in the first author’s $f$-vector theorem.

Definition 6.1.

A matroid is called series-parallel if it can be obtained by repeated series-parallel extensions from the matroid corresponding to a generic point of $Gr_{1,2}$.

See Whi86, Section 6.4 for background on series-parallel matroids.

Theorem 6.2 (Spe09).

Let $P$ be a tropical Plücker vector arising as $\operatorname {val}(p_I(A))$ for some $A\in Gr_{k,n}(\mathbb{K})$. Then $\mathcal{D}_P$ has at most $\frac{(n-c-1)!}{(k-c)!(n-k-c)!(c-1)!}$ interior faces of dimension $n-c$, with equality if and only if all facets of $\mathcal{D}_P$ correspond to series-parallel matroids.

In particular, the number of facets of $\mathcal{D}_P$ – that is, the number of matroid polytopes of dimension $n-1$ in $\mathcal{D}_P$ – is at most ${n-2 \choose k-1}$.

The following result can be found in Oxl11, Corollary 11.2.15.

Theorem 6.3.

A connected matroid is series-parallel if and only if it has no minor which is the uniform matroid $U_{2,4}$ or the graphical matroid $M_{K_4}$ associated to the complete graph $K_4$.

The graphical matroid $M_{K_4}$ is not a positroid, and all minors of positroids are positroids ARW16, so we have the following corollary.

Corollary 6.4.

A connected positroid is series-parallel if and only if it has no uniform matroid $U_{2,4}$ as a minor.

If $M$ is a matroid on the ground set $[n]$, with matroid polytope $\Gamma _M$, and $I$ and $J$ are disjoint subsets of $[n]$, then the the polytope $\Gamma _{M \backslash I / J}$ is $\Gamma _M \cap \{ z_i =0 : i \in I \} \cap \{ z_j = 1 : j \in J \}$. So we can phrase Corollary 6.4 as

Corollary 6.5.

Let $M$ be a connected positroid. Then $M$ is series-parallel if and only if its matroid polytope $\Gamma _M$ does not contain any face which is an (unsubdivided) octahedron.

It follows from Proposition 2.5 that in a matroidal subdivision, all facets correspond to connected matroids.

Theorem 6.6.

Let $P = \{P_K\}_{K\in {[n] \choose k}}$ be a positive tropical Plücker vector. For the positroidal subdivision $\mathcal{D}_P$ of $\Delta _{k,n}$, the following are equivalent:

(1)

$\mathcal{D}_P$ is a finest subdivision.

(2)

Every facet of $\mathcal{D}_P$ is the matroid polytope of a series-parallel matroid.

(3)

Every octahedron in $\mathcal{D}_P$ is subdivided.

Proof.

Suppose that (3) holds. Let $\Gamma _M$ be a facet of this subdivision. Since $\dim \Gamma _M = n-1$, the matroid $M$ is connected, and by hypothesis $M$ is a positroid. Hypothesis (3) says that $\Gamma _M$ does not contain any octahedron, so Corollary 6.5 says that $M$ is series-parallel. We have shown $(2)$.

Now suppose that (2) holds. If every facet is series-parallel, then by Theorem 6.2, we get equality in the $f$-vector theorem, and in particular get equality in the $c=1$ term. So we have the maximal number of possible facets, so the positroidal subdivision is finest possible. This implies (1).

Now suppose that (1) holds. To show that every octahedron in $\mathcal{D}_P$ is subdivided, we need to show that we never have equality in a tropical 3-term Plücker relation, in other words, we never have

$$\begin{equation*} P_{Sab}+P_{Scd} = P_{Sad}+P_{Sbc} \end{equation*}$$

for $a<b<c<d$ and $S\in {[n] \choose k-2}$ disjoint from $\{a,b,c,d\}$.

Using the fact that the positive Dressian equals the positive tropical Grassmannian (Theorem 3.9), as well as Remark 3.10, we can use flows in plabic graphs to parameterize the points in the positive Dressian, as in Theorem 8.8. We note that it follows from the technology of PSW09 that a flow is uniquely determined by its weight $\operatorname {wt}(F)$ (compare Definition 4.3 and Table 1, and note that flows are in bijection with almost perfect matchings).

Let us choose a reduced plabic graph $G$ for $(Gr_{k,n})_{>0}$, i.e. a reduced plabic graph with trip permutation $(k+1,k+2,\dots ,n, 1, 2, \dots ,k)$, and choose a perfect orientation $\mathcal{O}$ with sources at $I_{\mathcal{O}} = Sab$. (The fact that we can do so follows from e.g. Proposition 8.4).

Then by Remark 3.10, we can express $P = \operatorname {Trop}\Phi _G(\{X_{\mu }\}),$ for some fixed real values $X_{\mu }$ labeling the faces of $G$. In particular, the coordinates of $P = \{P_K\}_{K\in {[n] \choose k}}$ can be expressed as $P_K = \min _F (\operatorname {Wt}(F)),$ where $F$ ranges over all flows from $Sab$ to $K$, and $\operatorname {Wt}(F)$ is a sum of certain parameters $X_{\mu }$.

Since we are assuming that $\mathcal{D}_P$ is finest, we can assume that the parameters $X_{\mu }$ are generic: that these parameters are distinct real numbers, and that there are not two different subsets of parameters whose sums coincide.

Let us consider the tropical Plücker coordinate $P_{Sab}$. This equals $\min _F (\operatorname {Wt}(F)),$ where $F$ ranges over all flows from $Sab$ to $Sab$; in this case, the flows $F$ are simply collections of vertex-disjoint cycles in $G$ (including the empty collection). We now explain how to reduce to the case that the flow achieving the minimum is the empty flow.

Let $F'$ be the flow achieving the minimum, so $F'$ is a collection of disjoint cycles. Adjust $\mathcal{O}$ to a new perfect orientation $\mathcal{O}'$ by reversing the orientation of all edges belonging to $F'$. Then $\mathcal{O'}$ is again a perfect orientation (see PSW09, Lemma 4.5) and that (preserving the values of the $X_{\mu }$) the collection of new Plücker coordinates are all adjusted by the same scalar (the weight of $F'$), preserving the point in tropical projective space which is represented by $P$. Now, in the orientation $\mathcal{O}'$, the minimum flow for $P_{Sab}$ is the empty flow. We therefore assume, from now on, that the minimum flow for $P_{Sab}$ is the empty flow. With this reduction, we have $P_{Sab}=0$.

Meanwhile $P_{Scd}$ is the weight of the minimal flow $F_2$ from $Sab$ to $Scd$, which will be a pair of paths $\{w_1,w_2\}$ taking $a$ to $d$ and $b$ to $c$ (plus possibly some closed loops). $P_{Sad}$ is the weight of the minimal flow $F_3$ from $Sab$ to $Sad$, which will be a single path $w_3$ from $b$ to $d$ (plus possibly closed loops). And $P_{Sbc}$ is the weight of the minimal flow $F_4$ from $Sab$ to $Sbc$, which will be a single path $w_4$ from $a$ to $c$ (plus possibly closed loops), see Figure 3.

But now because our parameters $X_{\mu }$ associated to the faces are generic, the only way to get equality $P_{Sab}+P_{Scd} = P_{Sad}+P_{Sbc}$ is if our minimal flow $F_2$ from $S_{ab}$ to $S_{cd}$ has to its left precisely the same multiset of faces that the pair of flows $(F_3,F_4)$ (which consists of the paths $w_3,w_4$ plus possibly some loops) does. This is only possible if $w_1$ and $w_2$ are obtained from $w_3$ and $w_4$ by “switching tails” at an intersection point of $w_3$ and $w_4$. But then $\{w_1, w_2\}$ would not be vertex-disjoint and hence not part of a flow.

■

Combining Theorem 3.9, Theorem 6.2, and Theorem 6.6, we now have the following.

Corollary 6.7.

Every finest positroidal subdivision of $\Delta _{k,n}$ achieves equality in the $f$-vector theorem. In particular, such a positroidal subdivision has precisely ${n-2 \choose k-1}$ facets.

7. Nonregular positroidal subdivisions

In this paper we have discussed the positive Dressian, which consists of weight functions on the vertices of the hypersimplex $\Delta _{k,n}$ which induce positroidal subdivisions of $\Delta _{k,n}$; recall that subdivisions induced by weight functions are called regular or coherent. It is also natural to consider the set of all positroidal subdivisions of $\Delta _{k,n}$, whether or not they are regular. (See DLRS10 for background on regular subdivisions.) In this section, we will construct a nonregular positroidal subdivision of $\Delta _{3,12}$, and also make a connection to the theory of tropical hyperplane arrangements and tropical oriented matroids AD09Hor16.

Our strategy for producing the counterexample is as follows. We will start with a standard example of a nonregular rhombic tiling of a hexagon (with side lengths equal to $3$), and extend it to a nonregular mixed subdivision of $9 \Delta _2$; this mixed subdivision gives rise to a dual arrangement $\mathcal{H}$ of $9$ tropical pseudohyperplanes in $\mathbb{T} \mathbb{P}^2$. Moreover, the mixed subdivision corresponds, via the Cayley trick, to a polyhedral subdivision of $\Delta _2 \times \Delta _8$. We then map this polyhedral subdivision to a matroidal subdivision of $\Delta _{3,12}$, and analyze the $0$-dimensional regions of $\mathcal{H}$ to show that it is a positroidal subdivision of $\Delta _{3,12}$. Note that HJJS08, Example 4.7 used a similar strategy to encode a nonregular matroidal subdivision of $\Delta _{3,9}$. We give a careful exposition here in order to verify that our subdivision is positroidal.

7.1. The product of simplices and the hypersimplex

Let $I$ be any $k$-element subset of $[n]$ and let $J = [n] \setminus I$. Let $\Pi _I \subset \Delta _{k,n}$ be the convex hull of all points of the form $e_I - e_i + e_j$ for $i \in I$ and $j \in J$; clearly this set of points is in bijection with $I \times J$. The polytope $\Pi _I$ is isomorphic to $\Delta _{k-1} \times \Delta _{n-k-1}$, with vertices in bijection with $I \times J$. $\Pi _I$ has dimension $n-2$ and sits inside $\Delta _{k,n}$, which has dimension $n-1$. We review standard constructions for passing between polyhedral subdivisions of $\Pi _I$ and matroidal subdivisions of $\Delta _{k,n}$. We will be interested in polyhedral subdivisions of $\Pi _I$ all of whose vertices are vertices of $\Pi _I$, and we will take the phrase “subdivision of $\Pi _I$” to include this condition.

In many references, $I$ is standardized to be $[k]$. However, we will want to keep track of how these standard constructions relate to the property of a matroid being a positroid and, for this purpose, it will be important how $I$ sits inside the circularly ordered set $[n]$, so we do not impose a standard choice of $I$.

Given a matroidal subdivision $\mathcal{D}$ of $\Delta _{k,n}$, we can intersect $\mathcal{D}$ with $\Pi _I$ and obtain a polyhedral subdivision $\mathcal{G}_I$ of $\Pi _I$. If $\mathcal{D}$ is regular, so is $\mathcal{G}_I$.

7.2. From subdivisions of $\Pi _I$ to subdivisions of $\Delta _{k,n}$

Following HJS14, Theorem 7 and Remark 8, as well as Rin13, we will explain how to map each convex hull of vertices of $\Pi _I$ to a matroid polytope inside $\Delta _{k,n}$; this will be the matroid polytope of a principal transversal matroid.

Let $X \subseteq I \times J$. We define a polytope $\gamma (X) = \mathrm{Hull}_{(i,j) \in X} (e_I - e_i + e_j) \subseteq \Pi _I$. We also define a bipartite graph $G(X)$ with vertex set $I \sqcup J = [n]$ and an edge from $i \in I$ to $j \in J$ if and only if $(i,j) \in X$.

Associated to the graph $G(X)$ is the principal transversal matroid $\operatorname {Trans}(G(X))$ (see Bru87 and Whi86, Chapter 7), defined as follows: $B$ is a basis of $\operatorname {Trans}(G(X))$ if and only if there is a matching of $I \setminus B$ to $J \cap B$ in the bipartite graph $G(X)$. The matroid $\operatorname {Trans}(G(X))$ is realized by a $k \times n$ matrix $A = A_X$, with rows labeled by $I$ and columns labeled by $[n]$ where:

•

the values $A_{i j}$ for $(i, j) \in X$ (where $i\in I$ and $j\in J$) are algebraically independent,

•

$A_{i j} = 0$ if $(i, j) \not \in X$ (where $i\in I$ and $j \in J$),

•

$A_{i i'}=\delta _{i i'}$ (where $i, i'\in I$).

Remark 7.1.

Note that the restriction of $A$ to the columns labeled by $I$ is the $k \times k$ identity matrix.

In terms of polyhedral geometry, the matroid polytope of $\operatorname {Trans}(G(X))$ is the intersection of $\Delta _{k,n}$ with $e_I + \operatorname {Span}_{\mathbb{R}_{\geq 0}} \{ e_j - e_i : (i,j) \in X \}$. Summarizing, we have the following.

Lemma 7.2.

Each polytope $\gamma (X) = \mathrm{Hull}_{(i,j) \in X} (e_I - e_i + e_j) \subseteq \Pi _I$ gives rise to the matroid polytope $\Gamma _{\operatorname {Trans}(G(X))} \subseteq \Delta _{k,n}$. Abusing notation, we say that $\operatorname {Trans}$ maps $\gamma (X)$ to $\Gamma _{\operatorname {Trans}(G(X))}$.

If $\mathcal{G}$ is a polyhedral subdivision of $\Pi _I$, then we can apply $\operatorname {Trans}$ to each polytope in $\mathcal{G}$.

Proposition 7.3 (HJS14, Theorem 7 and Remark 8 and Rin13).

If we apply $\operatorname {Trans}$ to each polytope in a polyhedral subdivision $\mathcal{G}$ of $\Pi _I$, then we will obtain a matroid subdivision $\operatorname {Trans}(\mathcal{G})$ of $\Delta _{k,n}$. The subdivision $\operatorname {Trans}(\mathcal{G})$ is regular if and only if $\mathcal{G}$ is.

We will eventually be studying triangulations of $\Pi _I$, so we will want to focus on the case that $\gamma (X)$ is an $(n-2)$-dimensional simplex.

Lemma 7.4.

Let $X \subseteq I \times J$. The following are equivalent:

(1)

The polytope $\gamma (X)$ is an $(n-2)$-dimensional simplex.

(2)

The graph $G(X)$ is a tree on the vertices $[n]$.

Proof.

The equivalence of (1) and (2) is simple. The polytope $\gamma (X)$ is an $(n-2)$-dimensional simplex if and only if it’s the convex hull of $(n-1)$ affinely independent points. But this is equivalent to the statement that $G(X)$ consists of $n-1$ edges and no subset forms a cycle. This means that $G(X)$ is a tree on $[n]$.

■

Remark 7.5.

The conditions from Lemma 7.4 are additionally equivalent to the condition that the matroid $\operatorname {Trans}(G(X))$ is series-parallel. One can prove this using e.g. Spe08, Proposition 5.1.

We will want to know when the matroids in Lemma 7.4 are positroidal. One direction of Lemma 7.6 comes from Mar19, Theorem 6.3.

Lemma 7.6.

Suppose that $X$ is a subset of $I \times J$ such that $G(X)$ is a tree. The matroid $\operatorname {Trans}(G(X))$ is positroidal if and only if we can embed the tree $G(X)$ in a disk so that it is planar, and its vertices lie on the boundary of the disk in the standard circular order on $I \sqcup J = [n]$.

Proof.

If $G(X)$ can be embedded as a planar tree in a disk as above, then this graph is noncrossing, and by Mar19, Theorem 6.3 the transversal matroid $\operatorname {Trans}(G(X))$ is a positroid.

On the other hand, if it cannot be embedded as a planar tree, then we can find $i_1, i_2 \in I$ and $j_1, j_2 \in J$, such that $(i_1,j_1)$ and $(i_2,j_2)$ lie in $X$, and when we put the numbers $\{i_1,i_2,j_1,j_2\}$ at the boundary of a disk in the standard circular order, the two chords $(i_1,j_1)$ and $(i_2,j_2)$ cross each other. Moreover since $G(X)$ is a tree, we cannot have both $(i_1,j_2)$ and $(i_2,j_1)$ in $X$. Without loss of generality we can assume that either $i_1<i_2 < j_1<j_2$ or $i_1 < j_2 < j_1 < i_2$. Let us consider the first case. Then if we look at the rows labeled by $\{i_1,i_2\}$ and the columns labeled by $\{i_1,i_2,j_1,j_2\}$ in the matrix $A = A_X$, we find that the minors $p_{i_1 i_2 }$ and $p_{j_1 j_2}$ are nonzero, but the product $p_{i_1 j_1} p_{i_2 j_2}$ is zero. This fails to be a positroid on $\{i_1, i_2, j_1, j_2\}$ because such conditions are incompatible with finding a non-negative solution to the Plücker relation $p_{i_1 j_1} p_{i_2 j_2} = p_{i_1 i_2} p_{j_1 j_2}+p_{i_1 j_2}p_{i_2 j_1}$. Using Remark 7.1, we can now extend this $2 \times 4$ submatrix of $A$ to a $k \times (k+2)$ submatrix of $A$, by adding the rows and columns indexed by $I \setminus \{i_1,i_2\}$ The second case is analogous.

■

7.3. From tropical pseudohyperplane arrangements to subdivisions of the product of simplices

We now explain how to go between tropical pseudohyperplane arrangements and subdivisions of $\Pi _I$. This section is based on AD09, which initiated the study of tropical oriented matroids and conjectured that they are in bijection with subdivisions of the product of two simplices. AD09 proved their conjecture in the case of $\Delta _{k-1} \times \Delta _2$, which is all we need here; Hor16 proved their conjecture in general. Consult these sources for more detail.

Let $\mathbb{T}\mathbb{P}^{k-1}$ denote tropical projective space $\mathbb{R}^k\!/\mathbb{R}(1,1,\ldots ,1)$, and let $c\!\!=\!\!(c_1, \ldots , c_k)\!$ be an element of $\mathbb{T} \mathbb{P}^{k-1}$. The tropical hyperplane $H_c$ centered at $c$ is the set of points $(x_1, x_2, \ldots , x_k) \in \mathbb{T} \mathbb{P}^{k-1}$ such that $\min _{1 \leq j \leq k} \{x_j - c_j\}$ is not unique. If $x=(x_1, x_2, \ldots , x_k)$ is any point of $\mathbb{T} \mathbb{P}^{k-1}$, we let $S(H,x)$ be the set of indices $j \in [k]$ at which $x_j - c_j$ is minimized. Figure 4 shows a tropical hyperplane in $\mathbb{T} \mathbb{P}^2$, where the horizontal and vertical coordinates are $x_1-x_3$ and $x_2-x_3$, and each region is labelled with the set $S(H,x)$ for $x$ in that region. An arrangement of $m$ labelled tropical hyperplanes is a list of $m$ tropical hyperplanes in $\mathbb{T} \mathbb{P}^{k-1}$.

A tropical pseudohyperplane $H$ is a subset of $\mathbb{T} \mathbb{P}^{k-1}$ which is PL-homeomorphic to a tropical hyperplane. Note that the quantity $S(H,x)$ makes sense for $H$ a tropical pseudohyperplane in $\mathbb{T} \mathbb{P}^{k-1}$ and $x \in \mathbb{T} \mathbb{P}^{k-1}$. An arrangement of $m$ labelled tropical pseudohyperplanes is a list of $m$ tropical pseudohyperplanes which intersect in “reasonable” ways, see Hor16, Section 5 for details. Our main focus in this section will be on the case of tropical pseudohyperplanes in $\mathbb{T} \mathbb{P}^2$.

Consider an arrangement of $n-k$ tropical pseudohyperplanes $H_1$, $H_2$, …, $H_{n-k}$ in $\mathbb{T} \mathbb{P}^{k-1}$. Given a point $x \in \mathbb{T} \mathbb{P}^{k-1}$, we define a subset $X(x)$ of $[k] \times [n-k]$ where $(i,j) \in X(x)$ if and only if $j \in S(H_i, x)$. We can thus associate to each $x\in \mathbb{T} \mathbb{P}^{k-1}$ a polytope $\gamma (X(x)) \subseteq \Delta _{k-1} \times \Delta _{n-k-1}$, as well as the matroid polytope $\Gamma _{\operatorname {Trans}(G(X(x)))}$ of the transversal matroid $\operatorname {Trans}(G(X(x)))$. If we let $x$ range over the bounded regions of the tropical pseudohyperplane arrangement, we obtain the interior regions of a subdivision of $\Delta _{k-1} \times \Delta _{n-k-1}$. Using DS04, Theorem 1 and Hor16, Theorems 1.2 and 1.3, this subdivision is regular if and only if tropical pseudohyperplane arrangement can be realized by genuine tropical hyperplanes.

7.4. Our counterexample

We start with the mixed subdivision of $9 \Delta _2$ shown in Figure 5. The subdivision of the central hexagon (with each side of length $3$) is a standard example of a nonregular subdivision of a hexagon into rhombi, originally found by Richter-Gebert, see ER96, Figure 9. Thus, this mixed subdivision of $9 \Delta _2$ is not regular.

Mixed subdivisions of $b \Delta _{a-1}$ are dual to arrangements of $b$ labeled tropical pseudohyperplanes in $\mathbb{T} \mathbb{P}^{a-1}$. The arrangement of $9$ tropical pseudohyperplanes in $\mathbb{T} \mathbb{P}^2$ which is dual to the mixed subdivision from Figure 5 is shown in Figure 6. In this figure we have labeled the coordinates of $\mathbb{T} \mathbb{P}^2$ by $\{ 4, 8, 12 \}$ – placing the labels at the “ends” of the rays, according to which coordinate is becoming large along the ray – and labelled the tropical pseudohyperplanes by $\{ 1,2,3,5,6,7,9,10,11 \}$, placing the label at the trivalent point.

Also, by the “Cayley trick” HRS00San05, mixed subdivisions of $b \Delta _{a-1}$ correspond to polyhedral subdivisions of $\Delta _{a-1} \times \Delta _{b-1}$, with regular mixed subdivisions of $b \Delta _{a-1}$ corresponding to regular polyhedral subdivisions of $\Delta _{a-1} \times \Delta _{b-1}$. Therefore the mixed subdivision from Figure 5 corresponds to a nonregular polyhedral subdivision of $\Pi _{\{ 4,8,12 \}} \subset \Delta _{3,12}$.

It remains to check that this subdivision is positroidal. We need to check that each of the $45$ two-dimensional polytopes in Figure 5, or equivalently, each of the $45$ zero-dimensional cells of the tropical pseudohyperplane arrangement in Figure 6, corresponds to a positroid. Letting $x$ be one of these zero dimensional cells, we must check that $G(X(x))$ is a tree in each case, which can be embedded in a disk as in Lemma 7.6.

For example, let $x$ be the crossing which is circled in Figure 6; the dual rhombus is shaded in Figure 5. We have

$$\begin{equation*} \begin{array}{lcl@{\quad }lcl@{\quad }lcl} S(H_1, x) &=& \{ 12 \} & S(H_2,x) &=& \{ 12 \} & S(H_3, x) &=& \{ 4, 12 \} \\S(H_5, x) &=& \{ 4,8 \} & S(H_6, x) &=& \{ 8 \} & S(H_7, x) &=& \{ 8 \} \\S(H_9, x) &=& \{ 8 \} & S(H_{10}, x) &=& \{ 8 \} & S(H_{11}, x) &=& \{ 12 \} \\\end{array} \end{equation*}$$

We draw the corresponding tree in Figure 7.

8. Appendix. Combinatorics of cells of the positive Grassmannian

In Pos, Postnikov defined several families of combinatorial objects which are in bijection with cells of the positive Grassmannian, including decorated permutations, and equivalence classes of reduced plabic graphs. Here we review these objects as well as parameterizations of cells.

Definition 8.1.

A decorated permutation of $[n]$ is a bijection $\pi : [n] \to [n]$ whose fixed points are each colored either black (loop) or white (coloop). We denote a black fixed point $i$ by $\pi (i) = \underline{i}$, and a white fixed point $i$ by $\pi (i) = \overline{i}$. An anti-excedance of the decorated permutation $\pi$ is an element $i \in [n]$ such that either $\pi ^{-1}(i) > i$ or $\pi (i)=\overline{i}$.

For example, $\pi = (3,\underline{2},5,1,6,8,\overline{7},4)$ has a loop in position $2$, and a coloop in position $7$. It has three anti-excedances, in positions $4, 7, 8$. We let $k(\pi )$ denote the number of anti-excedances of $\pi$.

Postnikov showed that the positroids for $Gr_{k,n}^{\ge 0}$ are indexed by decorated permutations of $[n]$ with exactly $k$ anti-excedances Pos, Section 16.

Definition 8.2.

A plabic graph⁠⁴ is an undirected planar graph $G$ drawn inside a disk (considered modulo homotopy) with $n$ boundary vertices on the boundary of the disk, labeled $1,\dots ,n$ in clockwise order, as well as some internal vertices. Each boundary vertex is incident to a single edge, and each internal vertex is colored either black or white. If a boundary vertex is incident to a leaf (a vertex of degree $1$), we refer to that leaf as a lollipop.

⁴

“Plabic” stands for planar bi-colored.

✖

Definition 8.3.

A perfect orientation $\mathcal{O}$ of a plabic graph $G$ is a choice of orientation of each of its edges such that each black internal vertex $u$ is incident to exactly one edge directed away from $u$; and each white internal vertex $v$ is incident to exactly one edge directed towards $v$. A plabic graph is called perfectly orientable if it admits a perfect orientation. Let $G_\mathcal{O}$ denote the directed graph associated with a perfect orientation $\mathcal{O}$ of $G$. The source set $I_\mathcal{O} \subset [n]$ of a perfect orientation $\mathcal{O}$ is the set of $i$ which are sources of the directed graph $G_\mathcal{O}$. Similarly, if $j \in \overline{I}_{\mathcal{O}} \coloneq [n] - I_{\mathcal{O}}$, then $j$ is a sink of $\mathcal{O}$.

See Figure 8 for an example.

All perfect orientations of a fixed plabic graph $G$ have source sets of the same size $k$, where $k-(n-k) = \sum \mathrm{color}(v)\cdot (\deg (v)-2)$. Here the sum is over all internal vertices $v$, $\mathrm{color}(v) = 1$ for a black vertex $v$, and $\mathrm{color}(v) = -1$ for a white vertex; see Pos. In this case we say that $G$ is of type $(k,n)$.

As shown in Pos, Section 11, every perfectly orientable plabic graph gives rise to a positroid as follows. (Moreover, every positroid can be realized in this way.)

Proposition 8.4.

Let $G$ be a plabic graph of type $(k,n)$. Then we have a positroid $M_G$ on $[n]$ whose bases are precisely

$$\begin{equation*} \{I_{\mathcal{O}} \mid \mathcal{O} \text{ is a perfect orientation of }G\}, \end{equation*}$$

where $I_\mathcal{O}$ is the set of sources of $\mathcal{O}$.

Each positroid cell corresponds to a family of reduced plabic graphs which are related to each other by certain moves; see Pos, Section 12. From a reduced plabic graph $G$, we can read off the corresponding decorated permutation $\pi _G$ as follows.

Definition 8.5.

Let $G$ be a reduced plabic graph of type $(k,n)$ with boundary vertices $1,\dots , n$. For each boundary vertex $i\in [n]$, we follow a path along the edges of $G$ starting at $i$, turning (maximally) right at every internal black vertex, and (maximally) left at every internal white vertex. This path ends at some boundary vertex $\pi (i)$. By Pos, Section 13, the fact that $G$ is reduced implies that each fixed point of $\pi$ is attached to a lollipop; we color each fixed point by the color of its lollipop. In this way we obtain the decorated permutation $\pi _G = \pi$ of $G$. The decorated permutation $\pi _G$ will have precisely $k$ anti-excedances.

We now explain how to parameterize elements of positroid cells using perfect orientations of reduced plabic graphs.

We will associate a parameter $x_{\mu }$ to each face of $G$, letting $\mathcal{P}_G$ denote the indexing set for the faces. We require that the product $\prod _{\mu \in \mathcal{P}_G} x_{\mu }$ of all parameters equals $1$. A flow $F$ from $I_{\mathcal{O}}$ to a set $J$ of boundary vertices with $|J|=|I_{\mathcal{O}}|$ is a collection of paths and closed cycles in $\mathcal{O}$, all pairwise vertex-disjoint, such that the sources of the paths are $I_{\mathcal{O}} - (I_{\mathcal{O}} \cap J)$ and the destinations of the paths are $J - (I_{\mathcal{O}} \cap J)$.

Note that each directed path and cycle $w$ in $\mathcal{O}$ partitions the faces of $G$ into those which are on the left and those which are on the right of $w$. We define the weight $\operatorname {wt}(w)$ of each such path or cycle to be the product of parameters $x_{\mu }$, where $\mu$ ranges over all face labels to the left of the path. And we define the weight $\operatorname {wt}(F)$ of a flow $F$ to be the product of the weights of all paths and cycles in the flow.

Fix a perfect orientation $\mathcal{O}$ of a reduced plabic graph $G$. Given $J \in {[n] \choose k}$, we define the flow polynomial

$$\begin{equation} p_J^G = \sum _F \operatorname {wt}(F), {\tag{8.6}} \end{equation}$$

where $F$ ranges over all flows from $I_{\mathcal{O}}$ to $J$.

Example 8.7.

Consider the graph from Figure 8. There are two flows $F$ from $I_{\mathcal{O}}$ to $\{2,4\}$, and $P^G_{\{2,4\}} = x_{\vcenter{\img[][12pt][5pt][{\ydiagram{3}}]{Images/imgfa1cd1a2a7b64d26ff454eb24769ead5.svg}}} x_{\vcenter{\img[][9pt][8pt][{\ydiagram{2,2}}]{Images/imgd0e86e742b907305528e883fdde9438b.svg}}} x_{\vcenter{\img[][12pt][8pt][{\ydiagram{3,3}}]{Images/imgf777d6fd5b741d6ba5e3e360e249fea3.svg}}} +x_{\vcenter{\img[][9pt][5pt][{\ydiagram{2}}]{Images/imga6e7d436279b36ae53cb717cbf4d8abb.svg}}} x_{\vcenter{\img[][12pt][5pt][{\ydiagram{3}}]{Images/imgfa1cd1a2a7b64d26ff454eb24769ead5.svg}}} x_{\vcenter{\img[][9pt][8pt][{\ydiagram{2,2}}]{Images/imgd0e86e742b907305528e883fdde9438b.svg}}} x_{\vcenter{\img[][12pt][8pt][{\ydiagram{3,3}}]{Images/imgf777d6fd5b741d6ba5e3e360e249fea3.svg}}}$. There is one flow from $I_{\mathcal{O}}$ to $\{3,4\}$, and $P^G_{\{3,4\}} = x_{\vcenter{\img[][9pt][5pt][{\ydiagram{2}}]{Images/imga6e7d436279b36ae53cb717cbf4d8abb.svg}}} x_{\vcenter{\img[][12pt][5pt][{\ydiagram{3}}]{Images/imgfa1cd1a2a7b64d26ff454eb24769ead5.svg}}} x_{\vcenter{\img[][9pt][8pt][{\ydiagram{2,2}}]{Images/imgd0e86e742b907305528e883fdde9438b.svg}}} x_{\vcenter{\img[][12pt][8pt][{\ydiagram{3,3}}]{Images/imgf777d6fd5b741d6ba5e3e360e249fea3.svg}}}^2.$$\lozenge$

The following result is a combination of Pos, Theorem 12.7 and Tal08, Theorem 1.1.

Theorem 8.8.

Let $G$ be a reduced plabic graph of type $(k,n)$, and choose a perfect orientation $\mathcal{O}$ with source set $I_{\mathcal{O}}$. Then the map $\Phi _G$ sending $(x_{\mu })_{\mu \in \mathcal{P}_G} \in (\mathbb{R}_{>0})^{\mathcal{P}_G}$ to the collection of flow polynomials $\{p_J^G\}_{J\in {[n] \choose k}}$ is a homemorphism from $(\mathbb{R}_{>0})^{\mathcal{P}_G}$ to the corresponding positroid cell $S_G \subset Gr_{k,n}$ (realized in its Plücker embedding).

Figure 1.

$\operatorname {Web}_{k,n}$ for $k=3$ and $n=6$. If $w$ is the path on the right-hand side, then $\operatorname {wt}(w) = x_{25}x_{24}x_{36} x_{35}x_{34}$ and $\operatorname {Wt}(w) = X_{25}+X_{24}+X_{36} +X_{35}+X_{34}.$

Figure 2.

Inverting the map.

Figure 3.

Flows $F_1, F_2, F_3, F_4$ used to compute $P_{Sab}, P_{Scd}, P_{Sad}, P_{Sbc}$.

Figure 4.

The labeling of the regions of a tropical hyperplane.

Figure 5.

A nonregular subdivision of $9 \Delta _2$.

Figure 6.

The dual arrangement of $9$ tropical pseudohyperplanes.

Figure 7.

The planar tree corresponding to the marked point in Figure 6. Elements of $I$ are shown in white.

Figure 8.

A plabic graph $G$ with trip permutation $(3,4,5,1,2)$, together with a perfect orientation $\mathcal{O}$ with source set $I_\mathcal{O} = \{1,2\}$.