A survey of the higher Stasheff-Tamari orders

A su ey o he highe S ashe -Tama i o de s J¨ o g Rambau and Vic o Reine – P elimina y D a as o Oc obe 18, 2011 – Abs ac The Tama i la ice, hough as a pose on he se o iangula ions o a con ex polygon wi h n e ices, gene alizes o he highe S ashe -Tama i o de s on he se o iangula ions o a cyclic d -dimensional poly ope ha ing n e ices. This su ey discusses wha is known abou hese o de s, and wha one would like o know abou hem. 1 In oduc ion One o en hinks o he Tama i o de as a pa ial o de on pa en hesiza ions, o on bina y ees. Bu i can also be aken as an o de on iangula ions o any n -gon whose e ices lie in con ex posi ion. Choosing he e ices o he n -gon o lie on a pa abola, o 2 -dimensional momen cu e, lends i sel o a beau i ul geome ic in e p e a ion o he o de . This in e p e- a ion gene alizes o gi e wo closely ela ed o de s on he se o iangula ions o a cyclic poly ope C(n,d) , which is he con ex hull o any n poin s on he d -dimensional momen cu e. These o de s, called he highe S ashe -Tama i o de s HST1(n,d) and HST2(n,d) , i s appea ed oughly 20 yea s ago in he wo k o Kap ano and Voe odsky [ 24 , De n. 3.3], and a e somewha mys e ious. Ne e heless, hey sha e many beau i ul p ope ies wi h he Tama i o de . He e we su ey he wo k on hem by Edelman and Reine [ 15 ], Rambau [ 31 ], Reine [ 36 , § 6] Edelman, Rambau and Reine [ 14 ], Thomas [43, 44], and mos ecen ly, Oppe mann and Thomas [26]. We also discuss J¨ o g Rambau Uni e si y o Bay eu h, Ge many, e-mail: joe g. ambau@uni-bay eu h.de Vic o Reine Uni e si y o Minneso a, Minneapolis, USA, e-mail: [email p o ec ed] 1 2 J¨ o g Rambau and Vic o Reine wo k on he closely ela ed Baues p oblem o subdi isions o cyclic poly opes and zono opes, as s udied by Rambau and San os [ 33 ], A hanasiadis, Rambau and San os [3], and A hanasiadis [2]. Along he way, we indica e which ques ions abou hem emain open. 2 Cyclic poly opes One way o ealize he e ices o an n -gon in con ex posi ion is o pick he e ices as n poin s wi h dis inc x -coo dina es on he pa ame ized pa abola {( , 2): ∈R} wi hin R2 . Mo e gene ally, one can de ine (see [ 47 , Example 0.6]) he d -dimensional momen cu e in Rdas he image o he pa ame iza ion Rνd →Rd 7→ ( , 2,,..., d).(1) De ini ion 2.1. The d -dimensional cyclic poly ope wi h n e ices C(n,d) is he con ex hull o any npoin s νd( 1),...,νd( n)wi h dis inc x1-coo dina es 1< 2<··· < n.(2) We adop he con en ion when d=0 ha hese n poin s a e copies o he unique poin o R0. An exe cise in Vande monde de e minan s and polynomial algeb a and inequali ies [ 47 , Example 0.6, Theo em 0.7, Exe cise 0.8] shows ha , no ma e how one chooses he x1-coo dina es in (2), he poly ope C(n,d)has hese combina o ial p ope ies: •C(n,d) is a simplicial poly ope, meaning ha i s bounda y aces a e all simplices, •C(n,d) has he same subse s o indices {i0,i1,...,ik} indexing bounda y aces con {νd( i0),νd( i1),...,νd( ik)} , dic a ed by Gale’s e enness c i e ion, and in pa icula , •C(n,d) is bd 2c -neighbo ly, meaning ha e e y e ex subse o size a mos d 2 spans a simplex on he bounda y. In ligh o hese p ope ies, i is ai o alk abou C(n,d) and i s bound- a y aces indexed by se s o subsc ip s {i0,i1,...,ik} , wi hou e e ence o he choice o x1 -coo dina es in (2) . In he e minology o o ien ed ma oid heo y, he a ine poin con igu a ion gi en by he poin s wi h homogeneous coo dina es {(1, i, 2 i,..., d i)}i=1,2,...,n ealizes he al e na ing o ien ed ma oid [ 9 , Co . 8.2.10], ega dless o he choice in (2). No e also ha i one ixes his choice (2) , bu a ies he dimension d , hen one has canonical p ojec ion maps π:C(n,d0)→C(n,d) o d0≥d by o ge ing he A su ey o he highe S ashe -Tama i o de s 3 Fig. 1 Cyclic poly opes C(7,3) , C(7,2) , C(7,1) , and C(7,0) (se en epea ed poin s a he o igin) oge he wi h he canonical p ojec ions o ge ing he las coo dina e. The bo om iangula ion ˆ 07,2 o C(7,2), discussed in Sec ion 3, is ain ly isible as he (obscu ed) lowe ace s o C(7,3). las d0−d coo dina es. Figu e 1 shows he cyclic poly opes C(7,d) o d=0,1,2,3 , along wi h hese p ojec ion maps1. Because he o ien ed ma oid da a o he a ine poin con igu a ion {νd( i)}i=1,2,...,n is independen o he choice (2) , i is also well-de ined o say when a collec- ion T o (d+1) -elemen subse s {i1,i2,...,id+1} indexes he maximal simplices con {νd( i1),...,νd( id+1)} in a iangula ion o he cyclic poly ope C(n,d) . Fo comple e discussions o he mo i a ions and echnicali ies he e, see Rambau [ 31 , § 2] and DeLoe a, Rambau, and San os [11, Chap. 2]. We will say mo e abou how one encodes o cha ac e izes he collec ions T o (d+1)-subse s ha index iangula ions o C(n,d)in Sec ion 4. 3 The wo o de s The wo S ashe -Tama i o de s come om hinking abou how a iangula ion T o C(n,d)induces a sec ion 1 The as u e eade will no ice ha he poin con igu a ions C(7,1) and C(7,0) a e no eally de e mined by he poly ope which is hei con ex hull. We will aci ly use he e m “poly ope”, e en hough in ce ain si ua ions, he e is a poin con igu a ion in he backg ound which is eally pa o he da a. This becomes e en mo e appa en in he case o cyclic zono opes discussed in Sec ion 8. We elabo a e no u he on his he e, bu e e o [11, Chp. 2] o a echnically sa is ying se up. 4 J¨ o g Rambau and Vic o Reine Fig. 2 The wo iangula ions (g een and ed) o C(d+2,d) o small d, speci ically, d=0: {1} e sus {2} d=1: {1,3} e sus {1,2},{2,3} d=2: {1,2,4},{2,3,4} e sus {1,2,3},{1,3,4} d=3 : {1,2,3,4},{1,2,4,5},{2,3,4,5} e sus {1,2,3,5},{1,3,4,5} , depic ed he e in an exploded iew: he 3-simplices a e mo ed sligh ly apa o cla i y how hey assemble. C(n,d)sT →C(n,d+1) o he p ojec ion map C(n,d+1)π →C(n,d) , de ined uniquely by insis ing ha sT sends νd( i)7→ νd+1( i) , and hen ex ending sT piecewise-linea ly o e each simplex in he iangula ion T. F om his poin o iew (and a e s a ing a C(n,3) in Figu e 1 o a bi ), one ealizes ha he op and bo om elemen s in he usual Tama i pose co espond o he wo canonical iangula ions o C(n,2) ha come om he “uppe ” and “lowe ” ace s o C(n,3) . In gene al, one ob ains a canonical uppe ( esp. lowe ) iangula ion o C(n,d) by p ojec ing ia π:C(n,d+1)→C(n,d) he bounda y ace s o C(n,d+1) isible om poin s wi h la ge ( esp. small) xd+1 coo dina e. I is no ha d o see ha when n=d+2 , hese a e he only wo iangula ions o a cyclic poly ope C(d+2,d) ; o d=0,1,2,3 , hey a e pic u ed in Figu e 2. See also Figu e 10 o he d=3 case. Explici desc ip ions o hese canonical uppe and lowe iangula ions o gene al d may be ound in [15, Lemma 2.3]. De ini ion 3.1. Gi en wo iangula ions T,T0 o he cyclic poly yope C(n,d) , say ha hey a e ela ed as T≤2T0 in he second highe S ashe -Tama i o de HST2(n,d) i sT(x)d+1≤sT0(x)d+1 o e e y poin x o C(n,d) , ha is, he sec ion sTlies weakly below he sec ion sT0wi h espec o hei xd+1-coo dina es. De ini ion 3.2. To de ine he i s highe S ashe -Tama i o de HST1(n,d) on i- angula ions o C(n,d) , i s de ine when T0 is ob ained om T by an upwa d lip: his means ha he e exis s a (d+2) -subse i1<i2<··· <id+2 whose con ex hull gi es a subpoly ope C(d+2,d) o C(n,d) wi h he p ope y ha T,T0 es ic o A su ey o he highe S ashe -Tama i o de s 5 Fig. 3 The (lowe !) S ashe -Tama i o de s HST2(6,1) = HST1(6,1) on he se o iangula ions T o he line segmen C(6,1) . Ins ead o he iangula ion T , i s image unde he piecewise linea sec ion sT:C(6,1)→C(6,2)is depic ed in ed. he lowe , uppe iangula ions o his C(d+2,d) , and o he wise T,T0 ag ee on all o hei o he simplices no lying in his C(d+2,d). Then de ine T≤1T0 in HST1(n,d) , i he e is a sequence o upwa d lips s a ing wi h T and ending wi h T0 . Tha is, HST1(n,d) is he ansi i e closu e o he upwa d lip ela ion. Figu e 3 illus a es HST2(6,1) . I should be clea om he de ini ions and he abo e discussion ha ≤1 is a weake pa ial o de han ≤2 , and ha he lowe and uppe iangula ions o C(n,d) gi e he unique minimal ˆ 0n,d and maximal ˆ 1n,d elemen s o HST2(n,d) . I was le open in [ 15 ], and esol ed by Rambau a i ma i ely in [ 31 ], ha hese wo iangula ions also gi e unique minimal and maximal elemen s o HST1(n,d) . In pa icula , his esol es he ques ion o bis ella connec i i y o iangula ions o C(n,d) : any pai o iangula ions can be ela ed by a sequence o bis ella lips (see Sec ion 6). I is also closely ela ed o he Gene alized Baues P oblem o cyclic poly opes, discussed in Sec ion 7 below. I was shown in [ 15 ] ha he wo o de s HST1(n,d) and HST2(n,d) a e he same o d=0,1,2,3 , and his is also no ha d o check ha hey a e he same when n−d=1,2,3. This aises he ollowing ques ion ha emains open. Open P oblem 3.3. A e HST1(n,d)and HST2(n,d) he same o de s? His o ically, he o de HST1(n,d) is he one in oduced, in he di e en e minol- ogy o pas ing schemes, by Kap ano and Voe odsky [ 24 , De . 3.3]; he second o de HST2(n,d)was de ined in [15, p. 132]. 6 J¨ o g Rambau and Vic o Reine The highe S ashe -Tama i pose s o d=0,1,2 a e amilia objec s, as we nex explain. Example 3.4.Fo d=0 , he cyclic poly ope C(n,0) is he unique poin o R0 , howe e , i is iewed as a poin con igu a ion in which he e a e n di e en possible labels i in {1,2,...,n} o his poin . A iangula ion T o C(n,0) is a choice o one o hese labels i , and an upwa d lip eplaces he label i by he label i+1 . Thus HST1(n,d)and HST2(n,d)bo h equal he linea o de 1 <2<··· <n. Example 3.5.Fo d=1 , he cyclic poly ope C(n,1) is a line segmen [ 1, n] inside R1 , howe e , i is iewed as a poin con igu a ion in which he e a e n−2 in e io e ices { 2, 3,..., n−1} . Any subse o hese in e io e ices de e mines a unique iangula ion T o he line segmen C(n,1) in o smalle segmen s. A ypical upwa d lip eplaces wo consecu i e smalle segmen s [ i, j],[ j, k] ha ing i<j<k wi h he single segmen [ i, k] , o equi alen ly, emo es j om he subse o in e io e ices used in he iangula ion. Thus HST1(n,d) and HST2(n,d) a e bo h isomo phic o he Boolean algeb a 2{ 2, 3,..., n−1}. This was illus a ed o n=5 al eady in Figu e 3, depic ing HST2(6,1) = HST1(6,1) , which is isomo phic o he Boolean algeb a 2{ 2, 3, 4, 5}. Example 3.6.Fo d=2 , as men ioned abo e, he cyclic poly ope C(n,2) is a con ex n -gon. A ypical upwa d lip s a s wi h a iangula ed sub-quad ila e al C(4,2) wi h ou e ices i<j<k< ` which is iangula ed ia he wo iangles {i jk,ik`} , and eplaces i wi h he same iangula ion excep o using he wo iangles {i j`, jk`} ins ead. Thus HST1(n,2) is equi alen o one o he usual de ini ions o he Tama i o de . I is no comple ely ob ious ha HST1(n,2) = HST2(n,2) ; a p oo appea s in [15, Theo em 3.8]. Example 3.7.Figu es 4 h ough 6 show pic u es o HST1(6,2) , HST1(6,3) , and HST1(7,3), espec i ely, all suppo ed by TOPCOM [32]. The ollowing p ope y, sugges ed by he p e ious examples and sc u iny o he accompanying igu es, is easily deduced om he de ini ions. P oposi ion 3.8. [ 15 , P op. 2.11] In bo h pose s HST1(n,d),HST2(n,d) , e e sal o he labelling, ha is, he elabelling 17→ n, 27→ n−1, . . . , n 7→ 1 •induces a non- i ial pose au omo phism o d odd, and •induces a pose an i-au omo phism o d e en. Sc u iny o he examples and igu es also sugges s he ollowing p ope ies, which a e no as ob ious, bu deduced by Rambau in [31, Co . 12.(i)]. P oposi ion 3.9. Gi en a iangula ion T o C(n,d) , le |T| deno e i s numbe o maximal simplices. •Fo d e en, |T|is cons an , independen o T, equal o n−e−1 ei d =2e. • Fo d odd, |T| akes on all alues in he ange hn−e−1 e−1,n−e ei i d=2e−1 . In ac , HST1(n,d)is a anked pose in which Thas ank n−e e−|T|. A su ey o he highe S ashe -Tama i o de s 7 Fig. 4 A pic u e o HST1(6,2) = HST2(6,2) , simila o [ 15 , Fig. 4(a)]. T iangula ions T o C(6,2) a e depic ed as he images o hei co esponding sec ions sT:C(6,2)→C(6,3) , iewed om abo e C(6,3). Labels {j`,ik}on co e ing ela ions indica e suppo s o he co esponding lips as ollows: he 3 -simplex {i,j,k,`} wi h i<j<k< ` suppo ing he lip has lowe ace s {i jk,ik`} , and uppe ace s {i j`, jk`}. 8 J¨ o g Rambau and Vic o Reine Fig. 5 A pic u e o HST1(6,3) ; he labels o he co e ing ela ions indica e he suppo o he co esponding lip. A e eading Theo em 6.6 below, he in e es ed eade may wan o ind, o each o he 6 iangula ions in his igu e, a leas one maximal chain in Figu e 4 which induces i . A su ey o he highe S ashe -Tama i o de s 9 Fig. 6 A pic u e o HST1(7,3)(da a gene a ed by TOPCOM [32]), simila o [15, Fig. 4(b)]. 16 J¨ o g Rambau and Vic o Reine 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 subdi ision S o C(7,2) in o a g een quad angle and a blue pen agon, along wi h i s acial in e al [xS,yS]∼ =HST2(4,2)×HST2(5,2) in HST2(7,2) . The open in e al (xS,yS) is homo opy equi alen o a 1 -sphe e (ci cle). The hep agon C(7,2) is depic ed wi h espec o coo dina es on he Ca a heodo y cu e, a he han he momen cu e, o be e isibili y o iangles. acial in e als [x,y] , ha is, hose in which x=xS,y=yS a e he minimum and maximum elemen s lying on a pa icula ace o he associahed on, indexed by a polygonal subdi ision S o he n -gon C(n,2) ; see Hugue and Tama i [ 23 ], and Pallo [ 28 ]. Figu e 8 shows an example o such an in e al [xS,yS] wi hin HST2(7,2) , wi h in his case an isomo phism [xS,yS]∼ =HST2(4,2)×HST2(5,2). A su ey o he highe S ashe -Tama i o de s 17 6 Connec ion o Flip G aph Connec i i y The Hasse diag am o he highe S ashe -Tama i o de HST1(n,d) , conside ed as an undi ec ed g aph, is a special case o an impo an concep om disc e e and compu a ional geome y, which we discuss he e: he lip g aph o all iangula ions and (bis ella ) lips o an a bi a y a ine poin con igu a ion Ain Rd. 6.1 Bis ella lips Recall ha an edge in he Hasse diag am o HST1(n,d) co esponds o wo ian- gula ions T,T0 o A=C(n,d) ha sha e almos all o he same simplices excep ha hey es ic o he wo di e en possible iangula ions (uppe and lowe ) o he con ex hull o a ce ain subse A0=C(d+2,d)o ca dinali y d+2. I emains ue gene ally ha o d+2 poin s A0in Rd, he e will be exac ly wo iangula ions o hei con ex hull, using only e ices in A0 . I e en emains ue ha hese wo iangula ions will again be he se o “uppe ” and “lowe ” ace s o some li ing o he poin s A0 in Rd o he e ices o a (d+1) -simplex in Rd+1 , bu he combina o ics o hese wo iangula ions will depend upon he signs in he unique a ine dependence (up o scaling) among hese poin s, o he o ien ed ma oid o he a ine poin con igu a ion A0; see again [11, §2.4]. De ini ion 6.1. Two iangula ions T,T0 o he con ex hull o an a ine poin con igu a ion A in Rd using only e ices in A , a e said o di e by a ( d -dimensional) bis ella lip i hey sha e almos all o he same simplices, bu es ic o he wo possible iangula ions o he con ex hull o some d+2 elemen subse A0⊂A. Mo e gene ally han he d -dimensional bis ella lips, one also allows lowe - dimensional bis ella lips be ween wo iangula ions T,T0 , in ol ing a subse A0⊂Ao ca dinali y e+2 whose a ine span is e-dimensional; see again [11, §2.4] o he p ecise de ini ions. Figu e 9 illus a es some o he a ie y o lips possible al eady o poin s A in R2 , wi h he igh mos example being lowe -dimensional lip. Al hough he a ie y o possible ypes o lips g ows in highe dimensions (see Figu e 10 o one example), when A in Rd is in gene al posi ion (no d+1 o i s poin s lie on an a ine hype plane o Rd ), he lips a e local modi ica ions, ha a ec a mos d+1 simplices on d+2 poin s in a iangula ion. Thus, lips a e impo an in compu a ional geome y ( d=2 o d=3 , mos ly!) as a means o imp o e iangula ions by local modi ica ions (see [ 17 ] o jus one example o [ 16 ] and [ 10 , Chps. 3 and 9] o he low-dimensional iewpoin o Compu a ional Geome y). In non-gene al posi ion, lips can become qui e la ge modi ica ions. (See also [ 11 , Chp. 8] o a mo e de ailed discussion on algo i hmic issues in gene al dimension). We should wa n he eade ha he e is a closely ela ed no ion o bis ella lip in he li e a u e, which is no qui e he same: bis ella equi alences o iangula ions o PL-mani olds, as in he wo k o Pachne [ 27 ]. The e one does no insis ha he mani olds ha e a ixed embedding in o space no ha he e ices in he iangula ion 18 J¨ o g Rambau and Vic o Reine Fig. 9 An edge lip and a e ex lip in dimension wo (g ey), whose combina o ics can be ep e- sen ed opologically by pushing a su ace in dimension h ee (blue) h ough a e ahed on ( ed) all he way om he lowe ace s o he uppe ace s. The igh mos igu e is a lowe -dimensional lip, adding e ex 4 in he middle o edge 23 (g ey): i s combina o ics can ep esen ed opologically by pushing a su ace in dimension h ee (blue) h ough a e ical iangle (= 2 -simplex!) linked o wo e ices ( ed). Fig. 10 In dimension h ee, gene al posi ion lips will change he numbe o simplices, as in C(5,3) depic ed he e, which has exac ly hese wo iangula ions (exploded iew). Compa e wi h he discussion o (2,3)-Pachne mo es in he su ey by S ashe in his olume [41, §4.2]. ha e ixed coo dina es. In con as , iangula ions in ou con ex ha e e ices coming om he poin se A, wi h ixed coo dina es in Rd. A su ey o he highe S ashe -Tama i o de s 19 6.2 The lip connec i i y ques ion In disc e e and compu a ional geome y, one would like o use bis ella lips o explo e he se o all iangula ions o A , o o ge o any iangula ion ( o example, a special desi ed one) om any o he iangula ion ( o example, an ob ious one, such as he popula Delaunay iangula ion [ 11 , § 2.2.2]. This mo i a es he ollowing de ini ion and ques ion. De ini ion 6.2. Gi en an a ine poin con igu a ion A in Rd , i s lip g aph G i(A) has e ex se indexed by he iangula ions T o he con ex hull o A using only e ices in A , and edges be ween pai s o iangula ions T,T0 whene e hey di e by a bis ella lip. Ques ion 6.3. Gi en an a ine poin con igu a ion Ain Rd, is G i(A)connec ed? When ei he d≤2 , o |A|−d≤3 , i is no ha d o p o e ha he answe is “Yes”. Fo highe dimensions d and poin con igu a ions A , his ques ion an alized e- sea che s o qui e some ime un il esol ed nega i ely by San os, i s in [ 38 ], whe e he ound a coun e -example wi h d=6 , double-checked by compu e -calcula ions wi h TOPCOM [ 32 ]. La e San os [ 39 ] p oduced ano he coun e -example d=5 and in gene al posi ion, which can be u ned in o con ex-posi ion examples by a s anda d cons uc ion, he Law ence cons uc ion [11, §5.5]. Theo em 6.4. [ 39 , Theo em 1] The e is a 5 -dimensional poly ope wi h e ex se A o ca dinali y 26 o which he lip g aph G i(A)is disconnec ed. This should be compa ed wi h he posi i e esul s o Gel and, Kap ano and Zele insky on seconda y poly opes [ 19 ]. They dis inguish a pa icula ly well-beha ed subg aph o G i(A) , which is no only connec ed, bu e en (|A| − d−1) - e ex- connec ed in he g aph- heo e ic sense, because i gi es he 1 -skele on ( e ices and edges) o he (|A|−d−1) -dimensional seconda y poly ope. This subg aph consis s o he egula iangula ions o cohe en iangula ions (and he egula lips o cohe en lips be ween hem), namely hose ha a ise as p ojec ions o lowe ace s o a li ing o he poin con igu a ion. 6.3 The lip g aph o a cyclic poly ope Re u ning o cyclic poly opes C(n,d) , i is known and no ha d o see ha o d=2 , all iangula ions a e egula /cohe en . This co esponds o he ac ha he Hasse dia- g am o he Tama i o de is he 1 -skele on o he S ashe poly ope o associahed on, which is he seconda y poly ope o he poin con igu a ion C(n,2) . Howe e , o any ixed d≥3 , one can show ha , asymp o ically in n , mos iangula ions o C(n,d) a e no egula /cohe en , [ 11 , § 6.1], which aises ha ques ion o connec i i y o hei lip g aphs. Theo em 6.5. [ 31 , Thm. 1.1, Co . 1.2]. The i s highe S ashe -Tama i o de HST1(n,d) is bounded, wi h he same bo om ˆ 0n,d and op ˆ 1n,d iangula ions as he 20 J¨ o g Rambau and Vic o Reine Fig. 11 The Hasse-diag am o HST1(10,6) gene a ed by an unpublished maple package o he i s au ho and he S emb idge pose s package [42]. second highe S ashe -Tama i o de HST2(n,d) . In pa icula , he Hasse diag am o HST1(n,d), which is he lip g aph G i(C(n,d)), is connec ed. Figu e 11 shows he Hasse-diag am o HST1(10,6), a non- i ial case o which boundedness was unknown be o e. A su ey o he highe S ashe -Tama i o de s 21 6.4 Diame e Since he lip g aph G i(C(n,d)) is connec ed, i makes sense o ask o i s diame e , ha is, how many lips a e equi ed o each a iangula ion om any o he , in he wo s case. We explain he e how he ollowing s uc u al esul on HST1(n,d) leads o he exac diame e when dis odd, and diame e bounds when dis e en. Theo em 6.6. [ 31 , Thm. 1.1] The e is a one- o-one co espondence be ween equi - alence classes o maximal chains in HST1(n,d) and iangula ions o C(n,d+1) . Two chains a e equi alen i hei co e ing ela ions a e lips on iden ical se s o d+1 -simplices. This co espondence is induced by mapping each lip in a maximal chain in HST1(n,d) o he co esponding (d+1)-simplex in C(n,d+1). Fig. 12 The connec ion be ween a chain in HST1(6,1) ( ep esen ed by cha ac e is ic sec ions) and an elemen o HST1(6,2)( igu es om [11, Chp. 5]). When d is odd, so ha HST1(n,d) is bo h anked and bounded, his de e mines he diame e o G i(C(n,d)) exac ly, combining he p e ious esul , P oposi ion 3.9, and he ollowing well-known ac . P oposi ion 6.7. A bounded anked pose o ank has Hasse diag am diame e . P oo . E e y elemen lies in a maximal chain o leng h , and hence any pai o elemen s a e con ained in a closed cyclic pa h o 2 edges ha conca ena es wo such maximal chains; hus hey lie a dis ance a mos . On he o he hand, he unique bo om and op elemen s a e a dis ance a leas .u 22 J¨ o g Rambau and Vic o Reine Co olla y 6.8. [ 31 , Co . 1.2] Fo odd d=2e−1 , he diame e o he lip g aph o C(n,d)is n−e−1 e. Since a iangula ion o C(n,d+1) o de en has no mo e simplices han he e a e lowe ace s o C(n,d+2) and no ewe simplices han he e a e uppe ace s o C(n,d+2), he same a gumen a leas gi es hese bounds o he diame e . Co olla y 6.9. [ 31 , Co . 1.2] Fo e en d=2e , he diame e o he lip g aph o C(n,d)is bounded be ween n−e−2 eand 2n−e−2 e. 6.5 The case d=2: he o a ion g aph o bina y ees In he case whe e d=2 , he abo e diame e bounds show ha he diame e o G i(C(n,2)) is be ween n−3 and 2n−6 . Howe e , his case has been ex emely well-s udied unde he guise o he o a ion g aph on bina y ees, e.g. in he wo k o Pallo; see he su ey by Deho noy [12] in his olume o e e ences, and o he close connec ion wi h Thompson’s g oup. In pa icula , he abo e diame e bound is supe seded by he ollowing celeb a ed esul o Slea o , Thu s on, and Ta jan. Theo em 6.10. [ 40 , Thm. 2] The diame e o G i(C(n,2)) is, o su icien ly la ge alues o n, exac ly 2n−10. The p oo ha he diame e is a leas 2n−10 o su icien ly la ge n employs he h ee-dimensional in e p e a ion o lips ske ched abo e: lipping can be seen as shi ing a su ace om he lowe ace s o a (no necessa ily s aigh -line) e ahed on h ough he e ahed on all he way o he uppe ace s o he e ahed on. Mo eo e , a sequence o lips can be seen as mo ing a su ace all he way h ough a h ee-dimensional iangula ion, consis ing o one e ahed on pe lip and ha ing one iangula ion as he bo om and he o he iangula ion as he op su ace. I one could show ha he e a e iangula ions o an n -gon so ha he h ee-dimensional space be ween hem needs a leas 2n−10 e ahed a o be iangula ed, hen he claim would ollow. And indeed: by embedding he si ua ion in hype bolic geome y (whe e olumes o simplices a e bounded!), Slea o , Ta jan, and Thu s on es ablished he lowe bound along hese lines. Along hei way, hey had o mas e a weal h o echnical di icul ies, hough. No combina o ial o mo e in ui i e p oo has been gi en o his lowe bound o da e. 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 ( om le o igh ) o he s anda d iangula ion wi h espec o e ex 7. A su ey o he highe S ashe -Tama i o de s 23 On he o he hand, hei a gumen o he diame e uppe bound o 2n−10 is easy enough o ep oduce he e. Pick an a bi a y e ex p o an n -gon wi h n>12 and an a bi a y iangula ion T . Unless p lies in all possible in e io edges, ha is, i s deg ee degT(p) in he in e io edge g aph o T is n−3 , we can ind a lip ha inc eases he deg ee o p by one. (In ha case, no all adjacen iangles in he s a o p in T can o m a non-con ex quad ila e al.) Thus, we need a mos n−3−degT(p) lips o ans o m T in o he unique iangula ion wi h degT(p) = n−3 , he s anda d iangula ion wi h espec o p . The same holds o any o he iangula ion T0 , so ha he lip dis ance dis (T,T0)be ween Tand T0is a mos dis (T,T0)≤min p2n−6−degT(p)−degT0(p)(3) I one uses he wo s case o his ela ion as an uppe bound, one can no ge pas 2n−6 . Howe e , symme y comes o ou aid: Since e e y iangula ion o an n -gon has n−3 in e io edges, he a e age in e io -edge deg ee o a e ex is (2n−6)/n=2−6/n. Summa ized: dis (T,T0)≤2n−6−2+6/n−2+6/n=2n−10 +12/n.(4) Since n>12 and he dis ance is in eg al, he claim ollows. 7 Subdi isions and he Baues p oblem We ha e al eady seen, in he discussion o M ¨ obius unc ions o HST2(n,d) in Sec ion 5, he ele ance o poly opal subdi isions S o C(n,d) which a e coa se han iangula ions, and he impo ance o he e inemen o de ing on hem. The lip g aph G i(A) is a one-dimensional objec buil om hese iangula ions and bis ella lips ela ing hem. I u ns ou ha bis ella lips can also be hough o as subdi isions which a e only sligh ly coa se han iangula ions, namely hose ha ha e exac ly wo e inemen s, bo h iangula ions. They o m pa o a la ge s uc u e, he Baues pose , buil om all subdi isions. The connec i i y ques ion o G i(A) is closely ela ed o he ques ion o homo opy ype o his Baues pose . We discuss his somewha in o mally he e – see [36] o u he discussion and e e ences. 7.1 Subd isions and seconda y poly opes Poly opal subdi isions o he con ex hull o a poin con igu a ion A , using only e ices in A , al eady appea ed na u ally in he wo k o Gel and, Kap ano , and Zele insky [ 19 , 20 ] on he seconda y poly ope o A ha was discussed in Sec ion 6.2: he ace pose o he second poly ope is exac ly he pose o all egula poly opal subdi isions S o he con ex hull o A , o de ed by e inemen . See Figu e 14 o 24 J¨ o g Rambau and Vic o Reine he example o a pen agon (isomo phic o C(5,2) ). See also [ 11 , Chp. 5] o a mo e elemen a y in oduc ion in o his heo y. Fig. 14 The e inemen pose o a i e-gon is isomo phic o he ace la ice o i s seconda y poly ope (in his case also a i e-gon); igu es om [11, Chp. 5]. 2 4 (134) (124) (1234) (14) 31 Fig. 15 A pa h in a e ahed on and he co esponding cell in he squa e ( igu e om [29]). 7.2 Baues’s o iginal p oblem Meanwhile, a conjec u e o Baues in he model heo y o loop spaces [5] mo i a ed Bille a, Kap ano , and S u m els [ 6 ] o gene alize his subdi ision pose . We gi e he e a ough idea o Baues’s goal, be o e explaining hei gene aliza ion. The loop space ΩX o a base-poin ed opological space (X,x) has elemen s which a e closed pa hs γ in X s a ing and ending a x , equipped wi h a ce ain opology. I X happens o come om a simplicial complex, ha is, i is glued om simplices, hen one migh hope o model ΩX ia some ype o cell complex; his idea goes back o J. F. Adams [1] who applied i o compu e he homology o ΩX. To his end, conside a piece o a closed pa h γ inside a d -simplex, wi h e ices numbe ed {0,1,2,...,d} , wi h γ en e ing each isi ed (open) ace a i s minimal e ex and exi ing a i s maximal e ex d . Mo eo e , we equi e ha i en e s he simplex a e ex 0 and exi s a e ex d . The a ious subs an ially dis inc op ions A su ey o he highe S ashe -Tama i o de s 25 o how his piece o γ can a e se he simplex (in e ms o isi ed open aces) can be modeled by a (d−1) -cube: he ex eme possibili ies a e edge pa hs wi h inc easing e ex labels in he simplex, which bijec wi h e ices o a cube: he e ices 1 h ough d−1 o he simplex ha a e isi ed by γ de e mine he ones in he coo dina es o he e ex o he cube. All in e media e op ions whe e γ can wande speci y in a a he ob ious way aces o he cube, whe e a pa h mee ing he in e io o he simplex co esponds o he imp ope ace o he cube, ha is, he whole cube. Thus, one migh hink ha he loop space o a simplicial complex can be modeled by a cubical complex. As always, he e a e echnical sub le ies, one o which is ha a ce ain s uc u e mus ha e he homo opy ype o a sphe e o hings o wo k. Baues conjec u ed ha his s uc u e ac ually always does ha e he homo opy ype o a sphe e. Fig. 16 How cellula s ings in he bipy amid p ojec o compa ible subdi isions o he line; he igh mos se o aces is no a cellula s ing, because he p ojec ions o hose aces o e lap ( igu e de i ed om a igu e in [29, Chap. 1]). 7.3 Cellula s ings and he gene alized Baues p oblem Bille a, Kap ano , and S u m els [ 6 ] disco e ed ha he s uc u e Baues was a e is an example o he ollowing cons uc ion. De ini ion 7.1. Conside a d0 -dimensional poly ope P and linea unc ional Rd0π →R1 aking dis inc alues π( )6=π( 0) whene e , 0 a e e ices lying on an edge o P . Say ha a subdi ision o he line segmen π(P) in R1 in o consecu i e in e als [ 0, 1],[ 1, 2],...,[ `−1, `] is π -compa ible 3 i , o each i=1,2,...,` , one can 3 The o iginal e m “ π -induced” in [ 7 , 6 ] was modi ied in [ 11 ] o “ π -compa ible” because, in gene al, he e a e many subdi isions ha a e p ojec ions o aces unde π , induced by he co esponding cellula s ings and π, no πalone. 32 J¨ o g Rambau and Vic o Reine S o B(n,0) = 2{1,2,...,n} , is a choice o such a label, and is conside ed a zono opal iling o Z(n,0). Al e na i ely, i gi es a sec ion o he map Z(n,n)π →Z(n,0). No e also ha he co e ing ela ion be ween subse s SlS0 in B(n,0) co esponds o wo e ices lying along an edge o he n-cube. Example 8.6.When d=1 , each ec o ν1( i) = i poin s along he ( x1 -)axis o R1 , and Z(n,1) is he line segmen whose wo endpoin s min, max a e ±( 1+··· + n) . A igh zono opal iling o Z(n,1)is a sequence o in e als [ min, min +2 w1], [ min +2 w1, min +2 w1+2 w2], ..., [ min +2 w1+2 w2+···+2 wn−1, max] co esponding o a pe mu a ion w= (w1,...,wn) in Sn , o an elemen o B(n,1) ; see Example 8.2. On he o he hand, such pe mu a ions o elemen s o B(n,1) co espond o max- imal chains in B(n,0) , ha is, sequences o nes ed subse s as in (5) , and hence by ou obse a ion o d=0 , o edge-pa hs in he cube Z(n,n) which p oceed in a mono one ashion om he e ex labelled by he emp y se ∅ o he e ex labelled by {1,2,...,n} . In o he wo ds, hey gi e sec ions o he map Z(n,n)π →Z(n,1) . See Figu e 21 and ollowing o some examples o such edges pa hs wi h n=3. No e also ha co e ing ela ion be ween wo pe mu a ions wlw0 in B(n,1) co esponds o wo mono one edge pa hs in he cube Z(n,n) ha di e only in wo adjacen s eps ha p oceed in opposi e ways a ound a quad ila e al ace o he cube Example 8.7.Again, hings become in e es ing when d=2. Now he ec o s ν2( i) in R2gene a e a zono opal polygon Z(n,2), ha is, a cen ally symme ic 2n-gon. An elemen o B(n,2) can be hough o as a maximal chain o pe mu a ions in B(n,1) as in (7) , up o a ce ain equi alence ela ion. I is possible o model his equi alence ela ion in a leas wo ways. One way conside s he associa ed pseudoline a angemen o wi ing diag am, as in Figu e 19, whose e ical slices eco d he pe mu a ions in he chain as he o de ing o he s ands. These diag ams a e conside ed only up o he equi alence ela ion o iso opies in he plane ha ne e allow one s and o slide o e he c ossing o wo o he s ands. The o he way conside s each pe mu a ion wi in he chain as a mono one edge pa h in he cube, and each co e ing ela ion wilwi+1 in he chain as gi ing a quad ila e al ace o he cube on which he wo pa hs ake wo adjacen s eps ha disag ee. The union o all such quad ila e al aces is a 2 -dimensional su ace inside he cube Z(n,n) , which is a sec ion o he map Z(n,n)→Z(n,2). The conco dance be ween hese wo models is ha he quad ila e al aces in his 2 -dimensional su ace map unde π o a igh zono opal iling o he 2n -gon Z(n,2) . This iling can be eco e ed as he plana dual g aph o he g aph gi en by he pseudoline a angemen , conside ed as ha ing e ices only a he s and c ossings; see Figu e 19. A su ey o he highe S ashe -Tama i o de s 33 Fig. 19 An elemen o B(4,2) de i ed om a maximal chain o pe mu a ions in B(4,1) , he weak B uha o de on S4 . The chain o pe mu a ions (colo ed om ed o cyan) leads o an a angemen o pseudolines, also called a wi ing diag am: ho izon al slices ha e he s ands o de ed as in he pe mu a ions in he chain. The plana dual o he pseudoline g aph can be d awn as a igh subdi ision o he zono ope Z(4,2) , in which he pseudoline s and i o i=1,2,3,4 is dual o he edges o he iles in he pa allelism class labelled by i . Mo eo e , he chain o pe mu a ions can be eco e ed in he zono opal iling as a sequence o mono one pa hs (colo ed om ed o cyan) wi h co e ing ela ions coming om “ lipping” he pa hs “upwa ds” h ough a quad ila e al. This pic u e con inues. The wo k o Thomas [ 44 , P op. 2.1], Ziegle [ 46 , Theo em 4.1] shows ha an elemen o B(n,d) can be hough o as unions o d -dimensional aces inside he cube Z(n,n) , co esponding o he image o a sec ion o he map Z(n,n)π →Z(n,d), p ojec ing o a igh zono opal subdi ision o Z(n,d). One can u he mo e show ha i one ins ead associa es o hese igh zono opal subdi isions S o Z(n,d) a sec ion sS o he map Z(n,d+1)π →Z(n,d) , hen one has S≤S0 in he highe B uha o de B⊆(n,d) exac ly when sS(x)d+1≤sS0(x)d+1 o all xin Z(n,d); see Figu e 20 o his pic u e o B⊆(4,2). Analogously o he si ua ion o cyclic poly opes C(n,d) , hese igh zono opal subdi isions and he edges be ween hem in he Hasse diag am o B(n,d) a e special cases o he mo e gene al no ion o a zono opal subdi ision o Z(n,d) , which is 34 J¨ o g Rambau and Vic o Reine Fig. 20 A pic u e o B(4,2) wi h elemen s d awn as he sec ions o zono opal ilings o Z(4,2) in Z(4,3) , pa ially o de ed by heigh ; i can be seen how he sec ions, on hei way o he op, sub- me ge mo e and mo e poin s. Each chain can be buil by s acking cubes, and he cubes co esponding o a chain o m a zono opal iling o Z(4,3), which ep esen s an elemen o B(4,3). A su ey o he highe S ashe -Tama i o de s 35 a π -compa ible subdi ision o he p ojec ion Z(n,n)π →Z(n,d) . The e is again a Baues pose o all such subdi isions, o de ed by e inemen , and he Baues p oblem asks o i s homo opy ype. A hanasiadis [ 2 ] in es iga ed he Baues p oblem o all o he canonical p ojec ions Z(n,d0)π →Z(n,d), as in Figu e 18. Theo em 8.8. [ 2 , Thm. 1.1] Fo all d0>d , he gene alized Baues pose o he canonical p ojec ion om Z(n,d0) o Z(n,d)has he homo opy ype o a d0−d−1- sphe e. 8.3 The map om highe B uha o highe S ashe -Tama i o de s The simila i y o he desc ip ion be ween he highe B uha o de s B(n,k) in he las sec ion should make hei analogy o he highe S ashe -Tama i o de s HST1(n,d) appa en . Tigh ening he connec ion, Kap ano and Voe odsky [ 24 ] claimed, and la e Rambau [ 31 ] p o ed, ha he e ac ually is a pose map be ween hem. La e , Thomas shed mo e ligh on his connec ion in [ 44 , § 4] (see Figu es 21 h ough 24 o an illus a ion). Theo em 8.9. [31, Co . 8.16]. The e is an o de -p ese ing map B(n,k) →HST1(n+2,k+1). In low dimensions, he map is amilia . Example 8.1 no ed he isomo phisms B(n,0) = 2{1,2,...,n}∼ =HST1(n+2,1). In he nex dimension up, he map B(n,1) →HST1(n+2,2) is he same as he map om he weak B uha o de on Sn o he Tama i o de on iangula ions o C(n+2,2) discussed in he su ey by Reading [ 35 , § 1] in his olume 5 . To desc ibe i in ou geome ic se ing, one mus assign a iangula ion o C(n+2,2) o each pe mu a ion w in Sn , o o each mono one edge pa h in he n -cube. To his end, hink o C(n+2,2) as labeled by 0,1,2,...,n+1 , wi h {0,n+1} i s only uppe edge. In he o de o he pe mu a ion w , cu o any emaining e ex i o C(n+2,2) by inse ing he diagonal om i s le o i s igh neighbo . Once all e ices 0<i<n+1 ha e been cu o , he se o inse ed diagonals o ms a iangula ion. No e ha wo dis inc pe mu a ions can map o he same iangula ion because i,j ha a e adjacen in he pe mu a ion bu no adjacen du ing he cu -o p ocedu e can be cu o in an a bi a y o de . Compa e his wi h he desc ip ion o his map in he su ey by Reading [ 35 , § 1], and in pa icula , compa e [35, Figu e 3], wi h Figu es 22 h ough 24 below. This ex ends (modulo echnical de ails) o a map B(n,d) →HST1(n+2,d+1) ia induc ion on d. Elemen s o B(n,d)a e equi alence classes o maximal chains 5 This map also appea s implici ly in he su ey by Hohlweg [ 21 ], whe e i is explained how o embed he associahed on in such a way ha i s no mal an coa sens ha o he pe mu ohed on. 36 J¨ o g Rambau and Vic o Reine Fig. 21 Each pe mu a ion in B(3,1) co esponds o a mono one pa h in he 3 -cube, which induces a iangula ion o C(5,2) by using he o de in which he coo dina es change as he o de in which he e ices 1,2,3 a e cu -o by he iangula ion. No e ha his can be in e p e ed as an up lip sequence in HST1(5,1). Thus, wha we see he e is he lip map T lip om [31]. Fig. 22 A di e en mono one pa h can lead o an iden ical iangula ion. Fig. 23 A di e en mono one pa h can also lead o a di e en iangula ion. A su ey o he highe S ashe -Tama i o de s 37 Fig. 24 Mono one pa hs ha di e by a “ ace lip” ( ha is, he co esponding pe mu a ions a e connec ed by an in e sion) lead o iangula ions ha a e ei he iden ical o a e connec ed by a bis ella lip. Fig. 25 Illus a ion o he induc i e s uc u e o he map om highe B uha o de s o highe S ashe -Tama i o de s: A zono opal iling o Z(4,2) ( he one om Figu e 19) can be a e sed upwa ds by mono one pa hs (colo ed om ed o cyan), which map o iangula ions o C(6,2) ha o m a chain ( om ed o cyan) inducing a iangula ion o C(6,3) consis ing o he lip simplices in he chain – de e mining an elemen o HST1(6,3). c=c1lc2l··· o elemen s ci in B(n,d−1) . Each (ci) in HST1(n+2,d) is al eady de ined by induc ion, and he eby gi es a sequence o iangula ions o C(n+2,d) 38 J¨ o g Rambau and Vic o Reine (c1)≤ (c2)≤ ··· (8) I can be shown ha o each i , ei he (ci) = (ci+1) o (ci)l (ci+1) in he o de HST1(n+2,d) . Hence, a e elimina ing duplica es, he sequence (8) gi es a maximal chain in HST1(n+2,d) , and he e o e an elemen o HST1(n+2,d+1) by Theo em 6.6. This induc i e cons uc ion is illus a ed in Figu e 25. The esul s summa ized in his sec ion all equi ed echnical o mal p oo s, o which we e ain om p esen ing any de ails. Howe e , we close wi h one p oblem on he abo e map , sugges ed by an asse ion om he o iginal pape o Kap ano and Voe odsky [24, Theo em 4.10], bu which has so a emained unp o en. Open P oblem 8.10. P o e ha he map B(n,d) →HST1(n+2,d+1) is su jec i e. 9 Enume a ion We close wi h an enume a i e ques ion: How la ge a e he pose s HST1(n,d),HST2(n,d) , ha is, how many iangula ions a e he e o he cyclic poly ope C(n,d)? A ew mos ly i ial esul s in his di ec ion a e known, such as •C(n,0),C(n,1),C(n,2)ha e n,2n−2,1 n−12(n−2) n−2 iangula ions, espec i ely, •C(n,n−1),C(n,n−2),C(n,n−3), ha e 1,2,n iangula ions, espec i ely. The ollowing non i ial esul was p o en by Azaola and San os [4]. Theo em 9.1. [4] The numbe o iangula ions o C(n,n−4)is ((n+4)·2n−4 2−n o n e en, and 3n+11 2·2n−5 2−n o n odd. Ano he in e es ing unsol ed p oblem is he ollowing. Open P oblem 9.2. Coun he iangula ions o C(n,3). How abou compu e -based enume a ion? Table 1 below compiles a ew esul s achie ed by he gene al pu pose enume a ion p og am o iangula ions TOPCOM [ 32 ]. Wi h special pu pose codes i should be possible o gene a e mo e numbe s ha can be used o check conjec u al enume a ion o mulas. Re e ences 1. J. F. Adams, “On he coba cons uc ion”, P oceedings o he Na ional Academy o Science 42 (1956) 409–412. 2. C. A hanasiadis, “Zono opal subdi isions o cyclic zono opes”, Geome iae Dedica a 86 (2001) 37–57. A su ey o he highe S ashe -Tama i o de s 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 compu a ions done wi h TOPCOM [ 32 ] o some dimensions d and some codi- mensions c:=n−d ; he compu a ion o he la ges numbe s in he able o C(13,6) and C(14,3) needed a ound 40 GB o main memo y. 3. C. A hanasiadis, J. Rambau, and F. San os, “The Gene alized Baues P oblem o cyclic poly- opes II”, Publica ions De l’Ins i u Ma hema ique, Belg ade 66 (1999) 3–15. 4. M. Azaola and F. San os, “The numbe o iangula ions o he cyclic poly ope C(n,n−4) ”, Disc e e Compu . Geom. 27 (2002) 29–48, Geome ic combina o ics (San F ancisco, CA/Da is, CA, 2000). 5. H. J. Baues, “Geome y o loop spaces and he coba cons uc ion”, Memoi s o he Ame ican Ma hema ical Socie y 25 (1980) 1–171. 6. L. J. Bille a, M. M. Kap ano , and B. S u m els, “Cellula s ings on poly opes”, P oceedings o he Ame ican Ma hema ical Socie y 122 (1994) 549–555. 7. L. J. Bille a and B. S u m els, “Fibe poly opes”, Annals o Ma hema ics 135 (1992) 527–549. 8. A. Bj ¨ o ne , “Topological me hods”, in Handbook o Combina o ics, R. L. G aham, M. G ¨ o schel, and L. Lo ´ asz, eds., No h Holland, Ams e dam, 1995, 1819–1872. 9. A. Bj ¨ o ne , M. Las Ve gnas, B. S u m els, N. Whi e, and G. M. Ziegle , O ien ed ma oids, second ed., Encyclopedia o Ma hema ics and i s Applica ions, ol. 46, Camb idge Uni e si y P ess, Camb idge, 1999. 10. M. de Be g, O. Cheong, M. an K e eld, and M. O e ma s, Compu a ional Geome y: Algo- i hms and Applica ions, 3 d ed., Sp inge , 2008. 11. J. De Loe a, J. Rambau, and F. San os, T iangula ions – S uc u es o Applica ions and Algo i hms, Algo i hms and Compu a ion in Ma hema ics, ol. 25, Sp inge , 2010. 12. P. Deho noy, “Tama i la ices and he symme ic Thompson monoid”, in his olume, 2011. 13. T. K. Dey, “On coun ing iangula ions in ddimensions”, Compu . Geom. 3(1993) 315–325. 14. P. Edelman, V. Reine , and J. Rambau, “On subdi ision pose s o cyclic poly opes”, Eu opean Jou nal o Combina o ics 21 (2000) 85–101. 15. P. H. Edelman and V. Reine , “The highe S ashe -Tama i pose s”, Ma hema ika 43 (1996) 127–154. 16. H. Edelsb unne , Geome y and opology o mesh gene a ion, Camb idge Monog aphs on Applied and Compu a ional Ma hema ics, ol. 7, Camb idge Uni e si y P ess, Camb idge, 2001. 17. H. Edelsb unne and N. R. Shah, “Inc emen al opological lipping wo ks o egula iangula- ions”, in P oceedings o he 8 h annual ACM Symposium on Compu a ional Geome y, ACM p ess, 1992, 43–52. 18. S. Felsne and H. Weil, “A heo em on highe B uha o de s”, Disc e e & Compu a ional Geome y 23 (2000) 121–127. 19. I. M. Gel and, M. M. Kap ano , and A. V. Zele insky, “Disc iminan s o polynomials in se e al a iables and iangula ions o New on polyhed a”, Lening ad Ma hema ical Jou nal 2 (1991) 449–505. 40 J¨ o g Rambau and Vic o Reine 20. ,Disc iminan s, Resul an s, and Mul idimensional De e minan s, Ma hema ics: Theo y & Applica ions, Bi kh¨ ause , Bos on, 1994. 21. C. Hohlweg, “Pe mu ahed a and associahed a: Gene alized associahed a om he geome y o ini e e lec ion g oups”, in his olume, 2011. 22. S. Huang and D. Tama i, “P oblems o associa i i y: A simple p oo o he la ice p ope y o sys ems o de ed by a semi-associa i e law”, J. Combina o ial Theo y Se . A 13 (1972) 7–13. 23. D. Hugue and D. Tama i, “La s uc u e poly ´ ed ale des complexes de pa en h ´ esages”, J. Combin. In o m. Sys em Sci. 3(1978) 69–81. 24. M. M. Kap ano and V. A. Voe odsky, “Combina o ial-geome ic aspec s o polyca ego y heo y: pas ing schemes and highe B uha o de s (lis o esul s)”, Cahie s de Topologie e G´ eom´ e ie di ´ e en ielle ca ´ ego iques 32 (1991) 11–27. 25. Y. I. Manin and V. V. Schech man, “A angemen s o hype planes, highe b aid g oups and highe B uha o de s”, Ad anced S udies in Pu e Ma hema ics 17 (1989) 289–308. 26. S. Oppe mann and H. Thomas, “Highe dimensional clus e combina o ics and ep esen a ion heo y”, ma h a Xi (2010) ?? 27. U. Pachne , “P.L. homeomo phic mani olds a e equi alen by elemen a y shellings”, Eu opean J. Combin. 12 (1991) 129–145. 28. J. M. Pallo, “An algo i hm o compu e he M ¨ obius unc ion o he o a ion la ice o bina y ees”, RAIRO In o m. Th´ eo . Appl. 27 (1993) 341–348. 29. J. Rambau, P ojec ions o Poly opes and Polyhed al Subdi isions, Be ich e aus de Ma hema ik, Shake , Aachen, 1996, Disse a ion, TU Be lin. 30. , “A suspension lemma o bounded pose s”, J. Combin. Theo y Se . A 80 (1997) 374–379. 31. , “T iangula ions o cyclic poly opes and highe B uha o de s”, Ma hema ika 44 (1997) 162–194. 32. , “TOPCOM: T iangula ions o poin con igu a ions and o ien ed ma oids”, in Ma h- ema ical So wa e—ICMS 2002, A. M. Cohen, X.-S. Gao, and N. Takayama, eds., Wo ld Scien i ic, 2002, 330–340. 33. J. Rambau and F. San os, “The Gene alized Baues P oblem o cyclic poly opes I”, Eu opean Jou nal o Combina o ics 21 (2000) 65–83. 34. J. Rambau and G. M. Ziegle , “P ojec ions o poly opes and he Gene alized Baues Conjec u e”, Disc e e & Compu a ional Geome y 16 (1996) 215–237. 35. N. Reading, “F om he Tama i la ice o Camb ian la ices and beyond”, in his olume, 2011. 36. V. Reine , “The gene alized Baues p oblem”, in New Pe spec i es in Algeb aic Combina o ics (Be keley, CA, 1996–97), Ma h. Sci. Res. Ins . Publ., ol. 38, Camb idge Uni . P ess, Camb idge, 1999, 293–336. 37. J. Rich e -Gebe and G. M. Ziegle , “Zono opal ilings and he Bohne-D ess heo em”, in P oceedings “Je usalem Combina o ics ’93”, H. Ba celo and G. Kalai, eds., Con empo a y Ma hema ics, ol. 178, Ame ican Ma hema ical Socie y, 1994, 211–232. 38. F. San os, “A poin con igu a ion whose space o iangula ions is disconnec ed”, Jou nal o he Ame ican Ma hema ical Socie y 13 (2000) 611–637. 39. , “Non-connec ed o ic Hilbe schemes”, Ma hema ische Annalen 332 (2005) 645–665. 40. D. D. Slea o , R. E. Ta jan, and W. P. Thu s on, “Ro a ion dis ance, iangula ions, and hype - bolic geome y”, Jou nal o he Ame ican Ma hema ical Socie y 1(1988) 647–681. 41. J. D. S ashe , “How i ‘me ’ Do Tama i”, in his olume, 2011. 42. J. R. S emb idge, “A Maple package o pose s”, F ee so wa e, a ailable online, 2008. 43. H. Thomas, “New combina o ial desc ip ions o he iangula ions o cyclic poly opes and he second highe S ashe -Tama i pose s”, O de 19 (2002) 327–342. 44. , “Maps be ween highe B uha o de s and highe S ashe -Tama i pose s”, in Fo mal Powe Se ies and Algeb aic Combina o ics Con e ence – Link¨ oping, Sweden, 2003, 2003. 45. , “The Tama i la ice as i a ises in qui e ep esen a ions”, in his olume, 2011. 46. G. M. Ziegle , “Highe B uha o de s and cyclic hype plane a angemen s”, Topology 32 (1993) 259–279. 47. G. M. Ziegle , Lec u es on poly opes, G adua e Tex s in Ma hema ics, ol. 152, Sp inge -Ve lag, New Yo k, 1995.