Xem mẫu
Shella bility of a p oset of p olygonal sub divisions
Torsten Ekedahl
Sto kholms universitet
SE-106 91 Sto kholm
Sweden
t e k e m a t h . s u .s e
Submitted: Ot 31, 2008; Aepted: De 7, 2009; Published: De 15, 2009
M athematis Sub jet Classiation: 52B22, 18D50
Dedi ated to Anders Bj örner on the oasion of his sixtieth bir thday
Abs trat
We intro due a s equene of p osets losely related to the asso iahedra. In this we
are motivated by reasons s imilar to those of Stashe in the ase of the asso iahedra.
We make a study of this p oset showing that it has an indutive struture with
prop er downwards intervals b eing pro duts of smaller p osets in the same series and
asso iahedra. Us ing this we als o show that they are thin dual CL-shellable and in
partiular that they are the fae p oset of a regular ell deomp osition of the ball.
1 Intro du tio n
T he pu rp ose o f this a rtile is to intro due a sequene of p osets losely related to the fae
latties of the a sso ia hedra a nd study their ombinatorial prop erties, in partiular it will
b e sh ow n tha t they a re shella ble. The origin of these p osets are in priniple not relevant
for suh a study, nevertheless I shall start by briey disussing it. The asso iahedra
are rele vant to the desriptio n of pro duts whih are asso iative only up to homotopy
A
-sp aes).
(
The pro totypial suh example is the path spae of a top ologial spae
w he re th e o mp o sitio n o f pa ths is not asso iative but is asso iative up to homotopy and
two map s fro m o ne spa e to a nother onstruted out of suh homotopies are homotopi
and so on.
M Supp ose now tha t the spae is a manifold
and that we are really only
inte reste d in smo oth pa ths. The problem is that the omp osition of smo oth paths is
u su ally not smo o th. The so lution would seem to b e to smo oth the omp osition but the
p rob lem then is tha t suh a smo o thing is not unique. Thus one is fored to sp eak ab out
a omp ositio n a nd will have to o ntend with the ambiguities inherent in that. A diret
way of e xp ressing a o mp o sitio n is as a smo oth map from the standard 2 Δ
to-simplex
the electronic journal of combinatorics 16(2) (2009), #R23 1
M
, w he re the o rig ina l two pa ths a re the restrition of that map to the rst two edges and
the p artiula r o mp o site is the restrition to the third edge. The map itself is then the
p artiu lar smo o thing o f the o mp o sition of the rst two edges to the third edge. We write
a b → ab a b a b , where
represents the omp osition,
a re the original paths,
a nd
this as
ab ab
as end result.th e smo othing and the a rrow represents a partiular smo othing with
Following the pa ttern o f hig her oherene onditions that made the asso iahedra ap-
ab → ab ,
p ear in the rst plae, we a ssume that we have dierent hoies of omp ositions
bc → bc abc → abc abc → abc ,
and we are lo oking for some supplementary oherenea nd
on d ition tha t wo uld express that these hoies of omp osites are oherently asso iative.
In th is p artiula r a se the o mp o sites t together to give a smo oth map from the b oundary
Δ M Δ to
itself. However,
a nd we o uld dema nd that this map extend smo othly to
of
we wou ld rather have o nditio ns that an b e formulated in terms of omp osition of paths
A and the
- struture. Hene using the homotopies given by the smo othings together with
a(bc) −→ (ab)c the asso iativity ho mo to py
gives us a mapping from the b oundary
M :
of th e p enta g o n into the pa th spa e of
a (b c) abc (a b) c
a bc ab c
abc
T he oh erene o nditio n sho uld then b e that this map extend to the full p entagon. The
p entagon of o urse is the seo nd a sso iahedron indiating that there is indeed a relation
b etwee n this o nditio n a nd the asso iahedron. If one analyses the next oherene ondi-
tion , on e arrives at so mething tha t is not an asso iahedron (see Fig. 2) but is visibly a
p oly he d ron. In this no te we sha ll g ive a general denition of these oherene onditions
le ad ing to p o sets tha t share the simplest ombinatorial prop erties with the fae p osets of
p oly he d ra suh a s b eing a la ttie a nd b eing shellable. From the p oint of view of the origi-
n al motivatio n shella bility ha s the imp ortant onsequene that the p osets are fae p osets
of a regu lar ell deo mp o sitio n o f a ball. However, its lose relation with the asso iahedra
se ems to me a n india tion tha t they should b e interesting from a purely ombinatorial
p ersp e tive.
Just as f o r the a sso iahedra themselves everything is b est phrased in terms of trian-
gulation s of n
- g o ns. A new no tion app ears however. We shall need to onsider not just
trian gu lations o f a xed p o lyg on but also triangulations of a subp olygon all of whose
verti es are verties o f the la rg er p o lygon as well as a simple way of passing from a partial
trian gu lation to a pa rtia l tria ng ula tion of a smaller p olygon.
CC
, the p oset of omp ound ollapses;C on erning sp ei results o ur prinipal p oset is
by ad din g a sma llest element we g et CC+
whih is proved to b e a graded p oset (Corollary
CC+
is dual
3.5) an d a la ttie (Pro p o sitio n 3 .7 ). Finally it is shown in Theorem 4.2 that
C L-she llab le a nd thin. Ana lo g o usly to the ase of the asso iahedron we also have a lo al
the electronic journal of combinatorics 16(2) (2009), #R23 2
]0,x]
is a pro dut of smaller p osets of omp oundstru tu re theo rem in tha t every interval
CC ollapses and f a e p o sets o f a sso iahedra (P rop osition 3.3). As
will b e seen to b e
very an alogo us to the f a e p o set o f the asso iahedron the following problem omes very
n atu rally.
Pro b lem :
CC
the f a e p o set of a onvex p olytop e?
Is
M y own exp eriene with p o lyto p es is to o meager to allow me to venture an opinion.
2 A low d im ens io n al example
CC
, the rst non-trivialTo m otivate o ur subsequent delib erations we start by desribing
e xample. (No te tha t in order to simplify we shall disregard some terminologial distin-
tion s th at will b e ma de later.)
n
-gon as partial parenthesisations
We an a s usual desrib e ell deomp ositions of the
n−1 k k 6 n
of a pro d ut o f
we shall do the-gons for
symb o ls. As we shall deal also with
followin g: We a ttah symb o ls, letters starting with a
in our example, to the initial edges
n of th e
-gon a nd then to a n a rbitrary edge we attah the onatenation of the symb ols
in orde r of the initia l edges o nneting the initial vertex of the edge to the nal. (An
in itial vertex ha s b een hosen a nd the p olygon is then oriented ounterlo kwise.) Hene,
if we attah a b c 4 , a nd
to the initial edges of the,
-gon, the edge from the rst to the
ab
. The nal edge will in general get the lab el obtained bythird ve rte x will get la b el
6
-gon on aten ating a ll the la b els o f the initial edges. For instane if we start with a
w ith in itial edg e la b els a b c d e 6 , then the
,
-gon itself will orresp ond to the,
, and
,
a b c d e 4
whereas the
-gon onsisting of the edge fromu np are nthesised expression
the rst to the third vertex, f ro m the third to the fourth, from the fourth to the sixth,
ab c de
(f., Fig.and the na l edg e will orresp o nd to the unparenthesised expression
abcde 1
1). T he fu ll o natena tio n
-gon onsisting just of thewill then orresp ond to the
e
d de
c a•b•c•d•e
c
ab•c•de abcde
b ab
a
6 4 1 -gon and
-gon ontained in it.Figure 1 : A
- g on a nd a
nal ed ge (i dem ).
k Furth ermo re a ell deo mp osition of a
-gon, whih is the onvex hull of a set of
n
- g on o nta ining the initial and nal vertex, will orresp ond to a partiallyverti es of the
the electronic journal of combinatorics 16(2) (2009), #R23 3
p are nth esised expressio n of o natenations of the lab els of the initial edges suh that the
ab cd lab e ls ap p ea r in inrea sing o rder. Thus
orresp onds to the ell deomp osition,
5
- g o n, o nsisting of the edge onneting the rst vertex to the third,
u sin g e d ge s o f the
the e dge onneting the third to the fourth and (as always) the nal edge. A omp ound
ollapse th en o rresp o nds to repla ing p ossibly several but disjoint unparenthesised sub-
(ab)(cd) e xp re ssions with the o rresp o nding onatenation. Continuing the last example
ab (c d) (a b) cd ab cd .
, and
, ollapses to a ny o f
N ote fu rther tha t a ording to o ur denitions any ell deomp osition ollapses to itself
C → C ∈ CC C .
also by just
and we shall deno te
In Figure 2 we have a ssembled all the ollapses (or as they shall b e alled later
5 a b c d
and- gon exept the ones orresp onding to
om p ou n d o lla pses) inside o f a
abcd → abcd
...
- tailieumienphi.vn
nguon tai.lieu . vn