text:
# The tropical Grassmannian

## 1 Introduction

The *tropical semiring* $`(\{\mathrm{}\},\mathrm{min},+)`$ is the set of real numbers augmented by infinity with the *tropical addition*, which is taking the minimum of two numbers, and the *tropical multiplication* which is the ordinary addition . These operations satisfy the familiar axioms of arithmetic, e.g. distributivity, with $`\mathrm{}`$ and $`0`$ being the two neutral elements. *Tropical monomials* $`x_1^{a_1}\mathrm{}x_n^{a_n}`$ represent ordinary linear forms $`_ia_ix_i`$, and *tropical polynomials*

$$F(x_1,x_2,\mathrm{},x_n)=\underset{a𝒜}{}C_ax_1^{a_1}x_2^{a_2}\mathrm{}x_n^{a_n},\text{with}𝒜^n,C_a,$$
(1)
represent piecewise-linear convex functions $`F:^n`$. To compute $`F(x)`$, we take the minimum of the affine-linear forms $`C_a+_{i=1}^na_ix_i`$ for $`a𝒜`$. We define the *tropical hypersurface* $`𝒯(F)`$ as the set of all points $`x`$ in $`^n`$ for which this minimum is attained at least twice, as $`a`$ runs over $`𝒜`$. Equivalently, $`𝒯(F)`$ is the set of all points $`x^n`$ at which $`F`$ is not differentiable. Thus a tropical hypersurface is an $`(n1)`$-dimensional polyhedral complex in $`^n`$.

The rationale behind this definition will become clear in Section 2, which gives a self-contained development of the basic theory of tropical varieties. For further background and pictures see \[14, §9\]. Every tropical variety is a finite intersection of tropical hypersurfaces (Corollary 2.3). But not every intersection of tropical hypersurfaces is a tropical variety (Proposition 6.3). Tropical varieties are also known as *logarithmic limit sets* , *Bieri-Groves sets* , or *non-archimedean amoebas* . Tropical curves are the key ingredient in Mikhalkin’s formula  for planar Gromov-Witten invariants.

The object of study in this paper is the tropical Grassmannian $`𝒢_{d,n}`$ which is a polyhedral fan in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ defined by the ideal of quadratic Plücker relations. All of our main results regarding $`𝒢_{d,n}`$ are stated in Section 3. The proofs appear in the subsequent sections. In Section 4 we prove Theorem 3.4 which identifies $`𝒢_{2,n}`$ with the space of phylogenetic trees in . A detailed study of the fan $`𝒢_{3,6}^{20}`$ is presented in Section 5. In Section 6 we introduce tropical linear spaces and we prove that they are parametrized by the tropical Grassmannian (Theorem 3.6). In Section $`7`$ we show that the tropical Grassmannian $`𝒢_{3,7}`$ depends on the characteristic of the ground field.

## 2 The tropical variety of a polynomial ideal

Let $`K`$ be an algebraically closed field with a valuation into the reals, denoted $`\mathrm{deg}:K^{}`$. We assume that 1 lies in the image of $`\mathrm{deg}`$ and we fix $`tK^{}`$ with $`\mathrm{deg}(t)=1`$. The corresponding local ring and its maximal ideal are

$$R_K=\{cK:\mathrm{deg}(c)0\}\text{and}M_K=\{cK:\mathrm{deg}(c)>0\}.$$

The residue field $`k=R_K/M_K`$ is algebraically closed. Given any ideal

$$IK[x]=K[x_1,x_2,\mathrm{},x_n],$$

we consider its affine variety in the *$`n`$-dimensional algebraic torus* over $`K`$,

$$V(I)=\{u(K^{})^n:f(u)=\mathrm{\hspace{0.17em}0}\text{for all}fI\}.$$

Here $`K^{}=K\backslash \{0\}`$. In all our examples, $`K`$ is the algebraic closure of the rational function field $`(t)`$ and “deg” is the standard valuation at the origin. Then $`k=`$, and if $`c[t]`$ then $`\mathrm{deg}(c)`$ is the order of vanishing of $`c`$ at $`0`$.

Every polynomial in $`K[x]`$ maps to a tropical polynomial as follows. If

$$f(x_1,\mathrm{},x_n)=\underset{a𝒜}{}c_ax_1^{a_1}\mathrm{}x_n^{a_n}\text{with }c_aK^{}\text{ for }a𝒜.$$
(2)
and $`C_a=\mathrm{deg}(c_a)`$, then $`\mathrm{trop}(f)`$ denotes the tropical polynomial $`F`$ in (1).

The following definitions are a variation on Gröbner basis theory . Fix $`w^n`$. The *$`w`$-weight* of a term $`c_ax_1^{a_1}\mathrm{}x_n^{a_n}`$ in (2) is $`\mathrm{deg}(c_a)+a_1w_1+\mathrm{}+a_nw_n`$. The *initial form* $`\mathrm{in}_w(f)`$ of a polynomial $`f`$ is defined as follows. Set $`\stackrel{~}{f}(x_1,\mathrm{},x_n)=f(t^{w_1}x_1,\mathrm{},t^{w_n}x_n)`$. Let $`\nu `$ be the smallest weight of any term of $`f`$, so that $`t^\nu \stackrel{~}{f}`$ is a non-zero element in $`R_K[x]`$. Define $`\mathrm{in}_w(f)`$ as the image of $`t^\nu \stackrel{~}{f}`$ in $`k[x]`$. We set $`\mathrm{in}_w(0)=0`$. For $`K=\overline{(t)}`$ and $`k=`$ this means that the initial form $`\mathrm{in}_w(f)`$ is a polynomial in $`[x]`$.

Given any ideal $`IK[x]`$, then its *initial ideal* is defined to be

$$\mathrm{in}_w(I)=\mathrm{in}_w(f):fIk[x].$$

###### Theorem 2.1.

For an ideal $`IK[x]`$ the following subsets of $`^n`$ coincide:

* The closure of the set $`\{(\mathrm{deg}(u_1),\mathrm{},\mathrm{deg}(u_n)):(u_1,\mathrm{},u_n)V(I)\}`$;
* The intersection of the tropical hypersurfaces $`𝒯(\mathrm{trop}(f))`$ where $`fI`$;
* The set of all vectors $`w^n`$ such that $`\mathrm{in}_w(I)`$ contains no monomial.

The set defined by the three conditions in Theorem 2.1 is denoted $`𝒯(I)`$ and is called the *tropical variety* of the ideal $`I`$. Variants of this theorem already appeared in \[14, Theorem 9.17\] and in \[7, Theorem 6.1\], without and with proof respectively. Here we present a short proof which is self-contained.

###### Proof.

First consider any point $`w=(\mathrm{deg}(u_1),\mathrm{},\mathrm{deg}(u_n))`$ in the set (a). For any $`fI`$ we have $`f(u_1,\mathrm{},u_n)=0`$ and this implies that the minimum in the definition of $`F=\mathrm{trop}(f)`$ is attained at least twice at $`w`$. This condition is equivalent to $`\mathrm{in}_w(f)`$ not being a monomial. This shows that (a) is contained in (b), and (b) is contained in (c). It remains to prove that (c) is contained in (a). Consider any vector $`w`$ in (c) such that $`w=(\mathrm{deg}(v_1),\mathrm{},\mathrm{deg}(v_n))`$ for some $`v(K^{})^n`$. Since the image of the valuation is dense in $``$ and the set defined in (a) is closed, it suffices to prove that $`w=(\mathrm{deg}(u_1),\mathrm{},\mathrm{deg}(u_n))`$ for some $`uV(I)`$. By making the change of coordinates $`x_i=x_iv_i^1`$, we may assume that $`w=(0,0,\mathrm{},0)`$.

Since $`\mathrm{in}_w(I)`$ contains no monomial and since $`k`$ is algebraically closed, by the Nullstellensatz there exists a point $`\overline{u}V(\mathrm{in}_w(I))(k^{})^n`$. Let $`\overline{m}`$ denote the maximal ideal in $`k[x]`$ corresponding to $`\overline{u}`$. Let $`S`$ be the set of polynomials $`f`$ in $`R_K[x]`$ whose reduction modulo $`M_K`$ is not in $`\overline{m}`$. Then $`S`$ is a multiplicative set in $`R_K[x]`$ disjoint from $`I`$. Consider the induced map

$$\varphi :R_KS^1R_K[x]/S^1(IR_K[x])$$

Let $`P`$ be a minimal prime of the ring on the right hand side. We claim that $`\varphi ^1(P)=\{0\}`$. Suppose not, and pick $`cR_K\backslash \{0\}`$ with $`\varphi (c)P`$. Then $`\varphi (c)`$ is a zero-divisor in $`R_K[x]/S^1(IR_K[x])`$, so we can find $`fS`$ such that $`cfI`$. Since $`c^1`$ exists in $`K`$, this implies $`fI`$ which is a contradiction.

Now, $`\varphi ^1(P)=\{0\}`$ implies that $`P_{R_K}K`$ is a proper ideal in $`K[x]/I`$. There exists a maximal ideal of $`K[x]/I`$ containing $`P_{R_K}K`$, and, since $`K`$ is algebraically closed, this maximal ideal has the form $`x_1u_1,\mathrm{},x_nu_n`$ for some $`uV(I)(K^{})^n`$. We claim that $`u_iR_K`$ and $`u_i\overline{u}_imodM_K`$. This will imply $`\mathrm{deg}(u_1)=\mathrm{}=\mathrm{deg}(u_1)=0`$ and hence complete the proof.

Consider any $`x_iu_iI`$. By clearing denominators, we get $`a_ixb_iIR_K[x]`$ with $`b_i/a_i=u_i`$, and not both $`a_i`$ and $`b_i`$ lie in $`M_k`$. If $`a_iM_K`$, then $`a_ixb_ib_imodM_K`$. Hence $`\mathrm{in}_w(I)`$ contains $`b_iK^{}`$ and hence equals the unit ideal, which is a contradiction. If $`a_iM_K`$ and $`b_i/a_i\cong ̸\overline{u}_imodM_K`$ then the reduction of $`a_ixb_i`$ modulo $`M_K`$ does not lie in $`\overline{m}`$. This means that $`a_ixb_iS`$ and is a unit of $`S^1R_K[x]`$, so $`P`$ is the unit ideal. But then $`P`$ is not prime, also a contradiction. This completes the proof. ∎

The key point in the previous proof can be summarized as follows:

###### Corollary 2.2.

Every zero over $`k`$ of the initial ideal $`\mathrm{in}_w(I)`$ lifts to a zero over $`K`$ of $`I`$.

By zero of an ideal $`I`$ in $`K[x]`$ we mean a point on its variety in $`(K^{})^n`$. The notion of (reduced) Gröbner bases is well-defined for ideals $`IK[x]`$ and (generic) weight vectors $`w`$, and, by adapting the methods of \[13, §3\] to our situation, we can compute a *universal Gröbner basis* $`\mathrm{UGB}(I)`$. This is a finite subset of $`I`$ which contains a Gröbner basis for $`I`$ with respect to any weight vector $`w^n`$. From part (c) of Theorem 2.1 we derive:

###### Corollary 2.3.

\[Finiteness in Tropical Geometry\] The tropical variety $`𝒯(I)`$ is the intersection of the tropical hypersurfaces $`𝒯(\mathrm{trop}(f))`$ where $`f\mathrm{UGB}(I)`$.

The following result is due to Bieri and Groves . An alternative proof using Gröbner basis methods appears in \[14, Theorem 9.6\].

###### Theorem 2.4.

\[Bieri-Groves Theorem\] If $`I`$ is a prime ideal and $`K[x]/I`$ has Krull dimension $`r`$, then $`𝒯(I)`$ is a pure polyhedral complex of dimension $`r`$.

We shall be primarily interested in the case when $`k=`$ and $`K=\overline{(t)}`$. Under this hypothesis, the ideal $`I`$ is said to have *constant coefficients* if the coefficients $`c_a`$ of the generators $`f`$ of $`I`$ lie in the ground field $``$. This implies $`C_a=\mathrm{deg}(c_a)=0`$ in (1), where $`F=\mathrm{trop}(f)`$. Our problem is now to solve a system of tropical equations all of whose coefficients are identically zero:

