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.