A survey of the higher Stasheff-Tamari orders

A survey of the higher Stasheff-Tamari orders J¨ org Rambau and Victor Reiner – Preliminary Draft as of October 18, 2011 – Abstract The Tamari lattice, thought as a poset on the set of triangulations of a convex polygon with n vertices, generalizes to the higher Stasheff-Tamari orders on the set of triangulations of a cyclic d -dimensional polytope having n vertices. This survey discusses what is known about these orders, and what one would like to know about them. 1 Introduction One often thinks of the Tamari order as a partial order on parenthesizations, or on binary trees. But it can also be taken as an order on triangulations of any n -gon whose vertices lie in convex position. Choosing the vertices of the n -gon to lie on a parabola, or 2 -dimensional moment curve, lends itself to a beautiful geometric interpretation for the order. This interpretation generalizes to give two closely related orders on the set of triangulations of a cyclic polytope C(n,d) , which is the convex hull of any n points on the d -dimensional moment curve. These orders, called the higher Stasheff-Tamari orders HST1(n,d) and HST2(n,d) , first appeared roughly 20 years ago in the work of Kapranov and Voevodsky [ 24 , Defn. 3.3], and are somewhat mysterious. Nevertheless, they share many beautiful properties with the Tamari order. Here we survey the work on them by Edelman and Reiner [ 15 ], Rambau [ 31 ], Reiner [ 36 , § 6] Edelman, Rambau and Reiner [ 14 ], Thomas [43, 44], and most recently, Oppermann and Thomas [26]. We also discuss J¨ org Rambau University of Bayreuth, Germany, e-mail: [email protected] Victor Reiner University of Minnesota, Minneapolis, USA, e-mail: [email protected] 1 2 J¨ org Rambau and Victor Reiner work on the closely related Baues problem for subdivisions of cyclic polytopes and zonotopes, as studied by Rambau and Santos [ 33 ], Athanasiadis, Rambau and Santos [3], and Athanasiadis [2]. Along the way, we indicate which questions about them remain open. 2 Cyclic polytopes One way to realize the vertices of an n -gon in convex position is to pick the vertices as n points with distinct x -coordinates on the parametrized parabola {(t,t2):t∈R} within R2 . More generally, one can define (see [ 47 , Example 0.6]) the d -dimensional moment curve in Rdas the image of the parametrization Rνd →Rd t7→ (t,t2,,...,td).(1) Definition 2.1. The d -dimensional cyclic polytope with n vertices C(n,d) is the convex hull of any npoints νd(t1),...,νd(tn)with distinct x1-coordinates t1<t2<··· <tn.(2) We adopt the convention when d=0 that these n points are copies of the unique point of R0. An exercise in Vandermonde determinants and polynomial algebra and inequalities [ 47 , Example 0.6, Theorem 0.7, Exercise 0.8] shows that, no matter how one chooses the x1-coordinates in (2), the polytope C(n,d)has these combinatorial properties: •C(n,d) is a simplicial polytope, meaning that its boundary faces are all simplices, •C(n,d) has the same subsets of indices {i0,i1,...,ik} indexing boundary faces conv{νd(ti0),νd(ti1),...,νd(tik)} , dictated by Gale’s evenness criterion, and in particular, •C(n,d) is bd 2c -neighborly, meaning that every vertex subset of size at most d 2 spans a simplex on the boundary. In light of these properties, it is fair to talk about C(n,d) and its boundary faces indexed by sets of subscripts {i0,i1,...,ik} , without reference to the choice of x1 -coordinates in (2) . In the terminology of oriented matroid theory, the affine point configuration given by the points with homogeneous coordinates {(1,ti,t2 i,...,td i)}i=1,2,...,n realizes the alternating oriented matroid [ 9 , Cor. 8.2.10], regardless of the choice in (2). Note also that if one fixes this choice (2) , but varies the dimension d , then one has canonical projection maps π:C(n,d0)→C(n,d) for d0≥d by forgetting the A survey of the higher Stasheff-Tamari orders 3 Fig. 1 Cyclic polytopes C(7,3) , C(7,2) , C(7,1) , and C(7,0) (seven repeated points at the origin) together with the canonical projections forgetting the last coordinate. The bottom triangulation ˆ 07,2 of C(7,2), discussed in Section 3, is faintly visible as the (obscured) lower facets of C(7,3). last d0−d coordinates. Figure 1 shows the cyclic polytopes C(7,d) for d=0,1,2,3 , along with these projection maps1. Because the oriented matroid data for the affine point configuration {νd(ti)}i=1,2,...,n is independent of the choice (2) , it is also well-defined to say when a collection T of (d+1) -element subsets {i1,i2,...,id+1} indexes the maximal simplices conv{νd(ti1),...,νd(tid+1)} in a triangulation of the cyclic polytope C(n,d) . For complete discussions of the motivations and technicalities here, see Rambau [ 31 , § 2] and DeLoera, Rambau, and Santos [11, Chap. 2]. We will say more about how one encodes or characterizes the collections T of (d+1)-subsets that index triangulations of C(n,d)in Section 4. 3 The two orders The two Stasheff-Tamari orders come from thinking about how a triangulation T of C(n,d)induces a section 1 The astute reader will notice that the point configurations C(7,1) and C(7,0) are not really determined by the polytope which is their convex hull. We will tacitly use the term “polytope”, even though in certain situations, there is a point configuration in the background which is really part of the data. This becomes even more apparent in the case of cyclic zonotopes discussed in Section 8. We elaborate no further on this here, but refer to [11, Chp. 2] for a technically satisfying setup. 4 J¨ org Rambau and Victor Reiner Fig. 2 The two triangulations (green and red) of C(d+2,d)for small d, specifically, d=0: {1}versus {2} d=1: {1,3}versus {1,2},{2,3} d=2: {1,2,4},{2,3,4}versus {1,2,3},{1,3,4} d=3 : {1,2,3,4},{1,2,4,5},{2,3,4,5} versus {1,2,3,5},{1,3,4,5} , depicted here in an exploded view: the 3-simplices are moved slightly apart to clarify how they assemble. C(n,d)sT →C(n,d+1) of the projection map C(n,d+1)π →C(n,d) , defined uniquely by insisting that sT sends νd(ti)7→ νd+1(ti) , and then extending sT piecewise-linearly over each simplex in the triangulation T. From this point of view (and after staring at C(n,3) in Figure 1 for a bit), one realizes that the top and bottom elements in the usual Tamari poset correspond to the two canonical triangulations of C(n,2) that come from the “upper” and “lower” facets of C(n,3) . In general, one obtains a canonical upper (resp. lower) triangulation of C(n,d) by projecting via π:C(n,d+1)→C(n,d) the boundary facets of C(n,d+1) visible from points with large (resp. small) xd+1 coordinate. It is not hard to see that when n=d+2 , these are the only two triangulations of a cyclic polytope C(d+2,d) ; for d=0,1,2,3 , they are pictured in Figure 2. See also Figure 10 for the d=3 case. Explicit descriptions of these canonical upper and lower triangulations for general d may be found in [15, Lemma 2.3]. Definition 3.1. Given two triangulations T,T0 of the cyclic polytyope C(n,d) , say that they are related as T≤2T0 in the second higher Stasheff-Tamari order HST2(n,d) if sT(x)d+1≤sT0(x)d+1 for every point x of C(n,d) , that is, the section sTlies weakly below the section sT0with respect to their xd+1-coordinates. Definition 3.2. To define the first higher Stasheff-Tamari order HST1(n,d) on triangulations of C(n,d) , first define when T0 is obtained from T by an upward flip: this means that there exists a (d+2) -subset i1<i2<··· <id+2 whose convex hull gives a subpolytope C(d+2,d) of C(n,d) with the property that T,T0 restrict to A survey of the higher Stasheff-Tamari orders 5 Fig. 3 The (lower!) Stasheff-Tamari orders HST2(6,1) = HST1(6,1) on the set of triangulations T of the line segment C(6,1) . Instead of the triangulation T , its image under the piecewise linear section sT:C(6,1)→C(6,2)is depicted in red. the lower, upper triangulations of this C(d+2,d) , and otherwise T,T0 agree on all of their other simplices not lying in this C(d+2,d). Then define T≤1T0 in HST1(n,d) , if there is a sequence of upward flips starting with T and ending with T0 . That is, HST1(n,d) is the transitive closure of the upward flip relation. Figure 3 illustrates HST2(6,1) . It should be clear from the definitions and the above discussion that ≤1 is a weaker partial order than ≤2 , and that the lower and upper triangulations of C(n,d) give the unique minimal ˆ 0n,d and maximal ˆ 1n,d elements of HST2(n,d) . It was left open in [ 15 ], and resolved by Rambau affirmatively in [ 31 ], that these two triangulations also give unique minimal and maximal elements of HST1(n,d) . In particular, this resolves the question of bistellar connectivity for triangulations of C(n,d) : any pair of triangulations can be related by a sequence of bistellar flips (see Section 6). It is also closely related to the Generalized Baues Problem for cyclic polytopes, discussed in Section 7 below. It was shown in [ 15 ] that the two orders HST1(n,d) and HST2(n,d) are the same for d=0,1,2,3 , and this is also not hard to check that they are the same when n−d=1,2,3. This raises the following question that remains open. Open Problem 3.3. Are HST1(n,d)and HST2(n,d)the same orders? Historically, the order HST1(n,d) is the one introduced, in the different terminology of pasting schemes, by Kapranov and Voevodsky [ 24 , Def. 3.3]; the second order HST2(n,d)was defined in [15, p. 132]. 6 J¨ org Rambau and Victor Reiner The higher Stasheff-Tamari posets for d=0,1,2 are familiar objects, as we next explain. Example 3.4.For d=0 , the cyclic polytope C(n,0) is the unique point of R0 , however, it is viewed as a point configuration in which there are n different possible labels i in {1,2,...,n} for this point. A triangulation T of C(n,0) is a choice of one of these labels i , and an upward flip replaces the label i by the label i+1 . Thus HST1(n,d)and HST2(n,d)both equal the linear order 1 <2<··· <n. Example 3.5.For d=1 , the cyclic polytope C(n,1) is a line segment [t1,tn] inside R1 , however, it is viewed as a point configuration in which there are n−2 interior vertices {t2,t3,...,tn−1} . Any subset of these interior vertices determines a unique triangulation T of the line segment C(n,1) into smaller segments. A typical upward flip replaces two consecutive smaller segments [ti,tj],[tj,tk] having i<j<k with the single segment [ti,tk] , or equivalently, removes tj from the subset of interior vertices used in the triangulation. Thus HST1(n,d) and HST2(n,d) are both isomorphic to the Boolean algebra 2{t2,t3,...,tn−1}. This was illustrated for n=5 already in Figure 3, depicting HST2(6,1) = HST1(6,1) , which is isomorphic to the Boolean algebra 2{t2,t3,t4,t5}. Example 3.6.For d=2 , as mentioned above, the cyclic polytope C(n,2) is a convex n -gon. A typical upward flip starts with a triangulated sub-quadrilateral C(4,2) with four vertices i<j<k< ` which is triangulated via the two triangles {i jk,ik`} , and replaces it with the same triangulation except for using the two triangles {i j`, jk`} instead. Thus HST1(n,2) is equivalent to one of the usual definitions of the Tamari order. It is not completely obvious that HST1(n,2) = HST2(n,2) ; a proof appears in [15, Theorem 3.8]. Example 3.7.Figures 4 through 6 show pictures of HST1(6,2) , HST1(6,3) , and HST1(7,3), respectively, all supported by TOPCOM [32]. The following property, suggested by the previous examples and scrutiny of the accompanying figures, is easily deduced from the definitions. Proposition 3.8. [ 15 , Prop. 2.11] In both posets HST1(n,d),HST2(n,d) , reversal of the labelling, that is, the relabelling 17→ n, 27→ n−1, . . . , n 7→ 1 •induces a non-trivial poset automorphism for d odd, and •induces a poset anti-automorphism for d even. Scrutiny of the examples and figures also suggests the following properties, which are not as obvious, but deduced by Rambau in [31, Cor. 12.(i)]. Proposition 3.9. Given a triangulation T of C(n,d) , let |T| denote its number of maximal simplices. •For d even, |T|is constant, independent of T, equal to n−e−1 eif d =2e. • For d odd, |T| takes on all values in the range hn−e−1 e−1,n−e ei if d=2e−1 . In fact, HST1(n,d)is a ranked poset in which Thas rank n−e e−|T|. A survey of the higher Stasheff-Tamari orders 7 Fig. 4 A picture of HST1(6,2) = HST2(6,2) , similar to [ 15 , Fig. 4(a)]. Triangulations T of C(6,2) are depicted as the images of their corresponding sections sT:C(6,2)→C(6,3) , viewed from above C(6,3). Labels {j`,ik}on covering relations indicate supports of the corresponding flips as follows: the 3 -simplex {i,j,k,`} with i<j<k< ` supporting the flip has lower facets {i jk,ik`} , and upper facets {i j`, jk`}. 8 J¨ org Rambau and Victor Reiner Fig. 5 A picture of HST1(6,3) ; the labels of the covering relations indicate the support of the corresponding flip. After reading Theorem 6.6 below, the interested reader may want to find, for each of the 6 triangulations in this figure, at least one maximal chain in Figure 4 which induces it. A survey of the higher Stasheff-Tamari orders 9 Fig. 6 A picture of HST1(7,3)(data generated by TOPCOM [32]), similar to [15, Fig. 4(b)]. 16 J¨ org Rambau and Victor Reiner 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 2 3 4 5 6 71 2 3 4 5 6 7 Fig. 8 A subdivision S of C(7,2) into a green quadrangle and a blue pentagon, along with its facial interval [xS,yS]∼ =HST2(4,2)×HST2(5,2) in HST2(7,2) . The open interval (xS,yS) is homotopy equivalent to a 1 -sphere (circle). The heptagon C(7,2) is depicted with respect to coordinates on the Caratheodory curve, rather than the moment curve, for better visibility of triangles. facial intervals [x,y] , that is, those in which x=xS,y=yS are the minimum and maximum elements lying on a particular face of the associahedron, indexed by a polygonal subdivision S of the n -gon C(n,2) ; see Huguet and Tamari [ 23 ], and Pallo [ 28 ]. Figure 8 shows an example of such an interval [xS,yS] within HST2(7,2) , with in this case an isomorphism [xS,yS]∼ =HST2(4,2)×HST2(5,2). A survey of the higher Stasheff-Tamari orders 17 6 Connection to Flip Graph Connectivity The Hasse diagram for the higher Stasheff-Tamari order HST1(n,d) , considered as an undirected graph, is a special case of an important concept from discrete and computational geometry, which we discuss here: the flip graph of all triangulations and (bistellar) flips for an arbitrary affine point configuration Ain Rd. 6.1 Bistellar flips Recall that an edge in the Hasse diagram for HST1(n,d) corresponds to two triangulations T,T0 of A=C(n,d) that share almost all of the same simplices except that they restrict to the two different possible triangulations (upper and lower) of the convex hull of a certain subset A0=C(d+2,d)of cardinality d+2. It remains true generally that for d+2 points A0in Rd, there will be exactly two triangulations of their convex hull, using only vertices in A0 . It even remains true that these two triangulations will again be the set of “upper” and “lower” facets for some lifting of the points A0 in Rd to the vertices of a (d+1) -simplex in Rd+1 , but the combinatorics of these two triangulations will depend upon the signs in the unique affine dependence (up to scaling) among these points, or the oriented matroid of the affine point configuration A0; see again [11, §2.4]. Definition 6.1. Two triangulations T,T0 of the convex hull of an affine point configuration A in Rd using only vertices in A , are said to differ by a ( d -dimensional) bistellar flip if they share almost all of the same simplices, but restrict to the two possible triangulations of the convex hull of some d+2 element subset A0⊂A. More generally than the d -dimensional bistellar flips, one also allows lowerdimensional bistellar flips between two triangulations T,T0 , involving a subset A0⊂Aof cardinality e+2 whose affine span is e-dimensional; see again [11, §2.4] for the precise definitions. Figure 9 illustrates some of the variety of flips possible already for points A in R2 , with the rightmost example being lower-dimensional flip. Although the variety of possible types of flips grows in higher dimensions (see Figure 10 for one example), when A in Rd is in general position (no d+1 of its points lie on an affine hyperplane of Rd ), the flips are local modifications, that affect at most d+1 simplices on d+2 points in a triangulation. Thus, flips are important in computational geometry ( d=2 or d=3 , mostly!) as a means to improve triangulations by local modifications (see [ 17 ] for just one example or [ 16 ] and [ 10 , Chps. 3 and 9] for the low-dimensional viewpoint of Computational Geometry). In non-general position, flips can become quite large modifications. (See also [ 11 , Chp. 8] for a more detailed discussion on algorithmic issues in general dimension). We should warn the reader that there is a closely related notion of bistellar flip in the literature, which is not quite the same: bistellar equivalences for triangulations of PL-manifolds, as in the work of Pachner [ 27 ]. There one does not insist that the manifolds have a fixed embedding into space nor that the vertices in the triangulation 18 J¨ org Rambau and Victor Reiner Fig. 9 An edge flip and a vertex flip in dimension two (grey), whose combinatorics can be represented topologically by pushing a surface in dimension three (blue) through a tetrahedron (red) all the way from the lower facets to the upper facets. The rightmost figure is a lower-dimensional flip, adding vertex 4 in the middle of edge 23 (grey): its combinatorics can represented topologically by pushing a surface in dimension three (blue) through a vertical triangle (= 2 -simplex!) linked to two vertices (red). Fig. 10 In dimension three, general position flips will change the number of simplices, as in C(5,3) depicted here, which has exactly these two triangulations (exploded view). Compare with the discussion of (2,3)-Pachner moves in the survey by Stasheff in this volume [41, §4.2]. have fixed coordinates. In contrast, triangulations in our context have vertices coming from the point set A, with fixed coordinates in Rd. A survey of the higher Stasheff-Tamari orders 19 6.2 The flip connectivity question In discrete and computational geometry, one would like to use bistellar flips to explore the set of all triangulations of A , or to get to any triangulation (for example, a special desired one) from any other triangulation (for example, an obvious one, such as the popular Delaunay triangulation [ 11 , § 2.2.2]. This motivates the following definition and question. Definition 6.2. Given an affine point configuration A in Rd , its flip graph Gtri(A) has vertex set indexed by the triangulations T of the convex hull of A using only vertices in A , and edges between pairs of triangulations T,T0 whenever they differ by a bistellar flip. Question 6.3. Given an affine point configuration Ain Rd, is Gtri(A)connected? When either d≤2 , or |A|−d≤3 , it is not hard to prove that the answer is “Yes”. For higher dimensions d and point configurations A , this question tantalized researchers for quite some time until resolved negatively by Santos, first in [ 38 ], where he found a counter-example with d=6 , double-checked by computer-calculations with TOPCOM [ 32 ]. Later Santos [ 39 ] produced another counter-example d=5 and in general position, which can be turned into convex-position examples by a standard construction, the Lawrence construction [11, §5.5]. Theorem 6.4. [ 39 , Theorem 1] There is a 5 -dimensional polytope with vertex set A of cardinality 26 for which the flip graph Gtri(A)is disconnected. This should be compared with the positive results of Gelfand, Kapranov and Zelevinsky on secondary polytopes [ 19 ]. They distinguish a particularly well-behaved subgraph of Gtri(A) , which is not only connected, but even (|A| − d−1) -vertexconnected in the graph-theoretic sense, because it gives the 1 -skeleton (vertices and edges) of the (|A|−d−1) -dimensional secondary polytope. This subgraph consists of the regular triangulations or coherent triangulations (and the regular flips or coherent flips between them), namely those that arise as projections of lower facets of a lifting of the point configuration. 6.3 The flip graph of a cyclic polytope Returning to cyclic polytopes C(n,d) , it is known and not hard to see that for d=2 , all triangulations are regular/coherent. This corresponds to the fact that the Hasse diagram of the Tamari order is the 1 -skeleton of the Stasheff polytope or associahedron, which is the secondary polytope for the point configuration C(n,2) . However, for any fixed d≥3 , one can show that, asymptotically in n , most triangulations of C(n,d) are not regular/coherent, [ 11 , § 6.1], which raises that question of connectivity for their flip graphs. Theorem 6.5. [ 31 , Thm. 1.1, Cor. 1.2]. The first higher Stasheff-Tamari order HST1(n,d) is bounded, with the same bottom ˆ 0n,d and top ˆ 1n,d triangulations as the 20 J¨ org Rambau and Victor Reiner Fig. 11 The Hasse-diagram of HST1(10,6) generated by an unpublished maple package of the first author and the Stembridge posets package [42]. second higher Stasheff-Tamari order HST2(n,d) . In particular, the Hasse diagram for HST1(n,d), which is the flip graph Gtri(C(n,d)), is connected. Figure 11 shows the Hasse-diagram of HST1(10,6), a non-trivial case for which boundedness was unknown before. A survey of the higher Stasheff-Tamari orders 21 6.4 Diameter Since the flip graph Gtri(C(n,d)) is connected, it makes sense to ask for its diameter, that is, how many flips are required to reach a triangulation from any other, in the worst case. We explain here how the following structural result on HST1(n,d) leads to the exact diameter when dis odd, and diameter bounds when dis even. Theorem 6.6. [ 31 , Thm. 1.1] There is a one-to-one correspondence between equivalence classes of maximal chains in HST1(n,d) and triangulations of C(n,d+1) . Two chains are equivalent if their covering relations are flips on identical sets of d+1 -simplices. This correspondence is induced by mapping each flip in a maximal chain in HST1(n,d)to the corresponding (d+1)-simplex in C(n,d+1). Fig. 12 The connection between a chain in HST1(6,1) (represented by characteristic sections) and an element of HST1(6,2)(figures from [11, Chp. 5]). When d is odd, so that HST1(n,d) is both ranked and bounded, this determines the diameter of Gtri(C(n,d)) exactly, combining the previous result, Proposition 3.9, and the following well-known fact. Proposition 6.7. A bounded ranked poset of rank r has Hasse diagram diameter r. Proof. Every element lies in a maximal chain of length r , and hence any pair of elements are contained in a closed cyclic path of 2r edges that concatenates two such maximal chains; thus they lie at distance at most r . On the other hand, the unique bottom and top elements are at distance at least r.ut 22 J¨ org Rambau and Victor Reiner Corollary 6.8. [ 31 , Cor. 1.2] For odd d=2e−1 , the diameter of the flip graph of C(n,d)is n−e−1 e. Since a triangulation of C(n,d+1)for deven has no more simplices than there are lower facets of C(n,d+2) and no fewer simplices than there are upper facets of C(n,d+2), the same argument at least gives these bounds for the diameter. Corollary 6.9. [ 31 , Cor. 1.2] For even d=2e , the diameter of the flip graph of C(n,d)is bounded between n−e−2 eand 2n−e−2 e. 6.5 The case d=2: the rotation graph of binary trees In the case where d=2 , the above diameter bounds show that the diameter of Gtri(C(n,2)) is between n−3 and 2n−6 . However, this case has been extremely well-studied under the guise of the rotation graph on binary trees, e.g. in the work of Pallo; see the survey by Dehornoy [12] in this volume for references, and for the close connection with Thompson’s group. In particular, the above diameter bound is superseded by the following celebrated result of Sleator, Thurston, and Tarjan. Theorem 6.10. [ 40 , Thm. 2] The diameter of Gtri(C(n,2)) is, for sufficiently large values of n, exactly 2n−10. The proof that the diameter is at least 2n−10 for sufficiently large n employs the three-dimensional interpretation of flips sketched above: flipping can be seen as shifting a surface from the lower facets of a (not necessarily straight-line) tetrahedron through the tetrahedron all the way to the upper facets of the tetrahedron. Moreover, a sequence of flips can be seen as moving a surface all the way through a three-dimensional triangulation, consisting of one tetrahedron per flip and having one triangulation as the bottom and the other triangulation as the top surface. If one could show that there are triangulations of an n -gon so that the three-dimensional space between them needs at least 2n−10 tetrahedra to be triangulated, then the claim would follow. And indeed: by embedding the situation in hyperbolic geometry (where volumes of simplices are bounded!), Sleator, Tarjan, and Thurston established the lower bound along these lines. Along their way, they had to master a wealth of technical difficulties, though. No combinatorial or more intuitive proof has been given of this lower bound to date. 1 2 3 45 6 7 1 2 3 45 6 7 1 2 3 45 6 7 1 2 3 45 6 7 Fig. 13 Flipping (from left to right) to the standard triangulation with respect to vertex 7. A survey of the higher Stasheff-Tamari orders 23 On the other hand, their argument for the diameter upper bound of 2n−10 is easy enough to reproduce here. Pick an arbitrary vertex p of an n -gon with n>12 and an arbitrary triangulation T . Unless p lies in all possible interior edges, that is, its degree degT(p) in the interior edge graph of T is n−3 , we can find a flip that increases the degree of p by one. (In that case, not all adjacent triangles in the star of p in T can form a non-convex quadrilateral.) Thus, we need at most n−3−degT(p) flips to transform T into the unique triangulation with degT(p) = n−3 , the standard triangulation with respect to p . The same holds for any other triangulation T0 , so that the flip distance dist(T,T0)between Tand T0is at most dist(T,T0)≤min p2n−6−degT(p)−degT0(p)(3) If one uses the worst case of this relation as an upper bound, one can not get past 2n−6 . However, symmetry comes to our aid: Since every triangulation of an n -gon has n−3 interior edges, the average interior-edge degree of a vertex is (2n−6)/n=2−6/n. Summarized: dist(T,T0)≤2n−6−2+6/n−2+6/n=2n−10 +12/n.(4) Since n>12 and the distance is integral, the claim follows. 7 Subdivisions and the Baues problem We have already seen, in the discussion of M ¨ obius functions for HST2(n,d) in Section 5, the relevance of polytopal subdivisions S of C(n,d) which are coarser than triangulations, and the importance of the refinement ordering on them. The flip graph Gtri(A) is a one-dimensional object built from these triangulations and bistellar flips relating them. It turns out that bistellar flips can also be thought of as subdivisions which are only slightly coarser than triangulations, namely those that have exactly two refinements, both triangulations. They form part of a larger structure, the Baues poset, built from all subdivisions. The connectivity question for Gtri(A) is closely related to the question of homotopy type for this Baues poset. We discuss this somewhat informally here – see [36] for further discussion and references. 7.1 Subdvisions and secondary polytopes Polytopal subdivisions of the convex hull of a point configuration A , using only vertices in A , already appeared naturally in the work of Gelfand, Kapranov, and Zelevinsky [ 19 , 20 ] on the secondary polytope of A that was discussed in Section 6.2: the face poset of the second polytope is exactly the poset of all regular polytopal subdivisions S of the convex hull of A , ordered by refinement. See Figure 14 for 24 J¨ org Rambau and Victor Reiner the example of a pentagon (isomorphic to C(5,2) ). See also [ 11 , Chp. 5] for a more elementary introduction into this theory. Fig. 14 The refinement poset of a five-gon is isomorphic to the face lattice of its secondary polytope (in this case also a five-gon); figures from [11, Chp. 5]. 2 4 (134) (124) (1234) (14) 31 Fig. 15 A path in a tetrahedron and the corresponding cell in the square (figure from [29]). 7.2 Baues’s original problem Meanwhile, a conjecture of Baues in the model theory of loop spaces [5] motivated Billera, Kapranov, and Sturmfels [ 6 ] to generalize this subdivision poset. We give here a rough idea of Baues’s goal, before explaining their generalization. The loop space ΩX of a base-pointed topological space (X,x) has elements which are closed paths γ in X starting and ending at x , equipped with a certain topology. If X happens to come from a simplicial complex, that is, it is glued from simplices, then one might hope to model ΩX via some type of cell complex; this idea goes back to J. F. Adams [1] who applied it to compute the homology of ΩX. To this end, consider a piece of a closed path γ inside a d -simplex, with vertices numbered {0,1,2,...,d} , with γ entering each visited (open) face at its minimal vertex and exiting at its maximal vertex d . Moreover, we require that it enters the simplex at vertex 0 and exits at vertex d . The various substantially distinct options A survey of the higher Stasheff-Tamari orders 25 for how this piece of γ can traverse the simplex (in terms of visited open faces) can be modeled by a (d−1) -cube: the extreme possibilities are edge paths with increasing vertex labels in the simplex, which biject with vertices of a cube: the vertices 1 through d−1 of the simplex that are visited by γ determine the ones in the coordinates of the vertex of the cube. All intermediate options where γ can wander specify in a rather obvious way faces of the cube, where a path meeting the interior of the simplex corresponds to the improper face of the cube, that is, the whole cube. Thus, one might think that the loop space of a simplicial complex can be modeled by a cubical complex. As always, there are technical subtleties, one of which is that a certain structure must have the homotopy type of a sphere for things to work. Baues conjectured that this structure actually always does have the homotopy type of a sphere. Fig. 16 How cellular strings in the bipyramid project to compatible subdivisions of the line; the rightmost set of faces is not a cellular string, because the projections of those faces overlap (figure derived from a figure in [29, Chap. 1]). 7.3 Cellular strings and the generalized Baues problem Billera, Kapranov, and Sturmfels [ 6 ] discovered that the structure Baues was after is an example of the following construction. Definition 7.1. Consider a d0 -dimensional polytope P and linear functional Rd0π →R1 taking distinct values π(v)6=π(v0) whenever v,v0 are vertices lying on an edge of P . Say that a subdivision of the line segment π(P) in R1 into consecutive intervals [v0,v1],[v1,v2],...,[v`−1,v`] is π -compatible 3 if, for each i=1,2,...,` , one can 3 The original term “ π -induced” in [ 7 , 6 ] was modified in [ 11 ] to “ π -compatible” because, in general, there are many subdivisions that are projections of faces under π , induced by the corresponding cellular strings and π, not πalone. 32 J¨ org Rambau and Victor Reiner S of B(n,0) = 2{1,2,...,n} , is a choice of such a label, and is considered a zonotopal tiling of Z(n,0). Alternatively, it gives a section of the map Z(n,n)π →Z(n,0). Note also that the covering relation between subsets SlS0 in B(n,0) corresponds to two vertices lying along an edge of the n-cube. Example 8.6.When d=1 , each vector ν1(ti) = ti points along the ( x1 -)axis of R1 , and Z(n,1) is the line segment whose two endpoints vmin,vmax are ±(t1+··· +tn) . A tight zonotopal tiling of Z(n,1)is a sequence of intervals [vmin,vmin +2tw1], [vmin +2tw1,vmin +2tw1+2tw2], ..., [vmin +2tw1+2tw2+···+2twn−1,vmax] corresponding to a permutation w= (w1,...,wn) in Sn , or an element of B(n,1) ; see Example 8.2. On the other hand, such permutations or elements of B(n,1) correspond to maximal chains in B(n,0) , that is, sequences of nested subsets as in (5) , and hence by our observation for d=0 , to edge-paths in the cube Z(n,n) which proceed in a monotone fashion from the vertex labelled by the empty set ∅ to the vertex labelled by {1,2,...,n} . In other words, they give sections of the map Z(n,n)π →Z(n,1) . See Figure 21 and following for some examples of such edges paths with n=3. Note also that covering relation between two permutations wlw0 in B(n,1) corresponds to two monotone edge paths in the cube Z(n,n) that differ only in two adjacent steps that proceed in opposite ways around a quadrilateral face of the cube Example 8.7.Again, things become interesting when d=2. Now the vectors ν2(ti) in R2generate a zonotopal polygon Z(n,2), that is, a centrally symmetric 2n-gon. An element of B(n,2) can be thought of as a maximal chain of permutations in B(n,1) as in (7) , up to a certain equivalence relation. It is possible to model this equivalence relation in at least two ways. One way considers the associated pseudoline arrangement or wiring diagram, as in Figure 19, whose vertical slices record the permutations in the chain as the ordering of the strands. These diagrams are considered only up to the equivalence relation of isotopies in the plane that never allow one strand to slide over the crossing of two other strands. The other way considers each permutation wi in the chain as a monotone edge path in the cube, and each covering relation wilwi+1 in the chain as giving a quadrilateral face of the cube on which the two paths take two adjacent steps that disagree. The union of all such quadrilateral faces is a 2 -dimensional surface inside the cube Z(n,n) , which is a section of the map Z(n,n)→Z(n,2). The concordance between these two models is that the quadrilateral faces in this 2 -dimensional surface map under π to a tight zonotopal tiling of the 2n -gon Z(n,2) . This tiling can be recovered as the planar dual graph to the graph given by the pseudoline arrangement, considered as having vertices only at the strand crossings; see Figure 19. A survey of the higher Stasheff-Tamari orders 33 Fig. 19 An element of B(4,2) derived from a maximal chain of permutations in B(4,1) , the weak Bruhat order on S4 . The chain of permutations (colored from red to cyan) leads to an arrangement of pseudolines, also called a wiring diagram: horizontal slices have the strands ordered as in the permutations in the chain. The planar dual of the pseudoline graph can be drawn as a tight subdivision of the zonotope Z(4,2) , in which the pseudoline strand i for i=1,2,3,4 is dual to the edges of the tiles in the parallelism class labelled by i . Moreover, the chain of permutations can be recovered in the zonotopal tiling as a sequence of monotone paths (colored from red to cyan) with covering relations coming from “flipping” the paths “upwards” through a quadrilateral. This picture continues. The work of Thomas [ 44 , Prop. 2.1], Ziegler [ 46 , Theorem 4.1] shows that an element of B(n,d) can be thought of as unions of d -dimensional faces inside the cube Z(n,n) , corresponding to the image of a section of the map Z(n,n)π →Z(n,d), projecting to a tight zonotopal subdivision of Z(n,d). One can furthermore show that if one instead associates to these tight zonotopal subdivisions S of Z(n,d) a section sS of the map Z(n,d+1)π →Z(n,d) , then one has S≤S0 in the higher Bruhat order B⊆(n,d) exactly when sS(x)d+1≤sS0(x)d+1 for all xin Z(n,d); see Figure 20 for this picture of B⊆(4,2). Analogously to the situation for cyclic polytopes C(n,d) , these tight zonotopal subdivisions and the edges between them in the Hasse diagram for B(n,d) are special cases of the more general notion of a zonotopal subdivision of Z(n,d) , which is 34 J¨ org Rambau and Victor Reiner Fig. 20 A picture of B(4,2) with elements drawn as the sections of zonotopal tilings of Z(4,2) in Z(4,3) , partially ordered by height; it can be seen how the sections, on their way to the top, submerge more and more points. Each chain can be built by stacking cubes, and the cubes corresponding to a chain form a zonotopal tiling of Z(4,3), which represents an element of B(4,3). A survey of the higher Stasheff-Tamari orders 35 a π -compatible subdivision for the projection Z(n,n)π →Z(n,d) . There is again a Baues poset of all such subdivisions, ordered by refinement, and the Baues problem asks for its homotopy type. Athanasiadis [ 2 ] investigated the Baues problem for all of the canonical projections Z(n,d0)π →Z(n,d), as in Figure 18. Theorem 8.8. [ 2 , Thm. 1.1] For all d0>d , the generalized Baues poset of the canonical projection from Z(n,d0)to Z(n,d)has the homotopy type of a d0−d−1sphere. 8.3 The map from higher Bruhat to higher Stasheff-Tamari orders The similarity of the description between the higher Bruhat orders B(n,k) in the last section should make their analogy to the higher Stasheff-Tamari orders HST1(n,d) apparent. Tightening the connection, Kapranov and Voevodsky [ 24 ] claimed, and later Rambau [ 31 ] proved, that there actually is a poset map between them. Later, Thomas shed more light on this connection in [ 44 , § 4] (see Figures 21 through 24 for an illustration). Theorem 8.9. [31, Cor. 8.16]. There is an order-preserving map B(n,k)f →HST1(n+2,k+1). In low dimensions, the map fis familiar. Example 8.1 noted the isomorphisms B(n,0) = 2{1,2,...,n}∼ =HST1(n+2,1). In the next dimension up, the map B(n,1)f →HST1(n+2,2) is the same as the map from the weak Bruhat order on Sn to the Tamari order on triangulations of C(n+2,2) discussed in the survey by Reading [ 35 , § 1] in this volume 5 . To describe it in our geometric setting, one must assign a triangulation of C(n+2,2) to each permutation w in Sn , or to each monotone edge path in the n -cube. To this end, think of C(n+2,2) as labeled by 0,1,2,...,n+1 , with {0,n+1} its only upper edge. In the order of the permutation w , cut off any remaining vertex i of C(n+2,2) by inserting the diagonal from its left to its right neighbor. Once all vertices 0<i<n+1 have been cut off, the set of inserted diagonals forms a triangulation. Note that two distinct permutations can map to the same triangulation because i,j that are adjacent in the permutation but not adjacent during the cut-off procedure can be cut off in an arbitrary order. Compare this with the description of this map in the survey by Reading [ 35 , § 1], and in particular, compare [35, Figure 3], with Figures 22 through 24 below. This f extends (modulo technical details) to a map B(n,d)f →HST1(n+2,d+1) via induction on d. Elements of B(n,d)are equivalence classes of maximal chains 5 This map also appears implicitly in the survey by Hohlweg [ 21 ], where it is explained how to embed the associahedron in such a way that its normal fan coarsens that of the permutohedron. 36 J¨ org Rambau and Victor Reiner Fig. 21 Each permutation in B(3,1) corresponds to a monotone path in the 3 -cube, which induces a triangulation of C(5,2) by using the order in which the coordinates change as the order in which the vertices 1,2,3 are cut-off by the triangulation. Note that this can be interpreted as an upflip sequence in HST1(5,1). Thus, what we see here is the flip map Tflip from [31]. Fig. 22 A different monotone path can lead to an identical triangulation. Fig. 23 A different monotone path can also lead to a different triangulation. A survey of the higher Stasheff-Tamari orders 37 Fig. 24 Monotone paths that differ by a “face flip” (that is, the corresponding permutations are connected by an inversion) lead to triangulations that are either identical or are connected by a bistellar flip. Fig. 25 Illustration of the inductive structure of the map from higher Bruhat orders to higher Stasheff-Tamari orders: A zonotopal tiling of Z(4,2) (the one from Figure 19) can be traversed upwards by monotone paths (colored from red to cyan), which map to triangulations of C(6,2) that form a chain (from red to cyan) inducing a triangulation of C(6,3) consisting of the flip simplices in the chain – determining an element of HST1(6,3). c=c1lc2l··· of elements ci in B(n,d−1) . Each f(ci) in HST1(n+2,d) is already defined by induction, and thereby gives a sequence of triangulations of C(n+2,d) 38 J¨ org Rambau and Victor Reiner f(c1)≤f(c2)≤ ··· (8) It can be shown that for each i , either f(ci) = f(ci+1) or f(ci)lf(ci+1) in the order HST1(n+2,d) . Hence, after eliminating duplicates, the sequence (8) gives a maximal chain in HST1(n+2,d) , and therefore an element of HST1(n+2,d+1) by Theorem 6.6. This inductive construction is illustrated in Figure 25. The results summarized in this section all required technical formal proofs, for which we refrain from presenting any details. However, we close with one problem on the above map f, suggested by an assertion from the original paper of Kapranov and Voevodsky [24, Theorem 4.10], but which has so far remained unproven. Open Problem 8.10. Prove that the map B(n,d)f →HST1(n+2,d+1) is surjective. 9 Enumeration We close with an enumerative question: How large are the posets HST1(n,d),HST2(n,d) , that is, how many triangulations are there of the cyclic polytope C(n,d)? A few mostly trivial results in this direction are known, such as •C(n,0),C(n,1),C(n,2)have n,2n−2,1 n−12(n−2) n−2triangulations, respectively, •C(n,n−1),C(n,n−2),C(n,n−3), have 1,2,ntriangulations, respectively. The following nontrivial result was proven by Azaola and Santos [4]. Theorem 9.1. [4] The number of triangulations of C(n,n−4)is ((n+4)·2n−4 2−n for n even, and 3n+11 2·2n−5 2−n for n odd. Another interesting unsolved problem is the following. Open Problem 9.2. Count the triangulations of C(n,3). How about computer-based enumeration? Table 1 below compiles a few results achieved by the general purpose enumeration program for triangulations TOPCOM [ 32 ]. With special purpose codes it should be possible to generate more numbers that can be used to check conjectural enumeration formulas. References 1. J. F. Adams, “On the cobar construction”, Proceedings of the National Academy of Science 42 (1956) 409–412. 2. C. Athanasiadis, “Zonotopal subdivisions of cyclic zonotopes”, Geometriae Dedicata 86 (2001) 37–57. A survey of the higher Stasheff-Tamari orders 39 c\d: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 4 4 8 14 25 40 67 102 165 244 387 562 881 1264 1967 5 5 16 42 138 357 1233 3278 12589 35789 159613 499900 2677865 9421400 62226044 6 6 32 132 972 4824 51676 340560 6429428 7 7 64 429 8477 96426 5049932 132943239 8 8 128 1430 89405 2800212 9 9 256 4862 1119280 116447760 10 10 516 16796 16384508 11 11 1028 58786 276961252 Table 1 Some computations done with TOPCOM [ 32 ] for some dimensions d and some codimensions c:=n−d ; the computation of the largest numbers in the table for C(13,6) and C(14,3) needed around 40 GB of main memory. 3. C. Athanasiadis, J. Rambau, and F. Santos, “The Generalized Baues Problem for cyclic polytopes II”, Publications De l’Institut Mathematique, Belgrade 66 (1999) 3–15. 4. M. Azaola and F. Santos, “The number of triangulations of the cyclic polytope C(n,n−4) ”, Discrete Comput. Geom. 27 (2002) 29–48, Geometric combinatorics (San Francisco, CA/Davis, CA, 2000). 5. H. J. Baues, “Geometry of loop spaces and the cobar construction”, Memoirs of the American Mathematical Society 25 (1980) 1–171. 6. L. J. Billera, M. M. Kapranov, and B. Sturmfels, “Cellular strings on polytopes”, Proceedings of the American Mathematical Society 122 (1994) 549–555. 7. L. J. Billera and B. Sturmfels, “Fiber polytopes”, Annals of Mathematics 135 (1992) 527–549. 8. A. Bj ¨ orner, “Topological methods”, in Handbook of Combinatorics, R. L. Graham, M. Gr¨ otschel, and L. Lov´ asz, eds., North Holland, Amsterdam, 1995, 1819–1872. 9. A. Bj ¨ orner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler, Oriented matroids, second ed., Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge University Press, Cambridge, 1999. 10. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008. 11. J. De Loera, J. Rambau, and F. Santos, Triangulations – Structures for Applications and Algorithms, Algorithms and Computation in Mathematics, vol. 25, Springer, 2010. 12. P. Dehornoy, “Tamari lattices and the symmetric Thompson monoid”, in this volume, 2011. 13. T. K. Dey, “On counting triangulations in ddimensions”, Comput. Geom. 3(1993) 315–325. 14. P. Edelman, V. Reiner, and J. Rambau, “On subdivision posets of cyclic polytopes”, European Journal of Combinatorics 21 (2000) 85–101. 15. P. H. Edelman and V. Reiner, “The higher Stasheff-Tamari posets”, Mathematika 43 (1996) 127–154. 16. H. Edelsbrunner, Geometry and topology for mesh generation, Cambridge Monographs on Applied and Computational Mathematics, vol. 7, Cambridge University Press, Cambridge, 2001. 17. H. Edelsbrunner and N. R. Shah, “Incremental topological flipping works for regular triangulations”, in Proceedings of the 8th annual ACM Symposium on Computational Geometry, ACM press, 1992, 43–52. 18. S. Felsner and H. Weil, “A theorem on higher Bruhat orders”, Discrete & Computational Geometry 23 (2000) 121–127. 19. I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, “Discriminants of polynomials in several variables and triangulations of Newton polyhedra”, Leningrad Mathematical Journal 2 (1991) 449–505. 40 J¨ org Rambau and Victor Reiner 20. ,Discriminants, Resultants, and Multidimensional Determinants, Mathematics: Theory & Applications, Birkh¨ auser, Boston, 1994. 21. C. Hohlweg, “Permutahedra and associahedra: Generalized associahedra from the geometry of finite reflection groups”, in this volume, 2011. 22. S. Huang and D. Tamari, “Problems of associativity: A simple proof for the lattice property vof systems ordered by a semi-associative law”, J. Combinatorial Theory Ser. A 13 (1972) 7–13. 23. D. Huguet and D. Tamari, “La structure poly ´ edrale des complexes de parenth ´ esages”, J. Combin. Inform. System Sci. 3(1978) 69–81. 24. M. M. Kapranov and V. A. Voevodsky, “Combinatorial-geometric aspects of polycategory theory: pasting schemes and higher Bruhat orders (list of results)”, Cahiers de Topologie et G´ eom´ etrie diff´ erentielle cat´ egoriques 32 (1991) 11–27. 25. Y. I. Manin and V. V. Schechtman, “Arrangements of hyperplanes, higher braid groups and higher Bruhat orders”, Advanced Studies in Pure Mathematics 17 (1989) 289–308. 26. S. Oppermann and H. Thomas, “Higher dimensional cluster combinatorics and representation theory”, math arXiv (2010) ?? 27. U. Pachner, “P.L. homeomorphic manifolds are equivalent by elementary shellings”, European J. Combin. 12 (1991) 129–145. 28. J. M. Pallo, “An algorithm to compute the M ¨ obius function of the rotation lattice of binary trees”, RAIRO Inform. Th´ eor. Appl. 27 (1993) 341–348. 29. J. Rambau, Projections of Polytopes and Polyhedral Subdivisions, Berichte aus der Mathematik, Shaker, Aachen, 1996, Dissertation, TU Berlin. 30. , “A suspension lemma for bounded posets”, J. Combin. Theory Ser. A 80 (1997) 374–379. 31. , “Triangulations of cyclic polytopes and higher Bruhat orders”, Mathematika 44 (1997) 162–194. 32. , “TOPCOM: Triangulations of point configurations and oriented matroids”, in Mathematical Software—ICMS 2002, A. M. Cohen, X.-S. Gao, and N. Takayama, eds., World Scientific, 2002, 330–340. 33. J. Rambau and F. Santos, “The Generalized Baues Problem for cyclic polytopes I”, European Journal of Combinatorics 21 (2000) 65–83. 34. J. Rambau and G. M. Ziegler, “Projections of polytopes and the Generalized Baues Conjecture”, Discrete & Computational Geometry 16 (1996) 215–237. 35. N. Reading, “From the Tamari lattice to Cambrian lattices and beyond”, in this volume, 2011. 36. V. Reiner, “The generalized Baues problem”, in New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996–97), Math. Sci. Res. Inst. Publ., vol. 38, Cambridge Univ. Press, Cambridge, 1999, 293–336. 37. J. Richter-Gebert and G. M. Ziegler, “Zonotopal tilings and the Bohne-Dress theorem”, in Proceedings “Jerusalem Combinatorics ’93”, H. Barcelo and G. Kalai, eds., Contemporary Mathematics, vol. 178, American Mathematical Society, 1994, 211–232. 38. F. Santos, “A point configuration whose space of triangulations is disconnected”, Journal of the American Mathematical Society 13 (2000) 611–637. 39. , “Non-connected toric Hilbert schemes”, Mathematische Annalen 332 (2005) 645–665. 40. D. D. Sleator, R. E. Tarjan, and W. P. Thurston, “Rotation distance, triangulations, and hyperbolic geometry”, Journal of the American Mathematical Society 1(1988) 647–681. 41. J. D. Stasheff, “How i ‘met’ Dov Tamari”, in this volume, 2011. 42. J. R. Stembridge, “A Maple package for posets”, Free software, available online, 2008. 43. H. Thomas, “New combinatorial descriptions of the triangulations of cyclic polytopes and the second higher Stasheff-Tamari posets”, Order 19 (2002) 327–342. 44. , “Maps between higher Bruhat orders and higher Stasheff-Tamari posets”, in Formal Power Series and Algebraic Combinatorics Conference – Link¨ oping, Sweden, 2003, 2003. 45. , “The Tamari lattice as it arises in quiver representations”, in this volume, 2011. 46. G. M. Ziegler, “Higher Bruhat orders and cyclic hyperplane arrangements”, Topology 32 (1993) 259–279. 47. G. M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995.