$$F(x_1,x_2,\mathrm{},x_n)=\underset{a𝒜}{}\mathrm{\hspace{0.17em}0}x_1^{a_1}x_2^{a_2}\mathrm{}x_n^{a_n}.$$
(3)
Here the tropical variety is a subfan of the Gröbner fan of an ideal in $`[x]`$.

###### Corollary 2.5.

If $`I`$ has constant coefficients then $`𝒯(I)`$ is a fan in $`^n`$.

## 3 Results on the tropical Grassmannian

We fix a polynomial ring in $`\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$ variables with integer coefficients:

$$[p]=[p_{i_1i_2\mathrm{}i_d}:\mathrm{\hspace{0.17em}1}i_1<i_2<\mathrm{}<i_dn].$$

The *Plücker ideal* $`I_{d,n}`$ is the homogeneous prime ideal in $`[p]`$ consisting of the algebraic relations among the $`d\times d`$-subdeterminants of any $`d\times n`$-matrix with entries in any commutative ring. The ideal $`I_{d,n}`$ is generated by quadrics, and it has a well-known quadratic Gröbner basis (see e.g. \[12, Theorem 3.1.7\]). The projective variety of $`I_{d,n}`$ is the *Grassmannian* $`G_{d,n}`$ which parametrizes all $`d`$-dimensional linear subspaces of an $`n`$-dimensional vector space.

The *tropical Grassmannian* $`𝒢_{d,n}`$ is the tropical variety $`𝒯(I_{d,n})`$ of the Plücker ideal $`I_{d,n}`$, over a field $`K`$ as in Section 2. Theorem 2.1 (c) implies

$$𝒢_{d,n}=\{w^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}:\mathrm{in}_w(I_{d,n})\text{contains no monomial}\}.$$

The ring $`([p]/I_{d,n})K`$ is known to have Krull dimension $`(nd)d+1`$. Therefore Theorem 2.4 and Corollary 2.5 imply the following statement.

###### Corollary 3.1.

The tropical Grassmannian $`𝒢_{d,n}`$ is a polyhedral fan in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$. Each of its maximal cones has the same dimension, namely, $`(nd)d+1`$.

We show in Section 7 that the fan $`𝒢_{d,n}`$ depends on the characteristic of $`K`$ if $`d3`$ and $`n7`$. All results in Sections 2–6 are valid over any field $`K`$.

It is convenient to reduce the dimension of the tropical Grassmannian. This can be done in three possible ways. Let $`\varphi `$ denote the linear map from $`^n`$ into $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ which sends an $`n`$-vector $`(a_1,a_2,\mathrm{},a_n)`$ to the $`\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$-vector whose $`(i_1,\mathrm{},i_d)`$-coordinate is $`a_{i_1}+\mathrm{}+a_{i_d}`$. The map $`\varphi `$ is injective, and its image is the common intersection of all cones in the tropical Grassmannian $`𝒢_{d,n}`$. Note that vector $`(1,\mathrm{},1)`$ of length $`\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$ lies in $`\mathrm{image}(\varphi )`$. We conclude:

* The image of $`𝒢_{d,n}`$ in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}/(1,\mathrm{},1)`$ is a fan $`𝒢_{d,n}^{}`$ of dimension $`d(nd)`$.
* The image of $`𝒢_{d,n}`$ or $`𝒢_{d,n}^{}`$ in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}/\mathrm{image}(\varphi )`$ is a fan $`𝒢_{d,n}^{\prime \prime }`$ of dimension $`(d1)(nd1)`$. No cone in this fan contains a non-zero linear space.
* Intersecting $`𝒢_{d,n}^{\prime \prime }`$ with the unit sphere yields a polyhedral complex $`𝒢_{d,n}^{\prime \prime \prime }`$. Each maximal face of $`𝒢_{d,n}^{\prime \prime \prime }`$ is a polytope of dimension $`ndnd^2`$.

We shall distinguish the four objects $`𝒢_{d,n}`$, $`𝒢_{d,n}^{}`$, $`𝒢_{d,n}^{\prime \prime }`$ and $`𝒢_{d,n}^{\prime \prime \prime }`$ when stating our theorems below. In subsequent sections less precision is needed, and we sometimes identify $`𝒢_{d,n}`$, $`𝒢_{d,n}^{}`$, $`𝒢_{d,n}^{\prime \prime }`$ and $`𝒢_{d,n}^{\prime \prime \prime }`$ if there is no danger of confusion.

###### Example 3.2.

$`(d=2,n=4)`$ The smallest non-zero Plücker ideal is the principal ideal $`I_{2,4}=p_{12}p_{34}p_{13}p_{24}+p_{14}p_{23}`$. Here $`𝒢_{2,4}`$ is a fan with three five-dimensional cones $`^4\times _0`$ glued along $`^4=\mathrm{image}(\varphi )`$. The fan $`𝒢_{2,4}^{\prime \prime }`$ consists of three half rays emanating from the origin (the picture of a tropical line). The zero-dimensional simplicial complex $`𝒢_{2,4}^{\prime \prime \prime }`$ consists of *three points*.

###### Example 3.3.

$`(d=2,n=5)`$ The tropical Grassmannian $`𝒢_{2,5}^{\prime \prime \prime }`$ is the *Petersen graph* with $`10`$ vertices and $`15`$ edges. This was shown in \[14, Example 9.10\].

The following theorem generalizes both of these examples. It concerns the case $`d=2`$, that is, the tropical Grassmannian of lines in $`(n1)`$-space.

###### Theorem 3.4.

The tropical Grassmannian $`𝒢_{2,n}^{\prime \prime \prime }`$ is a simplicial complex known as space of phylogenetic trees. It has $`2^{n1}n1`$ vertices, $`13\mathrm{}(2n5)`$ facets, and its homotopy type is a bouquet of $`(n2)!`$ spheres of dimension $`n4`$.

A detailed description of $`𝒢_{2,n}`$ and the proof of this theorem will be given in Section 4. Metric properties of the *space of phylogenetic trees* were studied by Billera, Holmes and Vogtmann in  (our $`n`$ corresponds to Billera, Holmes and Vogtmann’s $`n+1`$.) The abstract simplicial complex and its homotopy type had been found earlier by Vogtmann  and by Robinson and Whitehouse . The description has the following corollary. Recall that a simplicial complex is a *flag complex* if the minimal non-faces are pairs of vertices. This property is crucial for the existence of unique geodesics in .

###### Corollary 3.5.

The simplicial complex $`𝒢_{2,n}^{\prime \prime \prime }`$ is a flag complex.

We do not have a complete description of the tropical Grassmannian in the general case $`d3`$ and $`nd3`$. We did succeed, however, in computing all monomial-free initial ideals $`\mathrm{in}_w(I_{d,n})`$ for $`d=3`$ and $`n=6`$:

###### Theorem 3.6.

The tropical Grassmannian $`𝒢_{3,6}^{\prime \prime \prime }`$ is a $`3`$-dimensional simplicial complex with $`65`$ vertices, $`550`$ edges, $`1395`$ triangles and $`1035`$ tetrahedra.

The proof and complete description of $`𝒢_{3,6}`$ will be presented in Section 5. We shall see that $`𝒢_{3,6}`$ differs in various ways from the tree space $`𝒢_{2,n}`$. Here is one instance of this, which follows from Theorem 5.4. Another one is Corollary 4.4 versus Proposition 5.5.

###### Corollary 3.7.

The tropical Grassmannian $`𝒢_{3,6}^{\prime \prime \prime }`$ is not a flag complex.

If $`X`$ is a $`d`$-dimensional linear subspace of the vector space $`K^n`$, then (the topological closure of) its image $`\mathrm{deg}(X)`$ under the degree map is a polyhedral complex in $`^n`$. Such a polyhedral complex arising from a $`d`$-plane in $`K^n`$ is called a *tropical $`d`$-plane in $`n`$-space*. Since $`X`$ is invariant under scaling, every cone in $`\mathrm{deg}(X)`$ contains the line spanned by $`(1,1,\mathrm{},1)`$, so we can identify $`\mathrm{deg}(X)`$ with its image in $`^n/(1,1,\mathrm{},1)^{n1}`$. Thus $`\mathrm{deg}(X)`$ becomes a $`(d1)`$-dimensional polyhedral complex in $`^{n1}`$. For $`d=2`$, we get a tree.

The classical Grassmannian $`G_{d,n}`$ is the projective variety in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)1}`$ defined by the Plücker ideal $`I_{d,n}`$. There is a canonical bijection between $`G_{d,n}`$ and the set of $`d`$-planes through the origin in $`K^n`$. The analogous bijection for the tropical Grassmannian $`𝒢_{d,n}^{}`$ is the content of the next theorem.

###### Theorem 3.8.

The bijection between the classical Grassmannian $`G_{d,n}`$ and the set of $`d`$-planes in $`K^n`$ induces a unique bijection $`wL_w`$ between the tropical Grassmannian $`𝒢_{d,n}^{}`$ and the set of tropical $`d`$-planes in $`n`$-space.

Theorems 3.4, 3.6 and 3.8 are proved in Sections 4, 5 and 6 respectively.

## 4 The space of phylogenetic trees

In this section we prove Theorem 3.4 which asserts that the *tropical Grassmannian of lines* $`𝒢_{2,n}`$ coincides with the *space of phylogenetic trees* . We begin by reviewing the simplicial complex $`𝐓_n`$ underlying this space.

The vertex set $`\mathrm{Vert}(𝐓_n)`$ consists of all unordered pairs $`\{A,B\}`$, where $`A`$ and $`B`$ are disjoint subsets of $`[n]:=\{1,2,\mathrm{},n\}`$ having cardinality at least two, and $`AB=[n]`$. The cardinality of $`\mathrm{Vert}(𝐓_n)`$ is $`\mathrm{\hspace{0.17em}2}^{n1}n1`$. Two vertices $`\{A,B\}`$ and $`\{A^{},B^{}\}`$ are connected by an edge in $`𝐓_n`$ if and only if

$$AA^{}\mathrm{or}AB^{}\mathrm{or}BA^{}\mathrm{or}BB^{}.$$
(4)
We now define $`𝐓_n`$ as the flag complex with this graph. Equivalently, a subset $`\sigma \mathrm{Vert}(𝐓_n)`$ is a face of $`𝐓_n`$ if any pair $`\{\{A,B\},\{A^{},B^{}\}\}\sigma `$ satisfies (4).

The simplicial complex $`𝐓_n`$ was first introduced by Buneman (see \[3, §5.1.4\]) and was studied more recently by Robinson-Whitehouse  and Vogtmann . These authors obtained the following results. Each face $`\sigma `$ of $`𝐓_n`$ corresponds to a semi-labeled tree with leaves $`1,2,\mathrm{},n`$. Here each internal node is unlabeled and has at least three neighbors. Each internal edge of such a tree defines a partition $`\{A,B\}`$ of the set of leaves $`\{1,2,\mathrm{},n\}`$, and we encode the tree by the set of partitions representing its internal edges. The facets (= maximal faces) of $`𝐓_n`$ correspond to *trivalent trees*, that is, semi-labeled trees whose internal nodes all have three neighbors. All facets of $`𝐓_n`$ have the same cardinality $`n3`$, the number of internal edges of any trivalent tree. Hence $`𝐓_n`$ is pure of dimension $`n4`$. The number of facets (i.e. trivalent semi-labeled trees on $`\{1,2,\mathrm{},n\}`$) is the *Schröder number*

$$(2n5)!!=(2n5)\times (2n7)\times \mathrm{}\times 5\times 3\times 1.$$
(5)
It is proved in  and  that $`𝐓_n`$ has the homotopy type of a bouquet of $`(n2)!`$ spheres of dimension $`n4`$. The two smallest cases $`n=4`$ and $`n=5`$ are discussed in Examples 3.2 and 3.3. Here is a description of the next case:

###### Example 4.1.

$`(n=6)`$ The two-dimensional simplicial complex $`𝐓_6`$ has $`25`$ vertices, $`105`$ edges and $`105`$ triangles, each coming in two symmetry classes:

$`15\text{ vertices like }\{12,3456\},10\text{ vertices like }\{123,456\},`$
$`60\text{ edges like }\{\{12,3456\},\{123,456\}\},`$
$`45\text{ edges like }\{\{12,3456\},\{1234,56\}\},`$
$`90\text{ triangles like }\{\{12,3456\},\{123,456\},\{1234,56\}\},`$
$`15\text{ triangles like }\{\{12,3456\}\},\{34,1256\}\},\{56,1234\}\}.`$
Each edge lies in three triangles, corresponding to restructuring subtrees. ∎

