You are an expert at summarizing long articles. Proceed to summarize the following text: 
tropical algebraic geometry is the geometry of the tropical semiring @xmath0 . its objects are polyhedral cell complexes which behave like complex algebraic varieties . although this is a very new field in which many basic questions have not yet been addressed ( see @xcite for a nice introduction ) , tropical geometry has already been shown to have remarkable applications to enumerative geometry ( see @xcite ) , as well as connections to representation theory ( see @xcite , @xcite , @xcite ) .    the classical theory of total positivity concerns matrices in which all minors are positive . however , in the past decade this theory has been extended by lusztig ( see @xcite and @xcite ) , who introduced the totally positive variety @xmath11 in an arbitrary reductive group @xmath12 and the totally positive part @xmath13 of a real flag variety @xmath14 . in the process , lusztig discovered surprising connections between his theory of canonical bases for quantum groups and the theory of total positivity .    in this paper we introduce the totally positive part ( or positive part , for short ) of the tropicalization of an arbitrary affine variety over the ring of puiseux series , and then investigate what we get in the case of the grassmannian @xmath15 . first we give a parameterization of the totally positive part of the grassmannian , largely based on work of postnikov @xcite , and then we compute its tropicalization , which we denote by @xmath1 . we identify @xmath1 with a polyhedral subcomplex of the @xmath16-dimensional grbner fan of the ideal of plcker relations , and then show that this fan , modulo its @xmath17-dimensional lineality space , is combinatorially equivalent to an @xmath18-dimensional fan which we explicitly describe . as a special case , we show that @xmath2 is a fan which appeared in the work of stanley and pitman ( see @xcite ) , which parameterizes certain binary trees , and which is combinatorially equivalent to the ( type @xmath19 ) associahedron . we also show that @xmath4 and @xmath5 are fans which are closely related to the fans of the types @xmath6 and @xmath7 associahedra , which were first introduced in @xcite . these results are strikingly reminiscent of the results of fomin and zelevinsky @xcite , and scott @xcite , who showed that the grassmannian has a natural cluster algebra structure which is of type @xmath19 for @xmath8 , type @xmath6 for @xmath9 , and type @xmath7 for @xmath10 . ( fomin and zelevinsky proved the @xmath8 case and stated the other results ; scott worked out the cluster algebra structure of all grassmannians in detail . ) finally , we suggest a general conjecture about the positive part of the tropicalization of a cluster algebra . in this section we will define the tropicalization and positive part of the tropicalization of an arbitrary affine variety over the ring of puiseux series . we will then describe the tropical varieties that will be of interest to us . let @xmath20 and @xmath21 be the fields of puiseux series over @xmath22 and @xmath23 . every puiseux series @xmath24 has a unique lowest term @xmath25 where @xmath26 and @xmath27 . setting @xmath28 , this defines the _ valuation map _ @xmath29 . we define @xmath30 to be @xmath31 . we will discuss the wisdom of this definition later ; for practically all purposes , the reader may think of @xmath32 as if it were @xmath22 and of @xmath30 as if it were @xmath33 . let @xmath34 $ ] be an ideal . we define the tropicalization of @xmath35 , denoted @xmath36 , to be the closure of the image under @xmath37 of @xmath38 , where @xmath35 is the variety of @xmath39 . similarly , we define the positive part of @xmath36 , which we will denote as @xmath40 , to be the closure of the image under @xmath37 of @xmath41 . note that @xmath42 and @xmath43 are slight abuses of notation ; they depend on the affine space in which @xmath44 is embedded and not solely on the variety @xmath44 .    if @xmath45 \setminus \ { 0 \}$ ] , let the _ initial form _ @xmath46 $ ] be defined as follows : write @xmath47 for @xmath48 chosen as large as possible such that all powers of @xmath49 in @xmath50 are nonnegative . then @xmath51 is the polynomial obtained from @xmath50 by plugging in @xmath52 . if @xmath53 , we set @xmath54 . if @xmath55 then @xmath56 is defined to be @xmath57 . if @xmath34 $ ] then @xmath58 is the ideal generated by @xmath56 for all @xmath59 . it was shown in @xcite that @xmath36 consists of the collection of @xmath60 for which @xmath58 contains no monomials . the essence of this proof was the following :    @xcite [ lift ] if @xmath61 and @xmath58 contains no monomial then @xmath62 is nonempty and any point @xmath63 of this variety can be lifted to a point @xmath64 with the leading term of @xmath65 equal to @xmath66 . we now prove a similar criterion to characterize the points in @xmath40 . [ poschar ] a point @xmath67 lies in @xmath40 if and only if @xmath58 does not contain any nonzero polynomials in @xmath68 $ ] .    in order to prove this proposition , we will need the following result of @xcite , which relies heavily on a result of @xcite . @xcite[einsedler ] an ideal @xmath39 of @xmath69 $ ] contains a nonzero element of @xmath70 $ ] if and only if @xmath71 for all @xmath72 . we are now ready to prove proposition [ poschar ] . define @xmath73 to be the image of @xmath74 under @xmath37 . let @xmath75 denote the subset of @xmath76 consisting of those @xmath60 for which @xmath58 contains no polynomials with all positive terms . by definition , @xmath40 is the closure of @xmath77 in @xmath76 . we want to show that the closure of @xmath77 is @xmath75 . it is obvious that @xmath77 lies in @xmath75 . @xmath75 is closed , as the property that @xmath56 has only positive terms is open as @xmath60 varies . thus , the closure of @xmath77 lies in @xmath75 . conversely , suppose that @xmath78 . then , by proposition [ einsedler ] , for some @xmath72 , @xmath79 . for @xmath80 sufficently small , we have @xmath81 . therefore we can find a sequence @xmath82 , @xmath83 ,  approaching @xmath60 with @xmath84 . as @xmath60 varies , @xmath58 takes on only finitely many values , and the subsets of @xmath76 on which @xmath58 takes a specific value form the relative interiors of the faces of a complete rational complex known as the grbner complex ( see @xcite ) . these complexes are actually fans when @xmath39 is defined over @xmath23 ( @xcite ) . therefore , we may perturb each @xmath85 , while preserving @xmath86 , in order to assume that the @xmath87 and we still have @xmath88 . then , by proposition [ lift ] , each @xmath89 , so @xmath60 is in the closure of @xmath77 as desired . [ fancorollary ] @xmath36 and @xmath40 are closed subcomplexes of the grbner complex . in particular , they are polyhedral complexes . if @xmath39 is defined over @xmath23 , then @xmath36 and @xmath40 are closed subfans of the grbner fan .    one might wonder whether it would be better to modify the definition of @xmath30 to require that our power series lie in @xmath90 . this definition , for example , is more similar to the appearance of the ring of formal powers series in @xcite . one can show that in the case of the grassmanian , this difference is unimportant . moreover , the definition used here has the advantage that it makes it easy to prove that the positive part of the tropicalization is a fan . suppose @xmath91 and @xmath92 are varieties and we have a rational map @xmath93 taking @xmath94 . unfortunately , knowing @xmath95 for @xmath96 does not in general determine @xmath97 , so we do nt get a nice map @xmath98 . however , suppose that @xmath99 takes the positive points of @xmath35 surjectively onto the positive points of @xmath100 and suppose that @xmath101 is _ subtraction - free _ , that is , the formulas for the @xmath102 s are rational functions in the @xmath103 s whose numerators and denominators have positive coefficients . define @xmath104 by replacing every @xmath105 in @xmath99 with a @xmath106 , every @xmath107 with a @xmath108 , every @xmath106 with a @xmath109 and every constant @xmath110 with @xmath111 . [ blah ] suppose @xmath112 and @xmath113 are varieties . let @xmath114 be a subtraction - free rational map taking @xmath35 to @xmath100 such that @xmath115 surjects onto @xmath116 . then @xmath117 takes @xmath40 surjectively onto @xmath118 . this follows immediately from the formulas @xmath119 and @xmath120 for @xmath121 and @xmath122 . we now define the objects that we will study in this paper . fix @xmath123 and @xmath17 , and let @xmath124 . fix a polynomial ring @xmath125 in @xmath126 variables with coefficients in a commutative ring . the _ plcker ideal _ @xmath127 is the homogeneous prime ideal in @xmath125 consisting of the algebraic relations ( called _ plcker relations _ ) among the @xmath128 minors of any @xmath129-matrix with entries in a commutative ring . classically , the _ grassmannian _ @xmath15 is the projective variety in @xmath130 defined by the ideal @xmath127 of plcker relations . we write @xmath131 for the variety in @xmath132 defined by the same equations . similarly , we write @xmath133 for the real points of the grassmannian , @xmath134 for the real positive points , @xmath135 for those points of @xmath136 all of whose coordinates lie in @xmath30 and so on . we write @xmath137 when we want to emphasize that we are using the field @xmath22 , and use @xmath15 when discussing results that hold with no essential modification for any field . the _ totally positive grassmannian _ is the set @xmath134 . an element of @xmath15 can be represented by a full rank @xmath129 matrix @xmath138 . if @xmath139 \choose k}$ ] we define the _ plcker coordinate _ @xmath140 to be the minor of @xmath138 corresponding to the columns of @xmath138 indexed by @xmath141 . we identify the element of the grassmannian with the matrix @xmath138 and with its set of plcker coordinates ( which satisfy the plcker relations ) . our primary object of study is the _ tropical positive grassmannian _ @xmath1 , which is a fan , by corollary [ fancorollary ] . as in @xcite , this fan has an @xmath17-dimensional lineality space . let @xmath142 denote the map from @xmath143 into @xmath144 which sends @xmath145 to the @xmath16-vector whose @xmath146-coordinate is @xmath147 . we abuse notation by also using @xmath142 for the same map @xmath148 . let @xmath149 denote the corresponding linear map which sends @xmath145 to the @xmath16-vector whose @xmath146-coordinate is @xmath150 . the map @xmath149 is injective , and its image is the common lineality space of all cones in @xmath151 . in this section we explain two equivalent ways to parameterize @xmath134 , as well as a way to parameterize @xmath152 . the first method , due to postnikov @xcite , uses a certain directed graph @xmath153 with variables associated to each of its @xmath154 edges . the second method is closely related to the first and uses the same graph , but this time variables are associated to each of its @xmath155 regions . this has the advantage of giving a bijection between @xmath156 and @xmath134 . finally , we use @xmath153 with variables labelling each of its @xmath157 inner regions in order to give a bijective parameterization of @xmath158 . let @xmath153 be the directed graph which is obtained from a @xmath123 by @xmath159 grid , as shown in figure [ web49 ] . it has @xmath123 incoming edges on the right and @xmath159 outgoing edges on the bottom , and the vertices attached to these edges are labelled clockwise from @xmath160 to @xmath17 . we denote the set of @xmath154 edges by @xmath161 . let us associate a formal variable @xmath162 with each edge @xmath163 , and if there is no ambiguity , we abbreviate the collection @xmath164 by @xmath121 . if @xmath165 is a path on @xmath153 ( compatible with the directions of the edges ) , then we let @xmath166 denote @xmath167 . and if @xmath125 is a set of paths on @xmath153 , then we let @xmath168 denote @xmath169 .    as in @xcite , we define a @xmath129 matrix @xmath170 , whose entries @xmath171 are polynomials in the variables @xmath162 , by the following equation : @xmath172 where the sum is over all directed paths @xmath165 from vertex @xmath173 to vertex @xmath174 . note that the @xmath128 submatrix of @xmath170 obtained by restricting to the first @xmath123 columns is the identity matrix . in particular , @xmath175 is a full rank matrix and hence we can identify it with an element of @xmath15 . also note that every element of the totally positive grassmannian @xmath134 has a unique matrix representative whose leftmost @xmath128 submatrix is the identity . we shall see that as the @xmath164 vary over @xmath176 , the @xmath175 range over all of @xmath134 . we now show it is possible to express the maximal minors ( plcker coordinates ) of @xmath175 as subtraction - free rational expressions in the @xmath162 , as shown in @xcite . if @xmath177 \choose k}$ ] , then let @xmath178 denote the set @xmath179\backslash ( k\cap [ k ] ) \text { to } k\backslash ( [ k]\cap k ) \}.\ ] ] note that for @xmath180 $ ] , we consider the empty set to be a legitimate set of pairwise vertex - disjoint paths .    applied to @xmath153 , theorem 15.4 of @xcite implies the following . [ plucker ] the plcker coordinates of @xmath175 are given by @xmath181    we give a brief proof of this result : the main idea is to use the well - known gessel - viennot trick @xcite . first note that @xmath171 has a combinatorial interpretation : it is a generating function keeping track of paths from @xmath173 to @xmath174 . thus , the determinant of a @xmath128 submatrix of @xmath175 corresponding to the column set @xmath141 also has a combinatorial interpretation : it is a generating function for all sets of paths from @xmath182\backslash ( k\cap [ k])$ ] to @xmath183\cap k)$ ] , with the sign of each term keeping track of the number of crossings in the corresponding path set . what we need to show is that this is equal to the sum of the contributions from path sets which are pairwise vertex - disjoint . to see this , consider a path set which does have an intersection . look at its lexicographically last intersection , and compare this path set to the one obtained from it by switching the two path tails starting at that point of intersection . these two path sets get different signs , but have equal weights , and hence they cancel each other out . proposition [ plucker ] allows us to define a map @xmath184 as follows . let @xmath177 \choose k}$ ] , and define @xmath185 by @xmath186 clearly if we substitute positive values for each @xmath162 , then @xmath187 will be positive . we now define @xmath188 by @xmath189\choose k}}.\ ] ] in other words , @xmath188 is the map which sends a collection of positive real numbers @xmath164 to the element of @xmath15 with plcker coordinates @xmath187 ( which is identified with the matrix @xmath175 ) .    by theorem 19.1 of @xcite , the map @xmath188 is actually surjective : any point in @xmath134 can be represented as @xmath175 for some positive choices of @xmath164 . in summary , we have the following result ( which will also be a consequence of our theorem [ bij ] ) . [ parameter ] the map @xmath190 is a surjection onto @xmath134 . unfortunately , the method we have just described uses @xmath154 variables to parameterize a space of dimension @xmath155 . we will now explain how to do a substitution of variables which will reduce the number of variables to @xmath155 . we define an _ inner region _ of @xmath153 to be a bounded component of the complement of @xmath153 ( viewed as a subset of @xmath191 ) . and we define an _ outer region _ of @xmath153 to be one of the extra inner regions we would obtain if we were to connect vertices @xmath173 and @xmath192 by a straight line , for @xmath173 from @xmath160 to @xmath193 . a _ region _ is an inner or outer region . note that there are @xmath155 regions , which we denote by @xmath194 , and there are @xmath157 inner regions . let us label each region @xmath195 with a new variable @xmath196 , which we define to be the product of its counterclockwise edge variables divided by the product of its clockwise edge variables . for example , the new variables @xmath197 shown in figure [ substitute ] would be defined by @xmath198    it is easy to check that for a path @xmath165 on @xmath153 , @xmath166 is equal to the product of the variables attached to all regions below @xmath165 . since @xmath168 and @xmath175 were defined in terms of the @xmath166 s , we can redefine these expressions in terms of the @xmath155 region variables . proposition [ parameter ] still holds , but our map is now a map @xmath199 from @xmath156 onto @xmath134 , taking the region variables @xmath200 to the element of @xmath134 represented by @xmath170 . since we are now parameterizing a space of dimension @xmath155 with @xmath155 variables , we should have a bijection . we shall prove that this is so by constructing the inverse map . [ bij ] the map @xmath201 , which maps @xmath202 to the grassmannian element represented by @xmath175 , is a bijection . before we prove this theorem , we need a lemma about matrices and their minors . we use a very slight generalization of a lemma which appeared in @xcite . for completeness , we include the proof of this lemma . first we must define some terminology . let @xmath203 be a @xmath129 matrix . let @xmath204 denote the minor of @xmath203 which uses row set @xmath39 and column set @xmath205 . we say that @xmath204 is _ solid _ if @xmath39 and @xmath205 consist of several consecutive indices ; if furthermore @xmath206 contains @xmath160 , we say that @xmath204 is _ initial_. thus , an initial minor is a solid minor which includes either the first column or the first row . @xcite[minors ] a matrix @xmath203 is uniquely determined by its initial minors provided that all these minors are nonzero . let us show that each matrix entry @xmath207 of @xmath203 is uniquely determined by the initial minors . if @xmath208 or @xmath209 , there is nothing to prove , since @xmath207 is an initial minor . assume that @xmath210 . let @xmath211 be the initial minor whose last row is @xmath173 and last column is @xmath174 , and let @xmath212 be the initial minor obtained from @xmath211 by deleting this row and column . then @xmath213 , where @xmath214 is a polynomial in the matrix entries @xmath215 with @xmath216 and @xmath217 . using induction on @xmath218 , we can assume that each @xmath215 that occurs in @xmath214 is uniquely determined by the initial minors , so the same is true of @xmath219 . we now define a _ reflected initial _ minor to be a solid minor @xmath204 such that @xmath39 contains @xmath123 or @xmath205 contains @xmath160 . thus , a reflected initial minor is a solid minor which includes either the first column or the last row . a trivial corollary of lemma [ minors ] is the following . [ silly ] a matrix @xmath203 is uniquely determined by its reflected initial minors provided that all these minors are nonzero . now we are ready to prove theorem [ bij ] . to prove the theorem , we will construct an explicit inverse map @xmath220 . the first step is to prove that @xmath221 . let us index the regions in @xmath153 by ordered pairs @xmath222 as follows . given a region , we choose @xmath173 to be the label of the horizontal wire which forms the upper boundary of the region , and choose @xmath174 to be the label of the vertical wire which forms the left boundary of the region . now we define a map @xmath141 from the set of regions to @xmath223 \choose k}$ ] by @xmath224 if @xmath222 is not a region of @xmath153 , then we define @xmath225 . let @xmath138 be a @xmath129 matrix whose initial @xmath226 minor is the identity . we define @xmath227 by @xmath228 note that by convention , we define @xmath229 to be @xmath160 . see figure [ inverse ] for the definition of @xmath230 in the case of @xmath231 . note that for brevity , we have omitted the @xmath138 s from each term . we claim that if @xmath232 , then @xmath233 . to prove this , we note that the variable in region @xmath222 can be expressed in terms of vertex - disjoint paths as follows . first observe that if @xmath234 then there is a unique set of pairwise vertex - disjoint paths from @xmath182 \setminus ( [ k ] \cap k(i , j))$ ] to @xmath235 \cap k(i , j))$ ] . if one examines the terms in ( [ preimage ] ) and draws in the six sets of pairwise vertex - disjoint paths on @xmath153 ( say the three from the numerator in red and the three from the denominator in blue ) then it is clear that every region in @xmath153 lies underneath an equal number of red and blue paths  except the region @xmath222 , which lies underneath only one red path . thus , by definition of the maps @xmath236 , it follows that @xmath237    to complete the proof , it remains to show that @xmath230 is injective . this will complete the proof because we know that @xmath238 , and @xmath230 injective then implies that @xmath239 . choose an element of @xmath134 , which we identify with its unique matrix representative @xmath138 whose leftmost @xmath128 minor is the identity . let @xmath240 denote the set of rational expressions which appear in the right - hand side of ( [ preimage ] ) for all regions @xmath222 in @xmath153 . let @xmath241 denote the set of all individual plucker coordinates which appear in @xmath240 . we prove that @xmath230 is injective in two steps . first we show that the values of the expressions in @xmath240 uniquely determine the values of the plcker coordinates in @xmath241 . next we show that the values of the plcker coordinates in @xmath241 uniquely determine the matrix @xmath138 . the first step is clear by inspection . we illustrate the proof in the case of @xmath231 . by the choice of @xmath138 , @xmath242 looking at the rational expressions in figure [ inverse ] , we see that knowing the value @xmath243 determines @xmath244 ; the value @xmath244 together with the value @xmath245 determines @xmath246 ; and similarly for @xmath247 . next , these values together with the value @xmath248 determines @xmath249 , and so on .    for the second step of the proof , let @xmath250 denote the @xmath251 matrix obtained from @xmath138 by removing the leftmost @xmath128 identity matrix . note that the values of the plcker coordinates @xmath252 ( which are all elements of @xmath241 ) determine the values of all of the reflected initial minors of @xmath250 . ( each such plcker coordinate is equal to one of the reflected initial minors , up to sign . ) thus , by corollary [ silly ] , they uniquely determine the matrix @xmath250 and hence @xmath138 . this completes the proof of theorem [ bij ] . now let us parameterize @xmath253 . we shall show that we can do this by using variables corresponding to only the @xmath157 inner regions of @xmath153 . first recall that the @xmath17-dimensional torus acts on @xmath134 by scaling columns of a matrix representative for @xmath254 . ( although the torus has dimension @xmath17 , this is actually just an @xmath255-dimensional action as the scalars act trivially . ) namely , @xmath256 if @xmath254 then we let @xmath257 denote the torus orbit of @xmath138 under this action . note that if @xmath258 , then @xmath259 . we will now determine the corresponding torus action on @xmath156 such that the above bijection commutes with the actions . if @xmath260 is an internal region then @xmath196 is a ratio of plcker coordinates with the same indices appearing on the top and bottom , so @xmath196 is not modified by the torus action . a simple computation shows that the torus acts transitively on the values of the outer region variables . thus , taking the quotient by @xmath261 on the right hand side of the equation corresponds to forgetting the outer variables on the left . define a map @xmath262 by lifting a point @xmath263 to any arbitrarily chosen point @xmath264 and then mapping @xmath265 to @xmath266 . we have just proven :    [ secondbijection ] the map @xmath267 is a bijection . in this section we will construct a lower - dimensional fan associated to the tropical positive grassmannian @xmath1 . by methods precisely analogous to those above , we can prove an analogue of theorem [ secondbijection ] for the field of puiseux series . the map @xmath268 is a bijection . this theorem allows us to compute @xmath269 by applying the valuation map to the image of @xmath270 . by proposition [ blah ] we can tropicalize the map @xmath270 , obtaining the following surjective map . @xmath271    the map @xmath272 is the map we get by replacing multiplication with addition and addition with minimum in the definition of @xmath270 . explicitly , it is defined as follows . let @xmath139 \choose k}$ ] , and let inner region variables take on values @xmath200 in @xmath23 . outer region variables are chosen arbitrarily . if @xmath165 is a path on @xmath153 then we let @xmath273 denote the sum of all variables which label regions below @xmath165 . similarly , if @xmath125 is a set of paths , then let @xmath274 denote @xmath275 . now define @xmath276 by @xmath277 the map @xmath272 is the map @xmath278 given by @xmath279    the fan @xmath280 is the complete fan in @xmath281 whose maximal cones are the domains of linearity of the piecewise linear map @xmath272 .    because @xmath272 surjects onto @xmath269 , the fan @xmath280 reflects the combinatorial structure of the fan @xmath269 , which differs from @xmath1 only through modding out by the linearity space . however , @xmath280 is much easier to work with , as it lives in @xmath157-dimensional space as opposed to @xmath16-dimensional space . since the maps @xmath282 are piecewise linear functions , to each one we can associate a fan @xmath283 whose maximal cones are the domains of linearity for @xmath282 . it is clear that the fan @xmath280 is the simultaneous refinement of all of the fans @xmath283 . from now on , by abuse of notation , we will refer to @xmath269 as @xmath1 . in this section we will describe the fan @xmath284 associated to @xmath2 . we show that this fan is exactly the stanley - pitman fan @xmath285 , which appeared in the work of stanley and pitman in @xcite . in particular , the face poset of @xmath284 , with a top element @xmath286 adjoined , is isomorphic to the face lattice of the normal fan of the associahedron , a polytope whose vertices correspond to triangulations of the convex @xmath17-gon . ( in the language of @xcite , this is the associahedron of type @xmath3 . ) let us first do the example of @xmath287 . we use the web diagram @xmath288 , as shown in figure [ web25 ] . the maps @xmath282 are given by : @xmath289    each map @xmath290 is piecewise linear and so gives rise to the complete fan @xmath283 . for example , the map @xmath291 is linear on the region @xmath292 , where it is the function @xmath293 , and on the region @xmath294 , where it is the function @xmath295 . thus , @xmath296 is simply the subdivision of the real plane into the regions @xmath297 and @xmath298 . the three nontrivial fans that we get from the maps @xmath299 are shown in figure [ fan25 ] . in each picture , the maximal cones of each fan are separated by solid lines . @xmath300 , which is the simultaneous refinement of the three nontrivial fans , is shown in figure [ bigfan25 ] .    in @xcite , it was shown that maximal cones of the fan @xmath301 correspond to trivalent trees on @xmath17 labelled leaves . it turns out that maximal cones of the fan @xmath302 correspond to trivalent planar trees on @xmath17 labelled leaves , as is illustrated in figure [ bigfan25 ] . we will now describe the fan that appeared in @xcite , but first , we must review some notions about trees . plane binary tree _ is a rooted tree such that each vertex has either two children designated as left and right , or none at all ; and an _ internal vertex _ of a binary tree is a vertex which is not a leaf . trivalent planar tree _ is an ( unrooted ) tree such that every vertex has degree three , and such that the leaves are labelled in a clockwise fashion . it is known that both plane binary trees with @xmath193 leaves , and trivalent planar trees with @xmath17 labelled leaves , are counted by the catalan number @xmath303 . there is a simple bijection between such trivalent planar trees and plane binary trees : if t a trivalent planar tree , then simply contract the edge whose leaf is labelled @xmath160 , and make this the root . this bijection is illustrated in figure [ bigfan25 ] . let us now define the stanley - pitman fan @xmath285 in @xmath304 . ( note that we use different indices than are used in @xcite ) . the maximal cones of @xmath285 are indexed by plane binary trees with @xmath193 leaves , in the following manner . let @xmath77 be a plane binary tree with @xmath193 leaves . label the internal vertices of @xmath77 with the numbers @xmath305 in the order of the first time we drop down to them from a child when doing a depth - first search from left to right starting at the root . ( see figure [ bigfan25 ] for examples . ) let @xmath306 denote the coordinates in @xmath304 . if the internal vertex @xmath173 of @xmath77 is the parent of vertex @xmath174 , and @xmath307 , then associate with the pair @xmath222 the inequality @xmath308 while if @xmath309 then associate with @xmath222 the inequality @xmath310 these @xmath311 inequalities define a simplicial cone @xmath312 in @xmath304 . the result proved in @xcite is the following . [ @xcite ] the @xmath313 cones @xmath312 , as @xmath77 ranges over all plane binary trees with @xmath193 leaves , form the chambers of a complete fan in @xmath304 . moreover , the face poset of @xmath285 , with a top element @xmath286 adjoined , is dual to the face lattice of the associahedron which parameterizes triangulations of the convex @xmath17-gon . the key step in proving that our fan @xmath284 is equal to the stanley - pitman fan @xmath285 is the following lemma , also proved in @xcite . let @xmath314 . let @xmath315 consist of all plane binary trees with @xmath193 leaves and root @xmath173 . then @xmath316 . the fan @xmath284 is equal to the fan @xmath285 . first let us describe the fan @xmath284 as explicitly as possible . note that if we label the regions of @xmath317 with the variables @xmath306 from right to left , then all of the maps @xmath282 are of the form @xmath318 where @xmath319 . since this map has the same domains of linearity as the map @xmath320 we can work with the maps @xmath321 instead . let @xmath322 be the fan whose cones are the domains of linearity of @xmath321 . then @xmath284 is the simultaneous refinement of all fans @xmath322 where @xmath319 . now note that the previous lemma actually gives us an algorithm for determining which cone @xmath312 a generic point @xmath323 lies in . namely , if we are given such a point , compute the partial sums of @xmath324 , for @xmath325 . choose @xmath173 such that @xmath324 is the minimum of these sums . ( if @xmath208 , the sum is @xmath326 . ) then the root of the tree @xmath77 is @xmath173 . the left subtree of @xmath77 consists of vertices @xmath327 , and the right subtree of @xmath77 consists of vertices @xmath328 . we now compute @xmath329 and @xmath330 in order to compute the roots of these two subtrees and so forth . now take a point @xmath331 in a cone @xmath332 of @xmath284 . this means that the point is in a domain of linearity for all of the piecewise linear functions @xmath333 where @xmath319 , and we take @xmath334 to be @xmath326 . in other words , for each @xmath173 and @xmath174 , there is a unique @xmath123 such that @xmath335 . in particular , we can reconstruct the tree @xmath77 such that @xmath336 , and _ every _ point @xmath337 belongs to this same cone @xmath312 . finally , we can show by induction that @xmath338 . ( we need to show that all of the functions @xmath321 are actually linear on @xmath312 . ) this shows that each cone @xmath332 in @xmath284 is actually equal to a cone @xmath312 in @xmath285 , and conversely . in connection with their work on cluster algebras , fomin and zelevinsky @xcite recently introduced certain polytopes called _ generalized associahedra _ corresponding to each dynkin type , of which the usual associahedron is the type @xmath138 example . when we computed @xmath339 , the fan associated with @xmath4 , we found that it was closely related to the normal fan of the type @xmath6 associahedron , in a way which we will now make precise . ( we defer the explanation of our computations to the end of this section . ) the @xmath99-vector of @xmath339 is @xmath340 . the rays of @xmath339 are listed in table [ 16 ] , along with the inequalities defining the polytope that @xmath339 is normal to . .rays and inequalities for @xmath339 [ cols= " < , < " , ] cluster algebras are commutative algebras endowed with a certain combinatorial structure , introduced in @xcite and expected to be relevant in studying total positivity and homogeneous spaces , such as grassmannians .    we will not attempt to give a precise definition of a cluster algebra here , but will rather describe their key properties . slightly varying definitions can be found in @xcite , @xcite and @xcite ; we follow @xcite but do not believe these small variations are important . a cluster algebra is an algebra @xmath341 over a field @xmath123 , which in our examples can be thought of as @xmath23 . additionally , a cluster algebra carries two subsets @xmath332 and @xmath342 , known as the coefficient variables and the cluster variables . @xmath332 is finite , but @xmath343 may be finite or infinite . if @xmath343 is finite , @xmath341 is known as a cluster algebra of finite type . there is also a nonnegative integer @xmath260 associated to a cluster algebra and known as the rank of the algebra . there is a pure @xmath344-dimensional simplicial complex called the _ cluster complex _ whose vertices are the elements of @xmath343 and whose maximal simplices are called _ clusters_. we will denote the cluster complex by @xmath345 . if @xmath346 and @xmath347 is a cluster containing @xmath121 , there is always a unique cluster @xmath348 with @xmath349 . let @xmath350 . then there is a relation @xmath351 where @xmath14 is a binomial in the variables of @xmath352 .    for any @xmath346 and any cluster @xmath211 , @xmath121 is a subtraction - free rational expression in the members of @xmath353 and is also a laurent polynomial in the members of @xmath353 . conjecturally , this laurent polynomial has non - negative coefficients . note that this conjecture does not follow from the preceding sentence : @xmath354 is a subtraction - free expression in @xmath121 and @xmath355 , and a polynomial in @xmath121 and @xmath355 , but it is not a polynomial with positive coefficients . it was demonstrated in @xcite that the coordinate rings of grassmannians have natural cluster algebra structures . usually these cluster algebras are of infinite type , making them hard to work with in practice , but in the cases of @xmath8 , @xmath356 for @xmath357 and their duals , we get cluster algebras of finite type .    in the case of @xmath8 , the coefficient set @xmath332 is @xmath358 and the set of cluster variables @xmath343 is @xmath359 . ( note that these @xmath211 s are plcker coordinates and not simplices . ) label the vertices of an @xmath17-gon in clockwise order with the indices @xmath360 and associate to each member of @xmath361 the corresponding chord of the @xmath17-gon . the clusters of @xmath8 correspond to the collections of chords which triangulate the @xmath17-gon . thus , @xmath345 in this example is ( as an abstract simplicial complex ) isomorphic to the dual of the associahedron . since we have shown that the fan of @xmath2 is combinatorially equivalent to the normal fan of the associahedron , it follows that @xmath2 is ( combinatorially ) the cone on @xmath345 .    in the case of @xmath9 , the coefficient set @xmath332 is equal to @xmath362 . @xmath343 contains the other @xmath363 plcker coordinates , but it also contains two unexpected elements : @xmath364 and @xmath365 . by definition , all plcker coordinates are positive on the totally positive grassmannian , so by the results above on subtraction - free rational expressions , these new coordinates are positive on the totally positive grassmannian as well . the new coordinates turn out to be laurent polynomials with positive coefficients in the region variables of section [ parameterize ] . thus , we can tropicalize these laurent polynomials and associate a fan to each of them . when we refine @xmath339 by these fans , the refinement subdivides the two bipyramids and yields precisely the normal fan to the @xmath6 associahedron , which is again the cone over @xmath345 .    in the case of @xmath10 , @xmath332 again consists of @xmath366 where indices are modulo @xmath367 . @xmath343 contains all of the other plcker variables and the pullbacks to @xmath10 of the two new cluster variables of @xmath9 , along with the @xmath367 rational coordinate projections @xmath368 . thus , @xmath343 contains @xmath369 plcker variables and @xmath363 other variables .    as in the case of @xmath9 , the 14 new variables are laurent polynomials with positive coefficients in the region variables of section [ parameterize ] , so to each one we can associate a corresponding fan . when we refine @xmath370 by these 14 new fans , we get a fan combinatorially equivalent to the fan normal to the @xmath7 associahedron . we can describe what we have seen in each of these grassmannian examples in terms of the general language of cluster algebras as follows :    embed @xmath371 in affine space by the variables @xmath372 . then @xmath373 is a fan with lineality space of dimension @xmath374 . after taking the quotient by this lineality space , we get a simplical fan abstractly isomorphic to the cone over @xmath345 . this observation does not quite hold for an arbitrary cluster algebra of finite type . for example , if we take the cluster algebra of @xmath375 and set all coefficient variables equal to @xmath160 , we get a different cluster algebra which is still of type @xmath376 . however , when we compute the positive part of the corresponding tropical variety , we get a fan whose lineality space has dimension @xmath160 , not @xmath326 as the above would predict . our fan is a cone over a hexagon cross a @xmath160-dimensional lineality space , which is a coarsening of the fan normal to the type @xmath376 associahedron . based on this and other small examples , it seems that in order to see the entire cone over @xmath345 , one needs to use  enough " coefficients . let @xmath341 be a cluster algebra of finite type over @xmath23 and @xmath345 its associated cluster complex . if the lineality space of @xmath373 has dimension @xmath374 then @xmath373 modulo its lineality space is a simplicial fan abstractly isomorphic to the cone over @xmath345 . if the condition on the lineality space does not hold , the resulting fan is a coarsening of the cone over @xmath345 . * remark : * the condition on the lineality space can be restated without mentioning tropicalizations . consider the torus @xmath377 acting on the affine space @xmath378 and let @xmath12 be the subgroup taking @xmath371 to itself . we want to require that @xmath379 . * remark : * in the notation of @xcite and @xcite , the condition on the dimension of the lineality space is equivalent to requiring that the matrix @xmath380 be of full rank . we thank andrei zelevinsky for pointing this out to us . note how surprising this conjecture is in light of how the two complexes are computed . the fan described in the conjecture is computed as the refinement of a number of fans , indexed by the vertices of @xmath345 . that the rays of this fan , which arise as the intersections of many hypersurfaces , should again be in bijection with the vertices of @xmath345 is quite unexpected . we expect an analogous statement to hold for infinite type cluster algebras . we are grateful to bernd sturmfels for suggesting this problem to us , and for advice throughout our work . in addition , we thank komei fukuda and michael joswig for their help in performing the polyhedral computations and joshua scott , richard stanley , and andrei zelevinsky for their useful comments . j. richter - gebert , b. sturmfels , t. theobald , first steps in tropical geometry , 29 pages , ` http://www.arxiv.org/math.ag/0306366 ` , to appear in `` idempotent mathematics and mathematical physics '' , proceedings vienna 2003 , ( editors g. litvinov and v. maslov ) .
tropical algebraic geometry is the geometry of the tropical semiring @xmath0 . 
 the theory of total positivity is a natural generalization of the study of matrices with all minors positive . in this paper 
 we introduce the totally positive part of the tropicalization of an arbitrary affine variety , an object which has the structure of a polyhedral fan . 
 we then investigate the case of the grassmannian , denoting the resulting fan @xmath1 . 
 we show that @xmath2 is the stanley - pitman fan , which is combinatorially the fan dual to the ( type @xmath3 ) associahedron , and that @xmath4 and @xmath5 are closely related to the fans dual to the types @xmath6 and @xmath7 associahedra . 
 these results are strikingly reminiscent of the results of fomin and zelevinsky , and scott , who showed that the grassmannian has a natural cluster algebra structure which is of types @xmath3 , @xmath6 , and @xmath7 for @xmath8 , @xmath9 , and @xmath10 . 
 we suggest a general conjecture about the positive part of the tropicalization of a cluster algebra .