We next describe an embedding of $`𝐓_n`$ as a simplicial fan into the $`\frac{1}{2}n(n3)`$-dimensional vector space $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}/\mathrm{image}(\varphi )`$. For each trivalent tree $`\sigma `$ we first define a cone $`B_\sigma `$ in $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$ as follows. By a *realization* of a semi-labeled tree $`\sigma `$ we mean a one-dimensional cell complex in some Euclidean space whose underlying graph is a tree isomorphic to $`\sigma `$. Such a realization of $`\sigma `$ is a metric space on $`\{1,2,\mathrm{},n\}`$. The *distance* between $`i`$ and $`j`$ is the length of the unique path between leaf $`i`$ and leaf $`j`$ in that realization. Then we set

$`B_\sigma =`$ $`\{(w_{12},w_{13},\mathrm{},w_{n1,n})^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}:w_{ij}\text{ is the distance from}`$
$`\text{leaf }i\text{ to leaf }j\text{ in some realization of }\sigma \}+\mathrm{image}(\varphi ).`$
Let $`C_\sigma `$ denote the image of $`B_\sigma `$ in the quotient space $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}/\mathrm{image}(\varphi )`$. Passing to this quotient has the geometric meaning that two trees are identified if their only difference is in the lengths of the $`n`$ edges adjacent to the leaves.

###### Theorem 4.2.

The closure $`\overline{C}_\sigma `$ is a simplicial cone of dimension $`|\sigma |`$ with relative interior $`C_\sigma `$. The collection of all cones $`\overline{C}_\sigma `$, as $`\sigma `$ runs over $`𝐓_n`$, is a simplicial fan. It is isometric to the Billera-Holmes-Vogtmann space of trees.

###### Proof.

Realizations of semi-labeled trees are characterized by the *four point condition* (e.g. \[3, Theorem 2.1\], ). This condition states that for any quadruple of leaves $`i,j,k,l`$ there exists a unique relabeling such that

$$w_{ij}+w_{kl}=w_{ik}+w_{jl}w_{il}+w_{jk}.$$
(6)
Given any tree $`\sigma `$, this gives a system of $`\left(\genfrac{}{}{0pt}{}{n}{4}\right)`$ linear equations and $`\left(\genfrac{}{}{0pt}{}{n}{4}\right)`$ linear inequalities. The solution set of this linear system is precisely the closure $`\overline{B}_\sigma `$ of the cone $`B_\sigma `$ in $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$. This follows from the *Additive Linkage Algorithm*  which reconstructs the combinatorial tree $`\sigma `$ from any point $`w`$ in $`B_\sigma `$.

All of our cones share a common linear subspace, namely,

$$\overline{B}_\sigma \overline{B}_\sigma =\mathrm{image}(\varphi ).$$
(7)
This is seen by replacing the inequalities in (6) by equalities. The cone $`\overline{B}_\sigma `$ is the direct sum (8) of this linear space with a $`|\sigma |`$-dimensional simplicial cone. Let $`\{e_{ij}:\mathrm{\hspace{0.17em}1}i<jn\}`$ denote the standard basis of $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$. Adopting the convention $`e_{ji}=e_{ij}`$, for any partition $`\{A,B\}`$ of $`\{1,2,\mathrm{},n\}`$ we define

$$E_{A,B}=\underset{iA}{}\underset{jB}{}e_{ij}.$$

These vectors give the generators of our cone as follows:

$$\overline{B}_\sigma =\mathrm{image}(\varphi )+_0\{E_{A,B}:\{A,B\}\sigma \}.$$
(8)
From the two presentations (6) and (8) it follows that

$$\overline{B}_\sigma \overline{B}_\tau =\overline{B}_{\sigma \tau }\text{for all}\sigma ,\tau 𝐓_n.$$
(9)
Therefore the cones $`B_\sigma `$ form a fan in $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}`$, and this fan has face poset $`𝐓_n`$. It follows from (8) that the quotient $`\overline{C}_\sigma =\overline{B}_\sigma /\mathrm{image}(\varphi )`$ is a pointed cone.

We get the desired conclusion for the cones $`\overline{C}_\sigma `$ by taking quotients modulo the common linear subspace (7). The resulting fan in $`^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}/\mathrm{image}(\varphi )`$ is simplicial of pure dimension $`n3`$ and has face poset $`𝐓_n`$. It is isometric to the Billera-Holmes-Vogtmann space in  because their metric is flat on each cone $`\overline{C_\sigma }_0^{|\sigma |}`$ and extended by the gluing relations $`\overline{C}_\sigma \overline{C}_\tau =\overline{C}_{\sigma \tau }`$. ∎

We now turn to the tropical Grassmannian and prove our first main result. We shall identify the simplicial complex $`𝐓_n`$ with the fan in Theorem 4.2.

Proof of Theorem 3.4:  The Plücker ideal $`I_{2,n}`$ is generated by the $`\left(\genfrac{}{}{0pt}{}{n}{4}\right)`$ quadrics

$$p_{ij}p_{kl}p_{ik}p_{jl}+p_{il}p_{jk}\text{for}\mathrm{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}1}i<j<k<ln.$$

The tropicalization of this polynomial is the disjunction of linear systems

$`w_{ij}+w_{kl}=w_{ik}+w_{jl}w_{il}+w_{jk}`$
$`\mathrm{or}`$ $`w_{ij}+w_{kl}=w_{il}+w_{jk}w_{ik}+w_{jl}`$
$`\mathrm{or}`$ $`w_{ik}+w_{jl}=w_{il}+w_{jk}w_{ij}+w_{kl}.`$
Every point $`w`$ on the tropical Grassmannian $`𝒢_{2,n}`$ satisfies this for all quadruples $`i,j,k,l`$, that is, it satisfies the four point condition (6). The Additive Linkage Algorithm reconstructs the unique semi-labeled tree $`\sigma `$ with $`wC_\sigma `$. This proves that every relatively open cone of $`𝒢_{2,n}`$ lies in the relative interior of a unique cone $`C_\sigma `$ of the fan $`𝐓_n`$ in Theorem 4.2.

We need to prove that the fans $`𝐓_n`$ and $`𝒢_{2,n}`$ are equal. Equivalently, every cone $`C_\sigma `$ is actually a cone in the Gröbner fan. This will be accomplished by analyzing the corresponding initial ideal. In view of (9), it suffices to consider maximal faces $`\sigma `$ of $`𝐓_n`$. Fix a trivalent tree $`\sigma `$ and a weight vector $`wC_\sigma `$. Then, for every quadruple $`i,j,k,l`$, the inequality in (6) is strict. This means combinatorially that $`\{\{i,l\},\{j,k\}\}`$ is a four-leaf subtree of $`\sigma `$.

Let $`J_\sigma `$ denote the ideal by the quadratic binomials $`p_{ij}p_{kl}p_{ik}p_{jl}`$ corresponding to all four-leaf subtrees of $`\sigma `$. Our discussion shows that $`J_\sigma \mathrm{in}_w(I_{2,n})`$. The proof will be complete by showing that the two ideals agree:

$`J_\sigma =\mathrm{in}_w(I_{2,n}).`$ (10)
This identity will be proved by showing that the two ideals have a common initial monomial ideal, generated by square-free quadratic monomials.

We may assume, without loss of generality, that $`w`$ is a strictly positive vector, corresponding to a planar realization of the tree $`\sigma `$ in which the leaves $`1,2,\mathrm{},n`$ are arranged in circular order to form a convex $`n`$-gon (Figure 1).

Let $`M`$ be the ideal generated by the monomials $`p_{ik}p_{jl}`$ for $`1i<j<k<ln`$. These are the crossing pairs of edges in the $`n`$-gon. By a classical construction of invariant theory, known as *Kempe’s circular straightening law* (see \[12, Theorem 3.7.3\]), there exists a term order $`_{\mathrm{circ}}`$ on $`[p]`$ such that

$$M=\mathrm{in}_{_{\mathrm{circ}}}(I_{2,n}).$$
(11)
Now, by our circular choice $`w`$ of realization of the tree $`\sigma `$, the crossing monomials $`p_{ik}p_{jl}`$ appear as terms in the binomial generators of $`J_\sigma `$. Moreover, the term order $`_{\mathrm{circ}}`$ on $`[p]`$ refines the weight vector $`w`$. This implies

$$\mathrm{in}_{_{\mathrm{circ}}}(\mathrm{in}_w(I_{2,n}))=\mathrm{in}_{_{\mathrm{circ}}}(I_{2,n})=M\mathrm{in}_{_{\mathrm{circ}}}(J_\sigma ).$$
(12)
Using $`J_\sigma \mathrm{in}_w(I_{2,n})`$ we conclude that equality holds in (12) and in (10). ∎

The simplicial complex $`\mathrm{\Delta }(M)`$ represented by the squarefree monomial ideal $`M`$ is an iterated cone over the boundary of the polar dual of the *associahedron*; see \[12, page 132\]. The facets of $`\mathrm{\Delta }(M)`$ are the triangulations of the $`n`$-gon. Their number is the common degree of the ideals $`I_{2,n}`$, $`J_\sigma `$ and $`M`$:

$$\text{the }(n2)^{\mathrm{nd}}\text{ Catalan number}=\frac{1}{n1}\left(\genfrac{}{}{0pt}{}{2n4}{n2}\right).$$

The reduced Gröbner basis of (11) has come to recent prominence as a key example in the Fomin-Zelevinsky theory of *cluster algebras* . Note also:

###### Corollary 4.3.

There exists a maximal cone in the Gröbner fan of the Plücker ideal $`I_{2,n}`$ which contains, up to symmetry, all cones of $`𝒢_{2,n}`$.

###### Proof.

The cone corresponding to the initial ideal (11) has this property. ∎

###### Corollary 4.4.

Every initial binomial ideal of $`I_{2,n}`$ is a prime ideal.

###### Proof.

If $`\mathrm{in}_w(I_{2,n})`$ is a binomial ideal then $`w`$ must satisfy the four point conditions (6) with strict inequalities. Hence $`\mathrm{in}_w(I_{2,n})=J_\sigma `$ for some semi-labeled trivalent tree $`\sigma `$. The ideal $`J_\sigma `$ is radical and equidimensional because its initial ideal $`M=\mathrm{in}_{_{\mathrm{circ}}}(J_\sigma )`$ is radical and equidimensional (unmixed).

To show that $`J_\sigma `$ is prime, we proceed as follows. For each edge $`e`$ of the tree $`\sigma `$ we introduce an indeterminate $`y_e`$. Consider the polynomial ring

$$[y]=[y_e:e\text{edge of}\sigma ].$$

Let $`\psi `$ denote the homomorphism $`[p][y]`$ which sends $`p_{ij}`$ to the product of all indeterminates $`y_e`$ corresponding to edges on the unique path between leaf $`i`$ and leaf $`j`$. We claim that $`\mathrm{kernel}(\psi )=J_\sigma `$.

A direct combinatorial argument shows that the convex polytope corresponding to the toric ideal $`\mathrm{kernel}(\psi )`$ has a canonical triangulation into $`\frac{1}{n1}\left(\genfrac{}{}{0pt}{}{2n4}{n2}\right)`$ unit simplices (namely, $`\mathrm{\Delta }(M)`$). Hence $`\mathrm{kernel}(\psi )`$ and $`J_\sigma `$ are both unmixed of the same dimension and the same degree. Since $`\mathrm{kernel}(\psi )`$ is obviously contained in $`J_\sigma `$, it follows that the two ideals are equal. ∎

###### Corollary 4.5.

The tropical Grassmannian $`𝒢_{2,n}`$ is characteristic-free.

This means that we can consider the Plücker ideal $`I_{2,n}`$ in the polynomial ring $`K[p]`$ over any ground field $`K`$ when computing its tropical variety. All generators $`p_{ij}p_{kl}p_{ik}p_{jl}`$ of the initial binomial ideals $`J_\sigma `$ have coefficients $`+1`$ and $`1`$, so $`J_\sigma k`$ contains no monomial in $`k[p]`$, even if $`\mathrm{char}(k)>0`$.

## 5 The Grassmannian of 3-planes in 6-space

In this section we study the case $`d=3`$ and $`n=6`$. The Plücker ideal $`I_{3,6}`$ is minimally generated by $`35`$ quadrics in the polynomial ring in $`20`$ variables,

$$[p]=[p_{123},p_{124},\mathrm{},p_{456}].$$

We are interested in the $`10`$-dimensional fan $`𝒢_{3,6}`$ which consists of all vectors $`w^{20}`$ such that $`\mathrm{in}_w(I_{3,6})`$ is monomial-free. The four-dimensional quotient fan $`𝒢_{3,6}^{\prime \prime }`$ sits in $`^{20}/\mathrm{image}(\varphi )^{14}`$ and is a fan over the three-dimensional polyhedral complex $`𝒢_{3,6}^{\prime \prime \prime }`$. Our aim is to prove Theorem 3.6, which states that $`𝒢_{3,6}^{\prime \prime \prime }`$ consists of $`65`$ vertices, $`550`$ edges, $`1395`$ triangles and $`1035`$ tetrahedra.

We begin by listing the vertices. Let $`E`$ denote the set of $`20`$ standard basis vectors $`e_{ijk}`$ in $`^{\left(\genfrac{}{}{0pt}{}{6}{3}\right)}`$. For each $`4`$-subset $`\{i,j,k,l\}`$ of $`\{1,2,\mathrm{},6\}`$ we set

$$f_{ijkl}=e_{ijk}+e_{ijl}+e_{ikl}+e_{jkl}.$$

Let $`F`$ denote the set of these $`15`$ vectors. Finally consider any of the $`15`$ *tripartitions* $`\{\{i_1,i_2\},\{i_3,i_4\},\{i_5,i_6\}\}`$ of $`\{1,2,\mathrm{},6\}`$ and define the vectors

$`g_{i_1i_2i_3i_4i_5i_6}:=f_{i_1i_2i_3i_4}+e_{i_3i_4i_5}+e_{i_3i_4i_6}`$
and $`g_{i_1i_2i_5i_6i_3i_4}:=f_{i_1i_2i_5i_6}+e_{i_3i_5i_6}+e_{i_4i_5i_6}.`$
This gives us another set $`G`$ of $`30`$ vectors. All $`65`$ vectors in $`EFG`$ are regarded as elements of the quotient space $`^{\left(\genfrac{}{}{0pt}{}{6}{3}\right)}/\mathrm{image}(\varphi )^{14}`$. Note that

$$g_{i_1i_2i_3i_4i_5i_6}=g_{i_3i_4i_5i_6i_1i_2}=g_{i_5i_6i_1i_2i_3i_4}.$$

Later on, the following identity will turn out to be important in the proof of Theorem 5.4:

$$g_{i_1i_2i_3i_4i_5i_6}+g_{i_1i_2i_5i_6i_3i_4}=f_{i_1i_2i_3i_4}+f_{i_1i_2i_5i_6}+f_{i_3i_4i_5i_6}.$$
(13)
Lemma 5.1 and other results in this section were found by computation.

###### Lemma 5.1.

The set of vertices of $`𝒢_{3,6}`$ equals $`EFG`$.

We next describe all the $`550`$ edges of the tropical Grassmannian $`𝒢_{3,6}`$.

* There are $`90`$ edges like $`\{e_{123},e_{145}\}`$ and $`10`$ edges like $`\{e_{123},e_{456}\}`$, for a total of $`100`$ edges connecting pairs of vertices both of which are in $`E`$. (By the word “like”, we will always mean “in the $`S_6`$ orbit of, where $`S_6`$ permutes the indices $`\{1,2,\mathrm{}6\}`$.)
* This class consists of $`45`$ edges like $`\{f_{1234},f_{1256}\}`$.
* Each of the $`15`$ tripartitions gives exactly one edge, like $`\{g_{123456},g_{125634}\}`$.
* There are $`60`$ edges like $`\{e_{123},f_{1234}\}`$ and $`60`$ edges like $`\{e_{123},f_{1456}\}`$, for a total of $`120`$ edges connecting a vertex in $`E`$ to a vertex in $`F`$.
* This class consists of $`180`$ edges like $`\{e_{123},g_{123456}\}`$. The intersections of the index triple of the $`e`$ vertex with the three index pairs of the $`g`$ vertex must have cardinalities $`(2,1,0)`$ *in this cyclic order*.
* This class consists of $`90`$ edges like $`\{f_{1234},g_{123456}\}`$.

###### Lemma 5.2.

The $`1`$-skeleton of $`𝒢_{3,6}^{\prime \prime \prime }`$ is the graph with the $`550`$ edges above.

Let $`\mathrm{\Delta }`$ denote the *flag complex* specified by the graph in the previous lemma. Thus $`\mathrm{\Delta }`$ is the simplicial complex on $`EFG`$ whose faces are subsets $`\sigma `$ with the property that each $`2`$-element subset of $`\sigma `$ is one of the $`550`$ edges. We will see that $`𝒢_{3,6}`$ is a subcomplex homotopy equivalent to $`\mathrm{\Delta }`$.

###### Lemma 5.3.

The flag complex $`\mathrm{\Delta }`$ has $`1,410`$ triangles, $`1,065`$ tetrahedra, $`15`$ four-dimensional simplices, and it has no faces of dimension five or more.

The facets of $`\mathrm{\Delta }`$ are grouped into seven symmetry classes:

Facet FFFGG: There are $`15`$ four-dimensional simplices, one for each partition of $`\{1,\mathrm{},6\}`$ into three pairs. An example of such a tripartition is $`\{\{1,2\},\{3,4\},\{5,6\}\}`$. It gives the facet $`\{f_{1234},f_{1256},f_{3456},g_{123456},g_{125634}\}`$. The $`75`$ tetrahedra contained in these $`15`$ four-simplices are not facets of $`\mathrm{\Delta }`$.

The remaining $`990`$ tetrahedra in $`\mathrm{\Delta }`$ are facets and they come in six classes:

Facet EEEE: There are $`30`$ tetrahedra like $`\{e_{123},e_{145},e_{246},e_{356}\}`$.

Facet EEFF1: There are $`90`$ tetrahedra like $`\{e_{123},e_{456},f_{1234},f_{3456}\}`$.

Facet EEFF2: There are $`90`$ tetrahedra like $`\{e_{125},e_{345},f_{3456},f_{1256}\}`$.

Facet EFFG: There are $`180`$ tetrahedra like $`\{e_{345},f_{1256},f_{3456},g_{123456}\}`$.

Facet EEEG: There are $`240`$ tetrahedra like $`\{e_{126},e_{134},e_{356},g_{125634}\}`$.

Facet EEFG:  There are $`360`$ tetrahedra like $`\{e_{234},e_{125},f_{1256},g_{125634}\}`$.

While $`\mathrm{\Delta }`$ is an abstract simplicial complex on the vertices of $`𝒢_{3,6}^{\prime \prime \prime }`$, it is not embedded as a simplicial complex because relation (13) shows that the five vertices of the four dimensional simplices only span three dimensional space. Specifically, they form a bipyramid with the F-vertices as the base and the G-vertices as the two cone points.

We now modify the flag complex $`\mathrm{\Delta }`$ to a new simplicial complex $`\mathrm{\Delta }^{}`$ which has pure dimension three and reflects the situation described in the last paragraph. The complex $`\mathrm{\Delta }^{}`$ is obtained from $`\mathrm{\Delta }`$ by removing the $`15`$ FFF-triangles $`\{f_{1234},f_{1256},f_{3456}\}`$, along with the $`30`$ tetrahedra FFFG and the $`15`$ four-dimensional facets FFFGG containing the FFF-triangles. In $`\mathrm{\Delta }^{}`$, the bipyramids are each divided into three tetrahedra arranged around the GG-edges. The following theorem implies both Theorem 3.6 and Corollary 3.7.

###### Theorem 5.4.

The tropical Grassmannian $`𝒢_{3,6}^{\prime \prime \prime }`$ equals the simplicial complex $`\mathrm{\Delta }^{}`$. It is not a flag complex because of the $`15`$ missing FFF-triangles. The homology of $`𝒢_{3,6}^{\prime \prime \prime }`$ is concentrated in (top) dimension 3; $`H_3(𝒢_{3,6}^{\prime \prime \prime },)=^{126}`$.

The integral homology groups were computed independently by Michael Joswig and Volkmer Welker. We are grateful for their help.

This theorem is proved by an explicit computation. The correctness of the result can be verified by the following method. One first checks that the seven types of cones described above are indeed Gröbner cones of $`I_{3,6}`$ whose initial ideals are monomial-free. Next one checks that the list is complete. This relies on a result in  which guarantees that $`𝒢_{3,6}`$ is connected in codimension $`1`$. The completeness check is done by computing the link of each of the known classes of triangles. Algebraically, this amounts to computing the (truly zero-dimensional) tropical variety of $`\mathrm{in}_w(I_{3,6})`$ where $`w`$ is any point in the relative interior of the triangular cone in question. For all but one class of triangles the link consists of three points, and each neighboring $`3`$-cell is found to be already among our seven classes. The links of the triangles are as follows:

Triangle EEE:  The link of $`\{e_{146},e_{256},e_{345}\}`$ consists of $`e_{123}`$, $`g_{163425}`$, $`g_{142635}`$.

Triangle EEF: The link of $`\{e_{256},e_{346},f_{1346}\}`$ consists of $`f_{1256}`$, $`g_{132546}`$, $`g_{142536}`$.

Triangle EEG:  The link of $`\{e_{156},e_{236},g_{142356}\}`$ consists of $`e_{124}`$, $`e_{134}`$, $`f_{1456}`$.

Triangle EFF:  The link of $`\{e_{135},f_{1345},f_{2346}\}`$ consists of $`e_{236}`$, $`e_{246}`$, $`g_{153426}`$.

Triangle EFG:  The link of $`\{e_{235},f_{2356},g_{143526}\}`$ consists of $`e_{145}`$, $`f_{1246}`$, $`e_{134}`$.

Triangle FFG:  The link of $`\{f_{1236},f_{1345},g_{134526}\}`$ consists of $`e_{126}`$, $`e_{236}`$, $`g_{132645}`$.

Triangle FGG:  The link of $`\{f_{1456},g_{142356},g_{145623}\}`$ consists of $`f_{2356}`$ and $`f_{1234}`$.

The FGG triangle lies in the interior of our bipyramid FFFGG and is incident to two of the three FFGG tetrahedra which make up the triangulation of that bipyramid. It is not contained in any other facet of $`𝒢_{3,6}^{\prime \prime \prime }`$.

The $`15`$ bipyramids are responsible for various counterexamples regarding $`𝒢_{3,6}`$. This includes the failure of Corollaries 3.5 and 4.4 to hold for $`d3`$.

###### Proposition 5.5.

Not every initial binomial ideal of $`I_{3,6}`$ is prime. More precisely, if $`w`$ is any vector in the relative interior of an FFGG cone then $`in_w(I_{3,6})`$ is the intersection of two distinct codimension $`10`$ primes in $`[p]`$.

###### Proof.

We may assume that $`w=f_{1256}+f_{3456}+g_{123456}+g_{125634}`$. Explicit computation (using \[13, Corollary 1.9\]) reveals that $`\mathrm{in}_w(I_{3,6})`$ is generated by

$`p_{124}p_{135}p_{123}p_{145},p_{123}p_{146}p_{124}p_{136},p_{125}p_{136}p_{126}p_{135},`$
$`p_{125}p_{146}p_{126}p_{145},p_{135}p_{146}p_{136}p_{145},p_{123}p_{245}p_{124}p_{235},`$
$`p_{123}p_{246}p_{124}p_{236},p_{126}p_{235}p_{125}p_{236},p_{125}p_{246}p_{126}p_{245},`$
$`p_{134}p_{235}p_{135}p_{234},p_{136}p_{234}p_{134}p_{236},p_{136}p_{235}p_{135}p_{236},`$
$`p_{134}p_{245}p_{145}p_{234},p_{134}p_{246}p_{146}p_{234},p_{146}p_{245}p_{145}p_{246},`$
$`p_{135}p_{346}p_{136}p_{345},p_{146}p_{345}p_{145}p_{346},p_{135}p_{245}p_{145}p_{235},`$
$`p_{135}p_{256}p_{156}p_{235},p_{156}p_{245}p_{145}p_{256},p_{135}p_{456}p_{145}p_{356},`$
$`p_{136}p_{246}p_{146}p_{236},p_{136}p_{256}p_{156}p_{236},p_{146}p_{256}p_{156}p_{246},`$
$`p_{136}p_{456}p_{146}p_{356},p_{235}p_{246}p_{236}p_{245},p_{235}p_{346}p_{236}p_{345},`$
$`p_{245}p_{346}p_{246}p_{345},p_{235}p_{456}p_{245}p_{356},p_{246}p_{356}p_{236}p_{456},`$
$`p_{136}p_{245}p_{135}p_{246},p_{145}p_{236}p_{135}p_{246},p_{146}p_{235}p_{135}p_{246},`$
$`p_{123}p_{456}p_{124}p_{356}\text{and}p_{134}p_{256}p_{156}p_{234}.`$
The ideal $`\mathrm{in}_w(I_{3,6})`$ is the intersection of the two codimension $`10`$ primes

$`P=\mathrm{in}_w(I_{3,6})+`$ $`p_{125}p_{346}p_{126}p_{345}\mathrm{and}`$
$`Q=\mathrm{in}_w(I_{3,6})+`$ $`p_{135},p_{136},p_{145},p_{146},p_{235},p_{236},p_{245},p_{246}.`$
The degrees of the ideals $`P`$, $`Q`$ and $`I_{3,6}`$ are $`\mathrm{\hspace{0.17em}38}`$, $`4`$ and $`42`$ respectively. ∎

We close this section with one more counterexample arising from the triangulated bipyramid in $`𝒢_{3,6}^{\prime \prime \prime }`$. It was proved in  that the $`d\times d`$-minors of a generic $`d\times n`$-matrix form a *universal Gröbner basis*. A question left open in that paper is whether the maximal minors also form a *universal sagbi basis*. It is well-known that they form a sagbi basis for a specific term order. See \[13, Theorem 11.8\] and the discussion in Section 6 below. The question was whether the sagbi basis property holds for all other term orders. We show that the answer is “no”: the maximal minors are not a universal sagbi basis.

###### Corollary 5.6.

There exists a term order on $`18`$ variables such that the $`3\times 3`$-minors of a generic $`3\times 6`$-matrix are not a sagbi basis in this term order.

###### Proof.

Consider the $`3\times 6`$-matrix in \[15, Example 1.8 and Proposition 3.13\]:

$$W=\left(\begin{array}{cccccc}2& 1& 2& 1& 0& 0\\ 1& 2& 0& 0& 2& 1\\ 0& 0& 1& 2& 1& 2\end{array}\right)$$

Let $`w^{\left(\genfrac{}{}{0pt}{}{6}{3}\right)}`$ be its vector of *tropical $`3\times 3`$-minors*. The coordinates of $`w`$ are

$`w_{ijk}=`$ $`\mathrm{min}\{W_{1i}+W_{2j}+W_{3k},W_{1i}+W_{3j}+W_{2k},W_{2i}+W_{1j}+W_{3k},`$
$`W_{2i}+W_{3j}+W_{1k},W_{3i}+W_{1j}+W_{2k},W_{3i}+W_{2j}+W_{1k}\}.`$
This vector represents the centroid of our bipyramid: $`w=g_{123456}+g_{125634}`$. We consider the $`3\times 3`$-minors of the following matrix of indeterminates:

$$\left(\begin{array}{cccccc}x_1& x_2& x_3& x_4& x_5& x_6\\ y_1& y_2& y_3& y_4& y_5& y_6\\ z_1& z_2& z_3& z_4& z_5& z_6\end{array}\right)$$
(14)
The initial forms of its $`3\times 3`$-minors with respect to the weights $`W`$ are

$`p_{123}=z_1x_2y_3,p_{124}=z_1x_2y_4,p_{125}=y_1z_2x_5,p_{126}=y_1z_2x_6,`$
$`p_{134}=z_1y_3x_4,p_{135}=z_1y_3x_5,p_{136}=z_1y_3x_6,p_{145}=z_1y_4x_5,`$
$`p_{146}=z_1y_4x_6,p_{156}=z_1x_5y_6,p_{234}=z_2y_3x_4,p_{235}=z_2y_3x_5,`$
$`p_{236}=z_2y_3x_6,p_{245}=z_2y_4x_5,p_{246}=z_2y_4x_6,p_{256}=z_2x_5y_6,`$
$`p_{345}=z_3y_4x_5,p_{346}=z_3y_4x_6,p_{356}=y_3z_5x_6,p_{456}=y_4z_5x_6.`$
Fix any term order $``$ which refines $`W`$. The criterion in \[13, §11\] will show that the $`3\times 3`$-minors are not a sagbi basis with respect to $``$. The toric ideal of algebraic relations on the twenty monomials above is precisely the prime $`P`$ in the proof of Proposition 5.5. The ideal $`P`$ strictly contains $`\mathrm{in}_w(I_{3,6})`$. Both have codimension $`10`$ but their degrees differ by $`4`$. Using \[13, Theorem 11.4\] we conclude that the $`3\times 3`$-minors are not a sagbi basis for $``$. ∎

## 6 Tropical Planes

The Grassmannian $`G_{d,n}`$ is the parameter space for all $`d`$-dimensional linear planes in $`K^n`$. We now prove the analogous statement in tropical geometry (Theorem 3.8). But there are also crucial differences between the classical planes and tropical planes. For instance, most tropical planes are not complete intersections of tropical hyperplanes (see Example 6.2 and Proposition 6.3). Our combinatorial theory of tropical $`d`$-planes is a direct generalization of the Buneman representation of trees (the $`d=2`$ case) and thus offers mathematical tools for possible future applications in phylogenetic analysis.

Proof of Theorem 3.8.  The tropical Grassmannian $`𝒢_{d,n}^{}`$ is a fan of dimension $`(nd)d`$ in $`^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}/(1,1,\mathrm{},1)^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)1}`$. We begin by describing the map which takes a point $`w`$ in $`𝒢_{d,n}^{}`$ to the associated tropical $`d`$-plane $`L_w^n`$. Given $`w`$, we consider the tropical polynomials

$$F_J(x_1,\mathrm{},x_n)=\underset{jJ}{}w_{J\{j\}}x_j,$$
(15)
where $`J`$ runs over all subsets of cardinality $`d+1`$ in $`[n]`$. We define $`L_w`$ as the subset of $`^n`$ which is the intersection of the $`\left(\genfrac{}{}{0pt}{}{n}{d+1}\right)`$ tropical hypersurfaces $`𝒯(F_J)`$. We claim that $`L_w`$ is a tropical $`d`$-plane. Pick a point $`\xi (K^{})^{\left(\genfrac{}{}{0pt}{}{n}{d}\right)}`$ which is a zero of $`I_{d,n}`$ and satisfies $`w=\mathrm{deg}(\xi )`$. The $`d`$-plane $`X`$ represented by $`\xi `$ is cut out by the $`\left(\genfrac{}{}{0pt}{}{n}{d+1}\right)`$ linear equations derived from Cramer’s rule:

$$f_J(x_1,\mathrm{},x_n)=\underset{jJ}{}\pm \xi _{J\{j\}}x_j=0$$
(16)
The tropicalization of this linear form is the tropical polynomial in (15), in symbols, $`\mathrm{trop}(f_J)=F_J`$. It is known that the $`f_J`$ form a universal Gröbner basis for the ideal they generate \[13, Proposition 1.6\]. Therefore, Corollary 2.3 shows that $`L_w`$ is indeed a tropical $`d`$-plane. In fact, we have

$$\mathrm{deg}(X)=L_w=L_{\mathrm{deg}(\xi )}.$$

This proves that the map $`wL_w`$ surjects the tropical Grassmannian onto the set of all tropical $`d`$-planes, and it is the only such map which is compatible with the classical bijection between $`G_{d,n}`$ and the set of $`d`$-planes in $`K^n`$.

It remains to be shown that the map $`wL_w`$ is injective. We do this by constructing the inverse map. Suppose we are given $`L_w`$ as a subset of $`^n`$. We need to reconstruct the coordinates $`w_{i_1\mathrm{}i_d}`$ of $`w`$ up to a global additive constant. Equivalently, for any $`(d1)`$-subset $`I`$ of $`[n]`$ and any pair $`j,k[n]\backslash I`$, we need to reconstruct the real number $`w_{I\{j\}}w_{I\{k\}}`$.

Fix a very large positive rational number $`M`$ and consider the $`(nd+1)`$-dimensional plane defined by $`x_i=M`$ for $`iI`$. The intersection of this plane with $`L_w`$ contains at least one point $`x^n`$, and this point can be chosen to satisfy $`x_jM`$ for all $`j[n]\backslash I`$. This can be seen by solving the $`d1`$ equations $`x_i=t^M`$ on any $`d`$-plane $`XK^n`$ which tropicalizes to $`L_w`$.

Now consider the tropical polynomial (15) with $`J=I\{j,k\}`$. Since $`x`$ lies $`𝒯(F_J)`$, and since $`\mathrm{max}(x_j,x_k)M=x_i`$ for all $`iI`$, we conclude

$$w_{J\backslash \{k\}}+x_k=w_{J\backslash \{j\}}+x_j.$$

This shows that the desired differences can be read off from the point $`x`$:

$$w_{I\{j\}}w_{I\{k\}}=x_jx_k.$$
(17)
We thus reconstruct $`w𝒢_{d,n}`$ by locating $`\left(\genfrac{}{}{0pt}{}{n}{d1}\right)`$ special points on $`L_w`$. ∎

The above proof offers an (inefficient) algorithm for computing the map $`wL_w`$, namely, by intersecting all $`\left(\genfrac{}{}{0pt}{}{n}{d+1}\right)`$ tropical hypersurfaces $`𝒯(F_J)`$. Consider the case $`d=2`$. Here the $`\left(\genfrac{}{}{0pt}{}{n}{3}\right)`$ tropical polynomials $`F_J`$ in (15) are

$$F_{ijk}=w_{ij}x_k+w_{ik}x_j+w_{jk}x_i.$$

The tropical hypersurface $`𝒯(F_{ijk})`$ is the solution set to the linear system

$`w_{ij}+x_k=w_{ik}+x_jw_{jk}+x_i`$
or $`w_{ij}+x_k=w_{jk}+x_iw_{ik}+x_j`$
or $`w_{ij}+x_k=w_{jk}+x_iw_{ik}+x_j.`$
The conjunction of these $`\left(\genfrac{}{}{0pt}{}{n}{3}\right)`$ linear systems can be solved efficiently by a variant of the tree reconstruction algorithm in . If $`r`$ and $`s^n/(1,\mathrm{},1)`$ are vertices of this tree connected by an edge $`e`$ then $`r=s+c_{iS}e_i`$ for some $`c>o`$ where $`S[n]`$ is the set of leaves on the $`s`$ side of $`e`$. We regard the tree as a metric space by assigning the length $`c`$ to edge $`e`$. The length of each edge is measured in lattice distance, so we get the tree with metric $`2w`$.

###### Corollary 6.1.

Let $`w`$ be a point in $`𝒢_{2,n}`$ which lies in the cone $`C_\sigma `$ for some tree $`\sigma `$. The image of $`L_w`$ in $`^n/(1,\mathrm{},1)`$ is a tree of combinatorial type $`\sigma `$.

The bijection $`wL_w`$ of Theorem 3.8 is a higher-dimensional generalization of recovering a phylogenetic tree from pairwise distances among $`n`$ leaves. For instance, for $`d=3`$ we can think of $`w`$ as data giving a proximity measure for any triple among $`n`$ “leaves”. The image of $`L_w`$ in $`^n/(1,\mathrm{},1)`$ is a “phylogenetic surface” which is a geometric representation of such data.

The tropical Grassmannians $`𝒢_{d,n}`$ and $`𝒢_{nd,n}`$ are isomorphic because the ideals $`I_{d,n}`$ and $`I_{nd,n}`$ are the same after signed complementation of Plücker coordinates. Theorem 3.8 allows us to define the *dual* $`(nd)`$-plane $`L^{}`$ of a tropical $`d`$-plane $`L`$ in $`^n`$. If $`L=L_w`$ then $`L^{}=L_w^{}`$ where $`w^{}`$ is the vector whose $`([n]\backslash I)`$-coordinate is the $`I`$-coordinate of $`w`$, for all $`d`$-subsets $`I`$ of $`[n]`$. One can check that a tropical hyperplane $`a_ix_i=0`$ contains $`L^{}`$ iff $`(a_i)L_w`$ and that $`(L^{})^{}=L`$.

###### Example 6.2.

Let $`w=e_{12}+e_{34}+e_{56}`$ in $`^{\left(\genfrac{}{}{0pt}{}{6}{2}\right)}`$. Then $`L_w`$ is a tropical $`2`$-plane in $`^6`$. Its image in $`^6/(1,\mathrm{},1)`$ is a tree as in Figure 1, of type $`\sigma =\{\{12,3456\},\{34,1256\},\{56,1234\}\}`$. The Plücker vector dual to $`w`$ is

$$w^{}=e_{3456}+e_{1256}+e_{1234}𝒢_{4,6}^{\left(\genfrac{}{}{0pt}{}{6}{4}\right)}.$$

We shall compute the tropical $`4`$-plane $`L_w^{}`$ by applying the algorithm in the proof of Theorem 3.8. There are $`6`$ tropical polynomials $`F_J`$ as in (15), namely,

$`F_{12345}=`$ $`0x_1+\mathrm{\hspace{0.17em}0}x_2+\mathrm{\hspace{0.17em}0}x_3+\mathrm{\hspace{0.17em}0}x_4+\mathrm{\hspace{0.17em}1}x_5`$
$`F_{12346}=`$ $`0x_1+\mathrm{\hspace{0.17em}0}x_2+\mathrm{\hspace{0.17em}0}x_3+\mathrm{\hspace{0.17em}0}x_4+\mathrm{\hspace{0.17em}1}x_6`$
$`F_{12356}=`$ $`0x_1+\mathrm{\hspace{0.17em}0}x_2+\mathrm{\hspace{0.17em}1}x_3+\mathrm{\hspace{0.17em}0}x_5+\mathrm{\hspace{0.17em}0}x_6`$
$`F_{12456}=`$ $`0x_1+\mathrm{\hspace{0.17em}0}x_2+\mathrm{\hspace{0.17em}1}x_4+\mathrm{\hspace{0.17em}0}x_5+\mathrm{\hspace{0.17em}0}x_6`$
$`F_{13456}=`$ $`1x_1+\mathrm{\hspace{0.17em}0}x_3+\mathrm{\hspace{0.17em}0}x_4+\mathrm{\hspace{0.17em}0}x_5+\mathrm{\hspace{0.17em}0}x_6`$
$`F_{23456}=`$ $`1x_2+\mathrm{\hspace{0.17em}0}x_3+\mathrm{\hspace{0.17em}0}x_4+\mathrm{\hspace{0.17em}0}x_5+\mathrm{\hspace{0.17em}0}x_6`$
The tropical $`4`$-plane $`L_w^{}`$ is the intersection of these six tropical hyperplanes:

$$𝒯(F_{12345})𝒯(F_{12346})𝒯(F_{12356})𝒯(F_{12456})𝒯(F_{13456})𝒯(F_{23456}).$$

We claim that $`L_w^{}`$ *is not a complete intersection*, i.e., there do no exist two tropical linear forms $`F`$ and $`F^{}`$ such that $`L_w^{}=𝒯(F)𝒯(F^{})`$. A tropical linear form $`F=a_1x_1+\mathrm{}+a_6x_6`$ vanishes on the dual $`4`$-plane $`L_w^{}`$ if and only if the point $`a=(a_1,\mathrm{},a_6)`$ lies in the $`2`$-plane $`L_w`$. There are $`9`$ types of such tropical linear forms $`F`$, one for each of the $`9`$ edges of the tree $`L_w`$. For instance, the bounded edge $`\{56,1234\}`$ represents the tropical forms

$$F=\alpha (x_1+x_2+x_3+x_4)+\beta (x_5+x_6)\text{where}\mathrm{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}0}<\alpha \beta .$$

By checking all pairs of the $`9`$ edges, we find that any conceivable intersection $`𝒯(F)𝒯(F^{})`$ must contain a $`5`$-dimensional cone like $`\{x_1+c=x_2x_3,x_4,x_5,x_6\}`$, $`\{x_3+c=x_4x_1,x_2,x_5,x_6\}`$ or $`\{x_5+c=x_6x_1,x_2,x_3,x_4\}`$.

This example can be generalized as follows.

###### Proposition 6.3.

Let $`L_w`$ be a tropical $`\mathrm{\hspace{0.17em}2}`$-plane in $`^n`$ whose tree is not combinatorially isomorphic to $`\sigma =\{\{1,\mathrm{},i\},\{i+1,\mathrm{},n\}:i=2,3,\mathrm{},n2\}`$. Then the dual tropical $`(n2)`$-plane $`L_w^{}`$ is not a complete intersection.

The special tree $`\sigma `$ in Proposition 6.3 is called the *caterpillar* in the phylogenetic literature (see Figure 2).

###### Proof.

Suppose for contradiction that $`L_w^{}`$ is the intersection of the hyperplanes $`a_ix_i=0`$ and $`b_ix_i=0`$. The vectors $`a=(a_1,\mathrm{},a_n)`$ and $`b=(b_1,\mathrm{},b_n)`$, regarded as elements of $`^n/(1,\mathrm{},1)`$, lie in the tree $`L_w`$. Denote by $`\gamma `$ the path through $`L_w`$ from $`a`$ to $`b`$. Since $`L_w`$ is not a caterpillar tree, the path $`\gamma `$ goes through fewer than $`n1`$ edges, so deleting those edges divides $`L`$ into fewer then $`n`$ connected components. Thus, there are two leafs of $`L`$, call them $`j`$ and $`k`$, such that the none of the edges of $`\gamma `$ separate $`j`$ from $`k`$. Every edge of $`\gamma `$ connects two points $`r`$ and $`s`$ with $`s=r+c_{iS}e_i`$ where, in each case, either $`j`$ and $`k`$ both lie in $`S`$ or neither do. Thus, $`a_ja_k=b_jb_k`$. Therefore, the intersection of the hyperplanes $`a_ix_i=0`$ and $`b_ix_i=0`$ contains every point $`(x_i)`$ with $`x_j+a_j=x_k+a_k`$ and $`x_ix_j`$ sufficiently positive for all $`ij,k`$. But this is a codimension one subset of $`^n/(1,\mathrm{},1)`$ and we know that $`L_w^{}`$ is pure of codimension two. ∎

Our next goal is to give a combinatorial encoding of tropical planes. The basic object in our combinatorial encoding is a $`d`$-partition $`\{A_1,\mathrm{},A_d\}`$. By a *$`d`$-partition* we mean an unordered partition of $`[n]`$ into $`d`$ subsets $`A_i`$. Let $`L_w`$ be a tropical $`d`$-plane and $`F`$ a maximal cell of $`L_w`$. Thus $`F`$ is a $`d`$-dimensional convex polyhedron in $`^n`$. The affine span of $`F`$ is a $`d`$-dimensional affine space which is defined by equations of the special form

$$x_kx_j=w_{J\backslash \{j\}}w_{J\backslash \{k\}}\text{(the right hand side is a constant)}$$

Such a system of equations defines a $`d`$-partition $`\{A_1,\mathrm{},A_d\}`$, namely, two indices $`j`$ and $`k`$ lie in the same block $`A_i`$ if and only if the difference $`x_kx_j`$ is constant on $`F`$. The number of blocks clearly equals $`d`$, the dimension of $`F`$.

###### Remark 6.4.

A maximal face $`F`$ of $`L_w`$ is uniquely specified by its $`d`$-partition $`\{A_1,\mathrm{},A_d\}`$. It is a (bounded) polytope in $`^n`$ if and only if $`|A_i|2`$ for all $`i`$. Hence a tropical $`d`$-plane $`L_w^n`$ has no bounded $`d`$-faces if $`n2d1`$.

We define the *type* of a tropical $`d`$-plane $`L`$, denoted $`\mathrm{type}(L)`$ to be the set of all $`d`$-partitions arising from the maximal faces of $`L`$. If $`d=2`$ and $`L=L_w`$ with $`wC_\sigma `$ then $`\mathrm{type}(L)`$ is precisely the set $`\sigma `$ together with the pairs $`\{\{i\},[n]\backslash \{i\}\}`$ representing the unbounded edges of the tree $`L`$. This follows from Corollary 6.1. Thus $`\mathrm{type}(L)`$ generalizes the Buneman representation of semi-labeled trees (Section 4) to higher-dimensional tropical planes $`L`$.

The type of a tropical plane $`L_w`$ is a strong combinatorial invariant, but it does not uniquely determine the cone of $`𝒢_{d,n}`$ which has $`w`$ in its relative interior. We will see this phenomenon in the example below.

###### Example 6.5.

We present three of the seven types in $`𝒢_{3,6}`$. In each case we display $`\mathrm{type}(L_w)`$ with the $`15`$ obvious tripartitions $`\{i,j,[6]\backslash \{i,j\}\}`$ removed.

We begin with a type which we call the *sagbi type*:

$`\{\{1,23,456\},\{1,56,234\},\{2,13,456\},\{2,56,134\},`$
$`\text{EEFF1}:`$ $`\{3,12,456\},\{3,56,124\},\{4,12,356\},\{4,56,123\},`$
$`\{5,12,346\},\{5,46,123\},\{6,12,345\},\{6,45,123\},\{12,34,56\}\}`$
The next type is the *bipyramid type*. All three tetrahedra in a bipyramid FFFGG have the same type listed below. As the faces of $`𝒢_{3,6}^{\prime \prime \prime }`$ contain those $`w`$ inducing different initial ideals $`\mathrm{in}_w(I_{d,n})`$, this example demonstrates that $`\mathrm{type}(L_w)`$ does not determine $`\mathrm{in}_w(I_{d,n})`$.

$`\{\{1,34,256\},\{1,56,234\},\{2,34,156\},\{2,56,134\}`$
$`\text{FFGG}:`$ $`\{3,12,456\},\{3,56,124\},\{4,12,356\},\{4,56,123\}`$
$`\{5,12,346\},\{5,34,126\},\{6,12,345\},\{6,34,125\},\{12,34,56\}\}`$
For all but one of the seven types in $`𝒢_{3,6}`$, the tropical plane $`L_w`$ has $`28`$ facets. The only exception is the type EEEE. Here the tropical plane $`L_w`$ has only $`27`$ facets, all of them unbounded.

$`\{\{1,23,456\},\{1,234,56\},\{2,13,456\},\{2,135,46\}`$
$`\text{EEEE}:`$ $`\{3,12,456\},\{3,126,45\},\{4,26,135\},\{4,126,35\}`$
$`\{5,16,234\},\{5,126,34\},\{6,15,234\},\{6,135,24\}\}`$
## 7 Dependence on the characteristic

Our definition of the tropical Grassmannian implicitly depended on the fields $`K`$ and $`k`$. The ideal $`I_{d,n}`$ makes sense over any field and has the same generators (the classical Plücker relations). Nonetheless, the properties of the initial ideal $`in_w(I_{d,n})`$ might depend on $`k`$, in particular, whether or not this ideal contains a monomial might depend on the charcteristic of $`k`$. Hence, whether or not $`w𝒢_{d,n}`$ might depend on the characteristic of $`k`$.

In Corollary 4.5 we saw that this does not happen for $`d=2`$, and it follows from the explicit computations in Section 6 that this does not happen for $`𝒢_{3,6}`$ either. In both of these cases, the tropical Grassmannian is characteristic-free. Another result that we observed in both of these nice cases is that it was enough to look at quadratic polynomials in $`I_{d,n}`$ to define the tropical Grassmannian. We shall see below that the same results do not hold for the next case $`𝒢_{3,7}`$. We summarize our result this in the following theorem.

###### Theorem 7.1.

Let $`d=2`$ or $`d=3`$ and $`n=3`$. Then every monomial-free initial ideal of $`I_{d,n}`$ is generated by quadrics, and the tropical Grassmannian $`𝒢_{d,n}`$ is characteristic-free. Both of these properties fail for $`d3`$ and $`n7`$.

###### Proof.

It suffices to consider the case $`d=3`$ and $`n=7`$. An easy lifting argument will extend our example to the general case $`d3`$ and $`n7`$. The Plücker ideal $`I_{3,7}`$ is minimally generated by $`140`$ quadrics in a polynomial ring $`k[p_{123},p_{124},\mathrm{},p_{567}]`$ in $`35`$ unknowns over an arbitrary field $`k`$.

We fix the following zero-one vector. The appearing triples are gotten gotten by a cyclic shift, and they correspond to the lines in the *Fano plane*:

$$w=e_{124}+e_{235}+e_{346}+e_{457}+e_{156}+e_{267}+e_{137}^{\left(\genfrac{}{}{0pt}{}{6}{3}\right)}.$$

We next compute the initial ideal $`\mathrm{in}_w(I_{3,7})`$ under the assumption that the characteristic of $`k`$ is zero. In a computer algebra system, this is done by computing the reduced Gröbner basis of $`I_{3,7}`$ over the field of rational numbers with respect to the (reverse lexicographically refined) weight order defined by $`w`$. The reduced Gröbner basis is found to have precisely $`196`$ elements, namely, $`140`$ quadrics, $`52`$ cubics, and $`4`$ quartics. The initial ideal $`\mathrm{in}_w(I_{3,7})`$ is generated by the $`w`$-leading forms of the $`196`$ elements in that Gröbner basis.

Among the $`52`$ cubics in the Gröbner basis of $`I_{3,7}`$, we find the special cubic

$`f=2p_{123}p_{467}p_{567}p_{367}p_{567}\underset{¯}{p_{124}}p_{167}p_{467}\underset{¯}{p_{235}}p_{127}p_{567}\underset{¯}{p_{346}}`$
$`p_{126}p_{367}\underset{¯}{p_{457}}p_{237}p_{467}\underset{¯}{p_{156}}+p_{134}p_{567}\underset{¯}{p_{267}}+p_{246}p_{567}\underset{¯}{p_{137}}+p_{136}\underset{¯}{p_{267}}\underset{¯}{p_{457}}.`$
Since $`\mathrm{char}(k)2`$, the leading form of this polynomial is the monomial

$$\mathrm{in}_w(f)=p_{123}p_{467}p_{567}.$$

This proves that $`w`$ is not in the tropical Grassmannian $`𝒢_{3,7}`$.

On the other hand, suppose now that the characteristic of $`k`$ equals two. In that case, the leading form of $`f`$ is a polynomial with seven terms

$$\mathrm{in}_w(f)=p_{367}p_{567}\underset{¯}{p_{124}}p_{167}p_{467}\underset{¯}{p_{235}}\mathrm{}+p_{246}p_{567}\underset{¯}{p_{137}}.$$

This is not a monomial. In fact, none of the leading forms of the $`196`$ Gröbner basis elements is a monomial. This proves that the initial ideal $`\mathrm{in}_w(I_{3,7})`$ contains no monomial, or equivalently, that $`w`$ lies in the tropical Grassmannian $`𝒢_{3,7}`$ when $`\mathrm{char}(k)=2`$. In fact, there is no inclusion in either direction between the tropical Grassmannians $`𝒢_{3,7}`$ in characteristic two and in characteristic zero. To see this, we modify our vector $`w`$ as follows:

$$w^{}=we_{124}=e_{235}+e_{346}+e_{457}+e_{156}+e_{267}+e_{137}^{\left(\genfrac{}{}{0pt}{}{6}{3}\right)}.$$

Then $`in_w^{}(f)=2p_{123}p_{467}p_{567}p_{367}p_{567}\underset{¯}{p_{124}}`$, which is not monomial if $`\mathrm{char}(k)=0`$, but it is a monomial if $`\mathrm{char}(k)=2`$. This shows that $`w^{}`$ does not lie in $`𝒢(3,7)`$ if the characteristic of $`k`$ is two. By recomputing the Gröbner basis in characteristic zero, we find that the initial ideal $`in_w^{}(I_{3,7})`$ contains no monomial, and hence does lie in $`𝒢(3,7)`$ if the characteristic of $`k`$ is zero.

The above argument also shows that, in any characteristic, either $`\mathrm{in}_w(I_{3,6})`$ or $`\mathrm{in}_w^{}(I_{3,6})`$ will be a monomial-free initial ideal which has a minimal generator of degree three. Quadrics do not suffice for $`d3`$ and $`n7`$. ∎

It is worth taking a moment to think about the intuitive geometry behind this argument. Let $`B`$ be any subset of $`\left(\genfrac{}{}{0pt}{}{[n]}{d}\right)`$; we can study the collection of points on the Grassmannian $`G(d,n)`$ over the field $`k`$ where the Plücker coordinate $`P_I`$ is nonzero exactly for those $`IB`$. Such points exist exactly if $`B`$ is the set of bases of a matroid of rank $`d`$ on $`n`$ points realizable over $`k`$.

Thus, when the characteristic of $`k`$ is $`2`$ there is a point $`xG_{3,7}`$ with $`x_{ijk}=0`$ exactly when $`i`$, $`j`$ and $`k`$ are collinear in the Fano plane and no such point should exist in characterisitc other than $`2`$. Passing to the tropicalization, one would expect that in characteristic $`2`$ there should be a point $`y𝒢_{d,n}`$ with $`y_{ijk}=\mathrm{}`$ for $`i`$, $`j`$ and $`k`$ collinear in the Fano plane and $`y_{ijk}=0`$ otherwise. Intuitively, $`w`$ is a perturbation of $`y`$ so that $`w_{ijk}`$ is 1 and not $`\mathrm{}`$.


format: text

text:
# Pattern formation driven by nematic ordering of assembling biopolymers

## Abstract

The biopolymers actin and microtubules are often in an ongoing assembling/disassembling state far from thermal equilibrium. Above a critical density this leads to spatially periodic patterns, as shown by a scaling argument and in terms of a phenomenological continuum model, that meets also Onsager’s statistical theory of the nematic–to–isotropic transition in the absence of reaction kinetics. This pattern forming process depends much on nonlinear effects and a common linear stability analysis of the isotropic distribution of the filaments is often misleading. The wave number of the pattern decreases with the assembling/disassembling rate and there is an uncommon discontinuous transition between the nematic and the periodic state.

preprint: APS

Ongoing polymerization and depolymerization of actin and microtubule filaments are prominent examples for dissipative non–equilibrium phenomena in living cells Alberts:2001 , which are important for many different purposes, such as the cell motility and division or morphogenesis. Both substances show also an inherent propensity to pattern formation and active phenomena Hill:87.1 ; Mandelkow:89.1 ; Tabony:90.1 ; Leibler:97.1 ; Ott:1997.1 ; Kaes:2002.1 ; Kaes:2003.101 . Like the famous example for rod–like particles, the Tobacco Mosaic Virus (TMV) Bawden:1936.1 , also actin and microtubule filaments may undergo with increasing density a well known transition to an orientational order Hitt:90.1 ; Suzuki:91.1 ; Kaes:96.1 , the so–called nematic order Onsager:49.1 ; deGennes:93 . By Onsager’s seminal work Onsager:49.1 ; Straley:1973.1 ; deGennes:93 ; Odijk:86.1  this transition has been traced back to excluded volume interactions between the filaments. This statistical theory is valid for long filaments of fixed shape and infinite lifetime $`\tau `$, and it predicts near the transition also a phase separation into domains of isotropically oriented rods at low density and nematic domains of higher rod–density, which has also been observed for actin with an almost vanishing kinetics Kaes:96.1 . For a finite lifetime of actin and microtubule filaments, Onsager’s statistical theory for the nematic order does not apply. Moreover, a finite $`\tau `$ limits the diffusive transport distance and the coarsening during the phase separation close to the orientational transition to a length scale of about $`l_D=\sqrt{D_\rho \tau }`$, with the filament diffusion constant $`D_\rho `$. According to our estimate we expect kinetically induced periodic patterns with a wavelength in the order of 10 $`\mu m`$. This is supported by current experiments Kaes:2003.101 .

The effect of reaction kinetics on a phase separation has been investigated for a chemical and a biophysical example in Refs. Glotzer:95.1 ; Zimmermann:95.2 . In both cases the transition to periodic patterns is supercritical and its onset as well as wavelength follows already from a linear stability analysis of the respective homogeneous basic state. Instead of these two competing states, near the orientational transition of filaments one has three different competing states, the spatially homogeneous isotropic state, the spatially homogeneous nematic one and the spatially inhomogeneous alternation between the isotropic and the nematic order. Here, the growth rate of perturbations of the basic state takes its maximum also at a finite wavenumber Doi:88.1 ; Liverpool:2003.2 , but this is not sufficient for a prediction of spatially inhomogeneous nonlinear states above the orientational transition. Instead of an inhomogeneous state, as suggested by the linear perturbation analysis, in the nonlinear regime one has an exchange of stability and the spatially homogeneous nematic state is often preferred, as described in this work. Therefore the bifurcation picture has to be explored by a nonlinear analysis, whereby an uncommon coarsening behavior at the nonlinear nematic–to–periodic transition has been found.

The generic scenario near the ordering transition is described in terms of a phenomenological model, which is introduced and analyzed at first without the reaction kinetics of the filaments. It is extended in the second part by the essential reaction steps as motivated by actin and microtubule polymerization.

Model without reaction kinetics. – In lyotropic liquid crystals the nematic order is forced beyond a critical rod density $`\stackrel{~}{\rho }_c`$ by excluded volume interactions Onsager:49.1  and the resulting local mean orientation of rod–like particles is described by the so–called director $`𝐧(𝐫)`$ (with $`𝐧=𝐧`$) deGennes:93 . Assuming rods of a single length and a uniform $`𝐧`$, then the largest eigenvalue $`\stackrel{~}{\lambda }`$ of the nematic order parameter tensor is sufficient for a description of the strength of the orientational order. $`\stackrel{~}{\lambda }`$ varies in the range $`[\frac{1}{3},1]`$, with $`\stackrel{~}{\lambda }=\frac{1}{3}`$ in the isotropic state and $`\stackrel{~}{\lambda }=1`$ for a uniform rod orientation deGennes:93 ; Dhont:2001.1 . It is convenient to use the difference $`\lambda :=\stackrel{~}{\lambda }\frac{1}{3}`$ and the dimensionless rod density $`\rho \stackrel{~}{\rho }V_E`$, with $`V_E=2bL^2`$ the excluded volume for rods of length $`L`$ and diameter $`b`$. For a constant orientation $`𝐧`$, as we assume in this work, spatial variations of $`\rho `$ and $`\lambda `$ also include spatially alternating isotropic and nematic ranges. Since for long rods the preferred director orientation is parallel to the isotropic–nematic interface Liu:70.1 , we assume spatial variations in the direction perpendicular to $`𝐧`$, which we call the $`x`$–direction. For this context we choose the phenomenological model for the conserved density $`\rho (x,t)`$ and for the unconserved field $`\lambda (x,t)`$

$`_t\rho `$ $`=`$ $`D_\rho _x^2\left[\lambda \rho \delta _\rho _x^2\rho +a_\rho \rho ^3\right],`$ (1a)
$`_t\lambda `$ $`=`$ $`D_r\left[(1\rho )\lambda {\displaystyle \frac{3}{2}}\rho \lambda ^2+{\displaystyle \frac{9}{2}}\rho \lambda ^3\right]`$ (1b)
$`+D_\lambda _x^2\left[(1\rho )\lambda \delta _\lambda _x^2\lambda +a_\lambda \lambda ^3\right].`$
In Eq. (1b), the part without spatial derivatives follows from the Smoluchowski equation for rigid rods by a moment approximation Dhont:2001.1 ; Ziebert:2003.02  and the factor $`\rho `$ in front of the nonlinear terms reflects the excluded volume interaction. It determines also the homogeneous solutions

$$\rho =\rho _0=const.,\lambda _0=0,\lambda _\pm =\frac{1}{6}\pm \frac{1}{6}\sqrt{9\frac{8}{\rho _0}}.$$
(2)
$`\lambda _0=0`$ corresponds to the isotropic rod distribution that becomes linearly unstable with respect to nematic fluctuations beyond the critical density $`\rho >\rho _c=1`$, where they grow up to the homogeneously stable upper branch $`\lambda _+`$ of the spatially uniform nematic order in Fig. 1b). Since the isotropic-nematic transition is of first order, both states coexist in a range $`\frac{8}{9}\rho 1`$.

Eq. (1a) is of the Cahn-Hilliard type Cahn:58.1 . Expressing its right hand side by a divergence of the current density $`j_\rho (x)=D_\rho _x\mu (x)`$ with $`\mu (x)=\lambda \rho \delta _\rho _x^2\rho +a_\rho \rho ^3`$, it takes the form of a conservation law for the rod–like particles. The first (nonlinear) term in Eq. (1a), i.e. $`D_\rho _x^2(\lambda \rho )`$, destabilizes the spatially homogeneous particle density for any finite value of $`\lambda `$ ($`\lambda `$ is always positive) and mimics therefore Onsager s prediction Onsager:49.1 ; Odijk:86.1  that the free energy can be reduced, by separating the system into ranges of low rod density $`\rho _i`$ (isotropic) and high density $`\rho _a`$ (nematic). The second term describes an isotropic-nematic interface energy and the third term limits the modulation amplitudes of the density (see also below).

Theories involving the distribution function predict beyond the critical $`\rho _c=1`$ an instability of the isotropic distribution against inhomogeneous order parameter fluctuations Doi:88.1 ; Ziebert:2003.02 . In Eq. (1b) this is taken into account by $`_x^2((1\rho )\lambda )`$ and the last two terms limit the wavenumber and the amplitude of the nonlinear modulations of $`\lambda `$. For intermediate values of $`\rho `$, Eqs. (1) have stationary kink solutions as shown in Fig. 1c). The densities $`\rho _i`$ and $`\rho _a`$, in the isotropic and nematic range respectively, are determined by the two coefficients $`a_\rho `$ and $`a_\lambda `$, as described in the following. For stationary kinks as in Fig. 1c) the particle transport vanishes $`j_\rho (x)=0`$ and $`\mu (x)=\mu _i=\mu _a`$ is constant. Sufficiently far away from the kink $`\rho _a`$ and $`\rho _i`$ are constant too and one obtains the equation

$`a_\rho \rho _i^3=\lambda _a\rho _a+a_\rho \rho _a^3,`$ (3)
where $`\lambda _a=\lambda (\rho _a)=(1+\sqrt{98/\rho _a})/6`$. The rotational term in Eq. (1b) vanishes in the nematic range as well as trivially in the isotropic range. Defining $`j_\lambda (x)=D_\lambda _x\nu (x)`$, since in the isotropic range $`\lambda _i`$ is zero, $`\nu _i`$ is zero as well. To prevent a current through the interface, the total current, i.e. just $`j_\lambda `$ in the nematic region, has to vanish and it follows $`\nu _a=\nu _i=0`$ leading to

$`(1\rho _a)\lambda _a+a_\lambda \lambda _a^3=0.`$ (4)
As $`\lambda _a`$ is known, from this equation the anisotropic density $`\rho _a`$ follows as a function of $`a_\lambda `$ (or vice versa) and $`\rho _i`$ is given with $`\rho _a`$ via Eq. (3) as a function of $`a_\rho `$ (or vice versa). Therefore, the two densities $`\rho _i`$ and $`\rho _a`$ may also be considered as input parameters that are obtained from different approaches as for instance from Refs. Onsager:49.1 ; Kayser:1977.1  or possibly from experiments. Since $`\rho _i`$ and $`\rho _a`$ do not depend on the system size $`L`$, the kink position changes with the mean density $`\rho _0`$ as shown in Fig. 1, where the nematic volume fraction $`V_n`$ is given in terms of $`\rho _0`$ .

Linear stability analysis. – For $`\rho >\rho _c`$ a linear stability analysis of the homogeneous isotropic state, cf. $`\lambda =0`$ and $`\rho =\rho _0`$, with respect to small periodic perturbations $`\lambda _1,\rho _1\mathrm{exp}(\sigma t\pm iqx)`$ gives the wave number dependence of the growth rate $`\sigma (q)`$ as shown for a set of parameters in Fig. 2a). This shape of $`\sigma (q)`$ with a positive value at $`q=0`$ and a maximum at a finite value of $`q`$ is typical for the unstable isotropic state and is in agreement with similar results for microscopic models Doi:88.1 . A linear stability analysis of the homogeneous nematic state $`\lambda _\pm `$ in terms of microscopic models is rather involved Ziebert:2003.02 . For our phenomenological model, however, the determination of $`\sigma (q)`$ is a straightforward task and its typical shape at the unstable nematic branch is shown in Fig. 2b). Along the dashed part of the curve in Fig. 1b) the homogeneous nematic state is linear unstable. Between our result and the linear stability described in Doi:88.1  there is a major difference. In both cases $`\sigma (q)`$ for the isotropic state takes its maximum at a finite value of $`q`$ and has positive values for any $`\rho >\rho _c`$. This is somewhat in contradiction to Onsager’s statistical theory, where inhomogeneous states (via phase separation) are only energetically preferred for a rod density below a maximum value $`\rho <\rho _a`$. In our model nonlinear effects stabilize the uniform nematic state for $`\rho >\rho _a`$ and it is unstable only along the dashed line in Fig. 1b). Simulations of Eqs. (1) confirm that inhomogeneous solutions $`\lambda (x)`$ and $`\rho (x)`$ only occur for a mean density $`\rho _0`$ smaller than $`\rho _a`$.

Reaction kinetics drives pattern. – In cells and in vitro actin and microtubule filaments are usually out of equilibrium and, due to an ongoing assembly/disassembly reaction, filaments have a finite lifetime $`\tau `$. This reaction kinetics leads to a stationary length distribution of the filaments Kaes:96.1  or even to oscillatory polymerization Hill:87.1 ; Mandelkow:94.1 ; Hammele:2003.1 . During the phase separation at the isotropic–to–nematic transition, filaments are transported, but only over a lifetime–dependent distance of about $`l_D=\sqrt{D_\rho \tau }`$. Since the lifetime of filaments is a constant, much more subunits are released in the nematic range with a high density $`\rho _a`$ than in the isotropic range with a low density $`\rho _i`$. However, due to a much larger diffusion constant, the subunits are redistributed quickly, leading to a nearly homogeneous subunit density $`m(x)`$. Thus the number of nucleated filaments per unit time, which depends on $`m(x)`$, is weakly varying too. By this qualitative reasoning one expects a steady net transport of subunits from the nematic to the isotropic range and in the opposite direction a transport of filaments, whereby the latter one is limited to distances of the order of $`l_D`$ or smaller. This length restriction causes, instead of a large scale phase separation, a spatially periodic pattern with a wavelength in the order of $`l_D`$.

Along this qualitative reasoning the complexity of the biochemical reaction steps, involved during the assembly/disassembly of actin or microtubules, is not crucial for this wavelength limitation. For instance, actin and microtubules are usually met with a polydisperse length distribution. Since the slowest kinetic step and the small diffusion constant of the long filaments will govern the limitation, we discard the polydispersity and assume for the sake of simplicity that all filaments are of the same length. With a decay $`\mathrm{\Sigma }=\tau ^1`$ and a nucleation rate $`s`$ of the filaments and a diffusion constant $`D_m`$ of the subunits one ends up finally with the three equations

$`_t\rho `$ $`=`$ $`D_\rho _x^2\left[\lambda \rho \delta _\rho _x^2\rho +a_\rho \rho ^3\right]+sm\mathrm{\Sigma }\rho ,`$ (5a)
$`_t\lambda `$ $`=`$ $`D_r\left[(1\rho )\lambda {\displaystyle \frac{3}{2}}\rho \lambda ^2+{\displaystyle \frac{9}{2}}\rho \lambda ^3\right]`$ (5b)
$`+D_\lambda _x^2\left[(1\rho )\lambda \delta _\lambda _x^2\lambda +a_\lambda \lambda ^3\right]\mathrm{\Sigma }\lambda ,`$
$`_tm`$ $`=`$ $`D_m_x^2m\gamma sm+\gamma \mathrm{\Sigma }\rho .`$ (5c)
The constant $`\gamma `$ is a measure for the number of subunits per rod–like particle. In the nematic range oriented filaments are lost, but new ones are nucleated everywhere with an arbitrary orientation which have to relax to the local mean orientation by rotational diffusion. Accordingly, there is only a decay term in Eq. (5b) which can be justified also microscopically Ziebert:2003.02 . This reaction kinetically caused partial loss of the orientational order leads to a higher critical density for the isotropic–to–nematic transition $`\rho _c=1+\mathrm{\Sigma }/D_r`$.

In the presence of reactive steps the rates $`s`$ and $`\mathrm{\Sigma }`$ determine the mean rod density in terms of the monomer density $`\rho =s\mathrm{\Sigma }^1m`$. The spatially homogeneous solutions of Eqs.(5) are

$$\rho =\rho _0,\lambda _0=0,\lambda _\pm =\frac{1}{6}\pm \frac{1}{6}\sqrt{9\frac{8}{\rho _0}\left(1+\frac{\mathrm{\Sigma }}{D_r}\right)},$$
(6)
where $`\lambda _\pm (\rho )`$ are depicted as a function of the mean density $`\rho `$ in Fig. 3d). In a certain parameter range $`\lambda _+`$ may become unstable with respect to periodic perturbations $`\lambda _1,\rho _1\mathrm{exp}(\sigma t\pm iqx)`$ and the wave number dependence of the growth rate $`\sigma (q)`$ has a typical shape as in Fig. 2c). Compared to the case without kinetics as in Fig. 2b), long wavelength perturbations are now suppressed and only perturbations with a finite wave number grow. The parameter range of the unstable homogeneous $`\lambda _+`$ branch is indicated by the dashed and the stable one by the solid line in Fig. 3d). The unstable range of the nematic branch decreases with increasing coefficients $`\delta _\rho `$ and $`\delta _\lambda `$ and with increasing and moderate values of the decay rate $`\mathrm{\Sigma }`$. Periodic states occurring at the unstable nematic branch are shown in Fig. 3a) and b) for three different mean densities $`\rho _0`$. The maxima of $`\rho (x)`$ come close to $`\rho _a`$, cf. Fig. 1, but the minima of $`\rho (x)`$ are considerably larger than $`\rho _i`$ in the case without kinetics. The solid line in Fig. 3c) indicates the range where the nonlinear periodic state is in coexistence with the homogeneous states. For $`\rho >\rho ^{}`$, along the dashed line in Fig. 3c), the periodic pattern becomes increasingly anharmonic, plateaus $`\rho \rho _a`$ spread out and the valleys of low filament density in between become less and narrower by approaching the upper end of the dashed curve in Fig. 3c), a behavior that is rather uncommon CrossHo . At the left end of this curve the state remains periodic, the wavelength increases and the valleys spread out.

Conclusions.– A reaction kinetically driven pattern forming process is predicted near the isotropic–nematic (I-N) transition, which is supported by recent experiments on actin polymerization Kaes:2003.101 . A phenomenological continuum model is introduced that reproduces the first order I-N transition in lyotropic liquid crystals, including the phase separation in its neighborhood and being in agreement with the statistical theory of Onsager. Periodic solutions arise due to a finite lifetime $`\tau `$ and a nucleation rate of the filaments. However, the correlation between a finite $`\tau `$ and the occurrence of periodic patterns is independent of the details of the model. Beyond a critical density $`\rho _c`$ the isotropic orientation of the filaments and below a certain $`\rho ^{}`$ the uniform nematic state becomes unstable against inhomogeneous perturbations. Hence for $`\rho <\rho ^{}`$ periodic states are favored and for our model the wavenumber varies as $`q\tau ^{0.17}`$. However, $`\rho _c`$ increases and $`\rho ^{}`$ decreases with $`\mathrm{\Sigma }=\tau ^1`$ and it may happen that $`\rho ^{}<\rho _c`$ holds, i.e. in a certain parameter range kinetics favors the uniform nematic state. Therefore, inhomogeneous states as predicted by a linear stability analysis of the isotropic state Doi:88.1 ; Liverpool:2003.2  may be irrelevant due to nonlinear effects. This pattern formation process near the I-N transition is expected to be generic and may also apply to situations with different transport and filament accumulation mechanisms such as in the case of filament bundling Takiguchi:91.1 ; Kruse:2001.1 ; Benedix:2003.101 . Even though our description is very simplified and restricted to one spatial dimension, we expect that the basic physical mechanism also plays a crucial role for situations with polydisperse filament distributions Hill:87.1 ; Kaes:96.1 ; Sollich:2002.1 , including living cells. Polydispersity favors periodic patterns and together with higher spatial dimensions this will give rise to an even larger variety of phenomena, to which forthcoming works are devoted.

We thank with great pleasure J. Dhont, B. Gentry, M. Hammele, J. Käs and K. Kawasaki for fruitful discussions.