WIWIUUWIWWWWllNHHillilfllfllllilflllll

        

(0.4
AOL)
000

  

I HSI

THL CiS

iiiiiliiiiiiiiiiiiiiiii jiiijiiiii ..

31293 01782

LIBRARY
Michigan State
University

 

 

 

 

This is to certify that the

dissertation entitled

LEFT-MODULAR ELEMENTS AND EDGE LABELINGS

presented by

Larry Shu-Chung Liu

has been accepted towards fulfillment
of the requirements for

Ph.D. . Mathematics

degree 1n

 

 

Bruce E. Sagan

8mm 8%

Major professor T]

Date S'/;/qi

 

MS U is an Affirmative Action/Equal Opportunity Institution 0- 12771

 

PLACE iN REIURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE

DATE DUE

DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

we WORD/Mafia“

LEFT-MODULAR ELEMENTS AND EDGE LABELINGS
By

Larry Shu-Chung Liu

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

1999

ABSTRACT

LEFT-MODULAR ELEMENTS AND EDGE LABELINGS
By

Larry Shu-Chung Liu

This work is a study of posets and lattices in three parts.

In the first part, we give a characterization of left-modular elements and demon-
strate two formulas for the characteristic polynomial of a lattice with a left-modular
element. One of the formulas generalizes Stanley’s Partial Factorization Theorem,
and also provides an inductive proof for Blass and Sagan’s Total Factorization The-
orem for LL lattices. The characteristic polynomials and the Mobius functions of
non-crossing partition lattices and shufl‘le posets are computed as examples.

The second and third parts both deal with edge labelings of posets and lattices.
We construct an edge labeling for a left-modular lattice and show that it is an SL-
labeling. This gives a method of labeling certain non-pure lattices, for example, the
Tamari lattice.

In the third part, we study the rank-selected subposet P5 of a poset P. By
constructing an induced labeling for P3, we show that if P is an R-poset then so is
P3. Furthermore, we define the notion of a thrifty labeling and show that if a labeling
is thrifty then EL- and SL-shellability are also inherited by P3.

In memory of my father, En-Tse Liu

iii

ACKNOWLEDGMENTS

I would like to express my deepest gratitude to my advisor, Professor Bruce Sagan,
for his guidance and encouragement throughout the course of this study, as well as
his invaluable advice on mathematics. I am indebted to him even more after finishing
this manuscript, because without his patient instructions I would not have been able
to transfer my first draft into a readable document.

I would also like to thank Professors Jonathan Hall, Tien-Yien Li, Edgar Palmer,
and Richard Phillips, who served on my thesis committee, for their guidance and
support. Special thanks to Professor Edgar Palmer for proofreading this thesis and to
Dr. Yeong-Nan Yeh for his enthusiastic advice on this work, while I was at Academia
Sinica in Taiwan.

I am grateful for the friendship of my graduate fellows at MSU. Especially, I thank
David Gebhard, Joan Stamm, Hsiu Chuan Wei, Mengnien Wu, and Niangone Wu for
their help and kindness. I also appreciate the financial support, which I received, in
the form of a teaching assistantship in the Mathematics Department. Without it I
could not have finished my degree.

I cannot thank my family enough for their love, support, and encouragement.
This volume was meant to be a humble gift to my father. I feel sorry that I could

not present it to him and I miss him very much.

iv

TABLE OF CONTENTS

LIST OF FIGURES
INTRODUCTION

1 PRELIMINARIES

1.1 Posets and Lattices ..............................
1.2 Mobius Functions ...............................
1.3 Characteristic Polynomials ..........................

2 LEFT-MODULAR ELEMENTS

2.1 Modular and Left—modular Elements ....................
2.2 Left-modular Elements and x(L, t) .....................
2.3 Non-crossing Partition Lattices .......... I .............
2.4 Shuffle Posets .................................
2.5 NBB Sets and Factorization Theorems ...................

3 EDGE LABELINGS OF POSETS

3.1 R-Labelings and Shellable Posets ......................
3.2 Left-modular Lattices ............................
3.3 Shellability of Rank-selected Posets .....................
3.4 CR—labelings and CL—labelings ........................

BIBLIOGRAPHY

1.1
1.2

2.1
2.2

3.1
3.2

LIST OF FIGURES

The lattices Cg, 33 and D12 ......................... 7
The partition lattice H4 ........................... 8
Partitions and their graphs .......................... 26
The lattice Wm ................................ 30
The Tamari lattice T3 ............................ 47
The Tamari lattice T4 and its SL—labeling .................. 48

vi

INTRODUCTION

The study of partially ordered sets (posets) and lattices can be traced back to the
nineteenth century. The work of G. D. Birkhoff in the 1930’s began the systematic
development of poset theory and lattice theory as subjects in their own right. As a
fundamental invariant, the Mobius function originated in several different forms re—
lated to number theory, geometry, algebra, topology and combinatorics. The Mobius
inversion formula for posets is essentially due to L. Weisner [19] in 1935 and was
independently rediscovered by P. Hall [10] in 1936. However, it was not until 1964
that the work of G.-C. Rota [12] started the systematic study of the Mébius function
within combinatorics. The theory of Mobius functions not only offers a very general
enumerative principle, of which the inclusion-exclusion principle in set theory is a
special case, but also provides a great deal of information regarding problems like
determination of the Euler characteristic and counting colorings of graphs. In the
first chapter of this thesis, we outline preliminaries concerning the theory of posets
and lattices needed for the following chapters. Some important theorems about the
Mobius function are also mentioned there.

The characteristic polynomial of a lattice was also first introduced by G. D.
Birkhoff [1], and its variants have been called the Birkhoff polynomial and the
Poincaré polynomial. Since it is a generating function for the Mébius function, much
has been done to explore the combinatorial and algebraic properties of this polyno-

mial. In the early 1970’s, Stanley proved two factorization theorems for the charac-

teristic polynomial. One of them states that a factor arises from a modular element
in a finite geometric lattice (the Partial Factorization Theorem, [14]). The other one
shows that the characteristic polynomial of a supersolvable and semimodular lattice
factors over the integers (the Total Factorization Theorem, [16]) and is implied by
the first result if the lattice is atomic. Various other methods for showing that this
polynomial has only integer roots have been developed; see the survey article [13].
Recently, A. Blass and B. Sagan [3] generalized Stanley’s Total Factorization Theo-
rem under a weaker hypothesis requiring only that the lattice satisfy left-modular and
level conditions. In Chapter 2, we give a characterization of left-modular elements
and then prove a generalization of the Partial Factorization Theorem which replaces
modularity with left-modularity. The latter result also provides us with an inductive
proof for Blass and Sagan’s theorem. So the previous three factorization theorems are
unified into one. We calculate the characteristic polynomials and M6bius functions
of non-crossing partition lattices and shuffle posets as examples.

R-labeling of pure (ranked) posets was introduced by R. Stanley [15]. The concept
offers a combinatorial interpretation of the Mobius function for an R—labeled poset.
Shortly thereafter EL- and SL-labelings, related to the concept of shelling in topol-
ogy, were defined by A. Bj6rner [4] and then generalized to CL-labeling in his joint
work with M. Wachs [5]. The resulting theory allows one to compute the homology
groups of the order complex of a poset. Recently, A. Bjiirner and M. Wachs [6], [7]
generalized the concept of Shellability to non-pure posets. They were motivated by
certain examples coming from the theory of subspace arrangements. In the first half
of Chapter 3, we show that a left-modular lattice is SL-shellable by constructing a
labeling which is induced by the maximal left-modular chain of the lattice. In the
second half, we study the edge labeling for the rank-selected subposet P5 of a poset
P. By constructing an induced labeling for P5, we show that if P is an R-poset then

so is P3. Then we introduce the concept of a thrifty labeling which allows EL— and

SL-shellability to be inherited by rank-selected subposets.

CHAPTER 1

PRELIMIN ARIES

1.1 Posets and Lattices

We will use N, P, Z, and IR for the nonnegative integers, positive integers, integers,
and real numbers, respectively. For other standard notation we will follow Stanley’s
text [18].

A partially ordered set, (P, S), or poset for short, is a set P together with a binary
relation S satisfying reflexivity, antisymmetry, and transitivity. Sometimes we write
3 p for g to avoid confusion. All posets discussed in this thesis will be finite. Let P‘
denote the dual poset of P obtained by reversing the order relation of P. Two posets
P and Q are isomorphic if there exists an order-preserving bijection n : P —) Q whose
inverse is also order-preserving. If 2:, y E P and a: g y, the closed interval [32, y] and

the open interval (1:, y) are defined by

[:c,y] = {zEPlxgzgy},

{zEP|x<z<y}.

(93,31)

The intervals (1:, y] and [:c, y) are defined similarly. If P contains a unique minimal
element (called a bottom element), it will be denoted by 6 (or 6 p to avoid confusion);

similarly, a unique maximal element (top element), if it exists, will be denoted by 1

(or La). A poset is called bounded if it has both a f) and a I. In this case [6, 1] = P.

We say that a: is covered by y, and write a: -< y, if a: < y and there is no element
zEPsuchthatz<z<y. Wealsousemjytomeana:-<yor:c=y. An atomis
an element covering a minimal element of P. Let A(P) denote the set of atoms in P
and A(a, b) denote the set of atoms in interval [a, b]. A co-atom is defined dually: it
is an element covered by a maximal element.

Any subset of P will form a subposet by inheriting the order relation of P. So,
in particular, intervals are subposets. A chain 0 of P is a subposet in which any
two elements are comparable. We define the length of a chain C by [(C) = [C] — 1,
where l - | denotes cardinality. The chain {x0 < 9:1 < - -- < zen} is called saturated (or
unrefinable) if 220 -< 2:1 -< -< :3”. A maximal chain in P is a saturated chain from

a minimal element to a maximal element of P. The length of a poset P is defined by
[(P) = max{£’(C) | C is a chain of P}.

Since we only consider finite posets here, this maximum value is finite. The length
of an interval [93, y] of P is denoted by [(x, y). If every maximal chain of P has the
same length n, then we say P is pure (or graded) of rank n. In this case, there is a

unique rank function p : P ——> N such that
i. p(:z:) = 0 if :c is a minimal element of P, and
ii. p(y) = p(:t:)+1ify > :c in P.

If p(:r:) = i, then we say that a: is of rank i. Obviously €(x,y) = p(y) — p(:c) and
[(P) = p(z) for any maximal element z of P. A generalized rank function will be
introduced in Section 2.2 for posets which could be non-pure.

A lattice L is a poset such that every pair 2:, y E L has a greatest lower bound and
a least upper bound. We call the greatest lower bound and the least upper bound

the meet and the join of a: and y, respectively. The meet is denoted x /\ y (or :1: AL y)

5

and the join is written a: V y (or a: V L y). Clearly, every finite lattice has a f) and
a 1, namely the meet and the join of all elements in the lattice. The following two

properties involving /\ and V are easy to check and very useful.
:1:/\(:r:Vy)=x=a:V(a:/\y). (1.1)

mAyzxéxVyzyfimSy. (1.2)

A subset M is called a sublattice of L if x, y E M implies a: VL y, :3 AL y E M.
Unlike posets, not every subset of L is a sublattice. Even though a subset itself forms
a lattice it might still not be a sublattice of L. An example will be given in Section 2.3
where we discuss the partition and non-crossing partition lattices. For a given subset
N, the sublattice generated by N is the smallest (in cardinality) sublattice containing
N.

If (P, 3p) and (Q, 3Q) are posets, then the direct product of P and Q is the poset
PXQ={(a:,y):xEPandy€Q}

such that (x, y) S (x’, y’) in P x Q if a: _<_ p :r’ and y SQ y’. It is clear from the definition
that P X Q and Q x P are isomorphic. The direct product of two lattices P, Q is still
alattice since (1:,y)V(:v’,y’) = (xvpx’,yVQy’) and (a3,y)/\(:c’,y’) = (zApx’,y/\Qy’).
The direct product of P with itself n times is denoted P".

The Hasse diagram of a poset P is a graph whose vertices are elements of P,
whose edges are the cover relations, and such that if y >- :1: then y is drawn above 2:.
Since a poset is completely determined by its cover relations, the Hasse diagram of
a poset depicts all order relations. The following are some fundamental examples of

finite lattices. The Hasse diagrams of these lattices are shown in Figures 1.1 and 1.2.

Example 1.1.1 Let n 6 N, [n] :2 {1,2,...,n}, and [0,11] := (0,1,. . .,n}.

i=3 i={1,2,3} 1:12

2 {1.2} {2,3} 4 6

1 {1} I I I {3} 2 3
C3 33 012

Figure 1.1. The lattices C3, 83 and D12

. The set [0, n] ordered in the usual manner forms the chain C". For any p,
q E [0, n], it is trivial that p /\ q = min{p, q}, p V q = max{p,q} and p(p) = p.

So 0,, is a lattice of rank n.

. The Boolean algebra 8,, consists of all subsets of [n] with inclusion Q as the
order relation. For any pair of subsets S, T E B“, we have 5 /\ T = S 0 T and
S V T = S' U T. The rank function is p(S) = [S]. So 3,, is a lattice of rank n.

B” is isomorphic to the direct product (01)".

. Let n 6 IP’ and n = pimp?“ . - -p["‘ with p1, p2, ..., p1 distinct primes and m1,
m2, . . . , m; 6 IP. The divisor lattice D" is the set of all positive integral divisors

of n ordered by divisibility, so u S v if and only if ulv, i.e., u divides o. For any
pair of divisors u and v of n, we have u A v = gcd(u,v) and u V v = lcm(u,v).
A divisor u = p’i’pg’ - - - p? has rank p(u) = i1 + i2 + - - - + i;. So Dn is a lattice
of rank m1 + mg + + m1. It is easy to check that D" is isomorphic to the

direct product C'm1 x Cm, x x CW.

 

Figure 1.2. The partition lattice I14

4. Let n E P. If it is a partition of [n] into k non-empty subsets, B,-, called blocks,
then we write 1r = 31/32/ . . . /B,, I- [n]. When it will cause no confusion,
we will not explicitly write out any blocks that are singletons. The partition
lattice 11,, consists of all partitions of [n] with partial order 1r S o if every block
of it is contained in a block of a. We denote by E, the equivalence relation
associated with the partition 1r, i.e., p 5,, q if and only if p and q belong to
the same block of 1r. It is easy to check that the equivalence relation am“, is
the transitive closure of 5,, and so; while 2“,, is their intersection. Suppose
7r = 81/32/ . . . /B,c then p(1r) = Ef=1(IBiI— 1) = n —- (number of blocks of 7r).

Therefore 11,, is a lattice of rank n — 1.

1 .2 Mobius Functions

One of the fundamental invariants of a poset P is its Mobius function, a : P x P —> Z,

defined recursively by

1 if a: = y,
Mar. 31) ==
— 2,:qu [1(3, 2) else.
Clearly ”(23, y) = 0 if :1: g y. Note that a is uniquely determined by the equation

2 “(3,2) = 63!!

ISZSy

where 63y is the Kronecker delta. If there is possible ambiguity, we will use up to
denote the Mobius function of P. In case P has a 0, for brevity we let ,u(:z:) = a(0, x).
If in addition P has a 1 then we write p(P) = p(0,1).

There are some general techniques for the evaluation of a. We begin with the

simplest one. For a proof, see [18, p. 118].

Proposition 1.2.1 (The Product Formula) Let P and Q be two finite posets.

Then

#Pxo((x,y), ($3311) = up(x,y)uo(m’,y')- I

Example 1.2.2 The Mobius functions of the first three lattices in Example 1.1.1 are

easy to find.

1. If p, q E C", then directly from the definition

1 ifq=p,
u(p,q)= —1 ifq=p+1,
0 else.

2. We have 8,, isomorphic to (01)" by identifying S Q [n] with a vector

1 if k e 5,
(1.1322) ' ' ' yin), Where ik :

0 otherwise.

Since the Mobius function of the chain CI = {0, 1} is given by p(0, 0) = u(1, 1) =
l and p(0, 1) = —1, we conclude from the product formula that if S g T (S g T)
in B,, then

MS. T) = (—1)‘”' = (—1)“S'T’.
In particular MS) = ,u(0, S) = (—1)'S'.

3. Recall that Dn E” Cm1 X Cm2 x >< Cm“ where n = p'f"p3"...p["‘ with
p1, p2, . . . , p1 distinct primes and m1, m2, ..., m1 6 IP’. Similarly to the pre-

vious example, if u s v in Du and v/u = p'fpg’ .. . p? then

( ) (1 / ) (—1)’1+"+"'+’l if 0 S i], g 1 for all k,
.11 “iv = ll ,1) U =
0 otherwise.

The value u(n) = [10,,(1, n) is the classical Mobius function in number theory.

The following two results are fundamental in the theory of Mobius function. A

proof of each can be found in [18, pp. 116, 117].

Theorem 1.2.3 (Mdbius Inversion Formula) Let P be a finite poset and f, g :

P —> R be any two functions. Then

g(a:) 2 Eggs: f(y) for all a: E P, if and only if
f (w) = 293. My. w)9(y) for all x E P. I

Theorem 1.2.4 (Mobius Inversion Formula, dual form) Let P be a finite

poset and f, g : P —> IR be any two functions. Then

g(a:) = ZyZz f(y) for all a: E P, if and only if
f (iv) = 2,2... u(a=,y)g(y) for all 2 E P- I
As an important application of Theorem 1.2.4, the Principle of Inclusion-Exclusion
is just Mobius inversion over a Boolean algebra. We will show it in the following

example.

10

Example 1.2.5 Let X be a set and let U denote a collection of properties which
elements of X either have or don’t have. For S Q U, let g(S) denote the number
of elements in X having all the properties in S, and let f (S) denote the number
of elements in X having all properties in S but no others. It is clear that 9(5) 2
ngr f (T) So by dual form of Mobius inversion formula
f(S) = Z ua.(s,T)g(T) = Z(—1)'T‘S'9<T)
SgT ng
where n = |U[. In the sum we use the Mobius function of B,, because the collection
of subsets of U forms a Boolean algebra. If we let S = (71, then
M) = Z(—1)'T'9(T)
TgU
which is the well—known sieve formula for the number of elements in X having none

of the properties in U.

An element of a lattice is called atomic if it is a join of atoms. The bottom
element 0 is the join of the empty set, so it is atomic. A lattice is called atomic if
all its elements are atomic. We denote by J (L) the set of atomic elements of lattice
L. In general, the set J (L) is not a sublattice of L because the meet of two atomic
elements is not necessarily atomic; however their join is atomic. An element p # 0 is

called join-irreducible (or just irreducible) if for every pair at, y E L
p=xVy implies p=morp=y.

It follows from the definition that an element is irreducible if and only if it covers a
single element in L. So atoms are irreducible. Irreducibles which are not atoms are
called singular elements. We can express any element a E L as a = p1 V p2 V .. - V p,
where p,- are irreducible elements. This expression is called a decomposition of a. The

remark after the definition of irreducible implies that the (single argument) Mobius

11

function of a singular element is zero. In fact, every non-atomic element has a Mobius

function value of zero. To prove this we define a map 6 : L —> J (L) by

6(3) 2 V{a E A(L) | a 3 at}.

Equivalently, 6(a) is the maximum atomic element in [0,12]. If a: is a non-atomic

element, then

u(w)=— Zu(y)+ Z My) =- Z My)-

3135(3) yE[0,z)\[0,6(z’)] y€I0s3)\IO.5(3)l
All y E [0,m)\[0,6(x)] are non-atomic and the minimal elements of [0,x)\[0,6(x)]
are all singular. So by induction 11(3) = 0. (Rota’s NBC Theory [12] is another

way to explain this result.) Therefore, for any atomic element a: E L, we have

[1(3) = #J(L)($)-

1.3 Characteristic Polynomials

Let P be a bounded pure poset of rank n and let t be an indeterminate. The char-

acteristic polynomial of P is then

X(P, t) = Z u($)t""’("-

zeP

One uses the co-rank of a: rather than the rank as the exponent on t so that the
polynomial will be monic. Since x is a generating function for p, it is of fundamental

importance. The following corollary is derived directly from Proposition 1.2.1.

Corollary 1.3.1 Let P and Q be two bounded pure posets. Then

X(P >< QJ) = X(P,t)X(Q,t)- I

Example 1.3.2 Continuing Example 1.2.2, it follows from the definition that the

characteristic polynomial of C" is
X(C,,,t) = t””1(t — 1).

12

By Corollary 1.3.1, the characteristic polynomials of B,, and D,, are

X(Bflit) : (t _ 1)”)
x(Dmt) = t""‘(t - 1)’.

wherem=m1+m2+---+m1.

13

CHAPTER 2

LEFT-MODULAR ELEMENTS

2.1 Modular and Left-modular Elements

Throughout this chapter L will be a finite lattice. Given 3:, y, z E L with z < y, it is

easy to check that the following inequality (the modular inequality)
zV(2:/\y)§(zVa:)/\y (2.1)

is always true and equality holds whenever y or z is comparable to 2:. We say that

:1:,y form a modular pair (2:, y) if
zV(:z:/\y)=(zVa:)/\y (2.2)

for any 2 < y. Note that this relation is not symmetric in general. We now define

two of the central concepts of this chapter.

Definition 2.1.1 1. An element a: is called a left-modular element if (2:,y) is a

modular pair for every y E L.

2. An element a: is called a modular element if both (2:, y) and (y, 2:) are modular

pairs for every y E L.

From the definition, if a: is left-modular in L then it is also left-modular in the dual

lattice L‘. However, this property is not true in general for modularity.

14

A finite lattice L is called (upper) semimodular if 2: /\ y -< 2: implies y -< 2: V y for
any 2:, y E L. A lattice L whose dual L“ is semimodular is called lower semimodular.
An equivalent definition of semimodularity is given in the following proposition. A

proof can be found in [18, p. 103].

Proposition 2.1.2 A finite lattice L is semimodular if and only if L is pure and the

rank function p of L satisfies
p(:v /\ y) + p(rc V y) S p(2) + £201)
for all 2:, y E L. I

In a semimodular lattice, the pair (2:, y) is modular if and only if

p(33 A y) + p(:8 V y) = p(:v) + p(y)- (2-3)

For a proof, see [2, p. 83]. So in this case the relation of being a modular pair is
symmetric, and then there is no difference between modularity and left-modularity in
a semimodular lattice. However, there are examples such as the non-crossing partition
lattices (see Sec. 2.3) and the Tamari lattices (see Sec. 3.2) where the two concepts
do not coincide.

We say a finite lattice is geometric if it is semimodular and atomic. In early work
of R. Stanley [14], he showed that x([0,2:],t) is a factor of x(L, t) if :r is a modular
element in a geometric lattice L. One of our goals is to generalize Stanley’s result by
replacing :c with a left-modular element and relaxing the condition that the lattice
be geometric. Stanley’s theorem and its generalization will be dealt with in next
section. Here we would like to examine some general properties of modular elements
and left-modular elements.

We say that y is a complement of 2: if 2: /\ y = 0 and x V y = 1. The following

theorem that was given in [14] provides a characterization of modular elements.

15

Theorem 2.1.3 (Stanley [14]) In a geometric lattice, an element 2: is modular if

and only if no two complements of 2: are comparable. I
The analog of Theorem 2.1.3 for left-modular elements is as follows.

Theorem 2.1.4 Let 2: be an element of any lattice L. The following statements are

equivalent:
i. The element 2: is left-modular.
ii. For anyy, z E L withz<y, we have2:/\z;£2:/\y orszséxVy.

iii. Foranyy,zELwithz<y, wehave2:/\z#:c/\y orzeryéxVy {butnot

both).

iv. For every interval [a, b] containing 2:, no two complements of 2: with respect to

the sublattice [a, b] are comparable.

Proof. We will prove the implications (i) => (ii) : (iii) :> (i). The proof of (ii) 4:)
(iv) is trivial.

First we make some preliminary observations. Suppose z < y. We claim that
2: V y = 2: V z if and only if y = (z V 2:) /\ y. The forward direction is trivial by
equation (1.1). Also we have y = (2 V at) /\ y implies y S 2: V z by (1.2). Now
2 < y g 2: V 2, and joining all sides with 2:, gives 2: V y = 2: V 2. Similarly we can show
that xAy:2:/\zifand onlyifz=zV(2:/\y).

For any 2 < y the inequalities
zSzV(w/\y)S(2Vx)/\ySy (2-4)

are true by the modular inequality (2.1). Since 2 75 y, at least one of the 3’s in (2.4)
should be <. Therefore (i) => (ii). If 2 -< y, then exactly two of the 3’s should be 2

and the remaining one must be <. Thus (ii) => (iii).

16

To show (iii) => (i), let us consider the contrapositive: assume that there are u, v E
L with u < v such that uV(2:/\v) < (uV2:)/\v. Given any y, z E [uV(2:/\v), (uV$)/\v]
with z < y, we havey g (uV2:)/\v _<_ v impliesuV(2:/\y) g uV(2:/\v) 5 z, so
that SL‘ /\ y 3 z. It follows that 2 V (2: /\ y) = z and also (2 V 2:) /\ y = y similarly, i.e.,

2:/\z=2:/\yand2:Vz=2:Vy. I

The existence of a left-modular element in L implies that one is also present in

certain sublattices as the next proposition shows.
Proposition 2.1.5 Let 2: be a left-modular element in lattice L. Then for any y E L
1. the meet 2: A y is a left-modular element in [0,y], and

2. the join 2: V y is a left-modular element in [y, 1].
Proof. Let a, b E [0, y] with b < a. By left-modularity of 2:, we have

bV((2:/\y)/\a) = bV(2:/\(y/\a)) = (er)/\(y/\a)

= ((bV23)/\y)/\a = (bV(2:/\y))/\a.

So 2: /\ y is a left-modular element in [0, y]. The proof for join is similar and will be

omitted. I

We obtain a result from [14] as a corollary.

Corollary 2.1.6 (Stanley [14]) Let 2: be a modular element in a semimodular lat-

tice L. Then for any y E L
1. the meet 2: /\ y is a modular element in [0, y], and

2. the join 2: V y is a modular element in [y, 1]. I

17

2.2 Left-modular Elements and x(L,t)

First, let us say a few words in motivation. There are two important factorization
theorems for characteristic polynomials given by Stanley. This factorization offers an
easy way to calculate the characteristic polynomials of various lattices. The following
theorem from [14] shows that if L is a geometric lattice then there is a factor of its

characteristic polynomial arising from a modular element.

Theorem 2.2.1 (Partial Factorization Theorem, Stanley [14]) Let L be a fi-
nite geometric lattice. If 2: is a modular element of L, then
x<L, t) = xaé, wit) 2 maven-MW“). -
bszz=0
In another paper [16], Stanley defined a supersolvable lattice to be a pair (L, A)
where L is a lattice, A : 0 = :60 -< 2:1 < -< 20,, = 1 is a maximal chain of L, and A
together with any other chain of L generates a distributive lattice, i.e., one such that

any elements 2:, y, z of it satisfy the distributive laws
2:V(y/\z) = (2:Vy)/\(.'sz),

ccA(sz)=(2:/\y)V(2:/\z).

The lattice formed by all subgroups of a supersolvable group partially ordered by
inclusion is an example of a supersolvable lattice. Stanley showed that a supersolv-
able lattice is pure. If L has a maximal modular chain A, i.e., every element of A
is modular, then (L, A) is supersolvable. Also, if (L, A) is supersolvable then the
elements of A are left-modular. So if (L, A) is both supersolvable and semimodular

then the elements of A are modular.

Theorem 2.2.2 (Total Factorization Theorem, Stanley [16]) Let (L,A) be a

supersolvable, semimodular lattice (SS lattice for short) of rank n, where A : 0 =

18

2:0-<2:1-<...-<2:,,=1. Then
x(L,t) = (t -— a1)(t —— a2) - - - (t — an) (2.5)
where a,- is the number of atoms of L that are below 2:,- but not below 2:,-1. I

If the SS lattice is also atomic, then Theorem 2.2.2 can be derived by inductively
applying the Partial Factorization Theorem to the chain A of modular elements. In
fact, we will show (Corollary 2.2.10) that the atomic restriction can be removed from
Theorem 2.2.1. So induction can applied even to lattices which are not necessarily
atomic such as the divisor lattice.

Recently A. Blass and B. Sagan [3] were able to generalize Theorem 2.2.2. To
replace supersolvability with a weaker hypothesis, they defined a left-modular lattice

L to be one such that
L has a maximal chain A, all of whose elements are left-modular.

Motivated by their result, we will generalize the Partial Factorization Theorem by

replacing 2: with a left-modular element.

Lemma 2.2.3 Let L be a lattice with an arbitrary function r : L —> IR and let it E IR.

If 2: E L is a left—modular element, then

Zu(y)t"""y’= 2 Mb) 2 u(b.v)t""‘y’-
yEL bAz=O yE[b,b\/2:]

Proof. We will mimic Stanley’s proof in [14]. By Crapo’s Complementation Theo-

rem [8], for any given a E [0, y]
#(y) = Z ”(01aI)C(a’i a”)l'l'(a"3 y),

where a’ and a" are complements of a in [0, y], and C is the zeta function defined by

((u,v) = 1 if u S v and ((u,v) = 0 else. Let us choose a = 2: /\ y. The element a is

19

left-modular in [0, y] by Proposition 2.1.5. But no two complements of a in [0, y] are
comparable by Theorem 2.1.4. Thus
p(y) = Z p(fi. b)u(b. .11). (2-6)
b
where the sum is over all complements b of a in [0, y], i.e., over all b satisfying b S y,
b/\ (2: /\ y) = 0 and bV (2: Ay) = y. Since 2: is left-modular, it is equivalent to say that
the sum in (2.6) is over all b E L satisfying b /\ 2: = 0 and y E [b, b V 2:]. Thus we have

Zn<y>t"“"y’ = Z Z u(0.b)u(b.y)t"""”’

yEL 96L be=O
yE[b,bV2:]

= Z Z u(b)u(b,y)t""’(”’-I

bAz=0 yE[b,sz]
Obviously the previous lemma is true for the rank function. To apply this result

to more general functions we make the following definition.

Definition 2.2.4 A generalized rank function of a lattice L is a function p : {(2:, y) E

LxleSy}—+IRsuchthatforanyagbgc

p(a, C) = p(a, b) + p(b, C)’
In this case, we say L is generalized graded by p.

For short we write p(2:) = p(0, 2:). Conversely, if we take any function p : L —+ IR
such that p(0) = 0, then we can easily construct a generalized rank function, namely
p(2:, y) = p(y) — p(2:). So the ordinary rank function is a special case.

If L is generalized graded by p, we now define a generalized characteristic poly-

nomial of L by
x(L,t> =-— Emotes“ = Spawn-Pr). (2.7)

zEL zEL
Note that X will depend on which generalized rank function we pick. Since the restric-

tion of a generalized rank function to an interval [a, b] still satisfies Definition 2.2.4

20

with L = [a, b], the characteristic polynomial of the interval is defined in the same

rnanner.

Theorem 2.2.5 Let L be generalized graded by p. If 2: E L is a left-modular element,

then

x(L,t> = Z [p(vtpdribvrxabw v m] . (2.8)

bEJ(L)
be=0

Proof. Directly from Lemma 2.2.3 and the definition of the generalized rank func-

tion, we get

x(L,t) = Z ”(5) Z “(5,y)tp(i)—p(y)

bAz=0 yE[b,bV2:]

= Z ”(bfiPIiI-MWE) Z ”(b,y)tp(bV==)—p(y)
bAz=0 yE[b,sz]

: Z ”(b)tp(i)*p(bv:c) Z ”(b,y)tp(y,bV2:)
bA2:=0 yE[b,bV2:]

= Z [p(b)tpli)"’(”v’)x([b,bv2:],t)] . .
bEJ(L)
bAz:0

In the sum (2.8), the term x([b,b V 2:],t) depends on b. To get a factorization
formula, we will remove the dependency by applying certain restrictions so that
x([b, b V 2:], t) = x([0,2:], t) for all b in the sum.

First, we will obtain a general condition under which two lattices have the same
characteristic polynomial. In the following discussion, let L and L’ be two lattices
and let 1' : L —> L’ be any map. For convenience, we also denote 0 = 0 L, 0’ = 0 L: and
similarly for 1, 1’, u, p’, etc.

We say r is a join-preserving map if
r(u V v) = r(u) V r(v)

for any u, v E L. Note that if 7' is join-preserving then it is also order-preserving

233/ => .11:wa => T(y)=T(xVy)=T(Iv)VT(y) => T($)Sr(y)-

21

If r is join-preserving, then given any 2:’ E T(L), we claim that the subset T"(2:’) has
a unique maximal element in L. Suppose that r(u) = r(v) = 2:’ for some u, v E L.
We have r(u V v) = r(u) V r(v) = 23’. Thus it V v E r‘1(2:’) and the claim follows. In

addition, if r is also surjective then we can define a' map a : L’ —+ L by
0(2c’) = the maximal element of r'1(2:’). (2.9)

Theorem 2.2.6 Using the previous notation, suppose that r is surjective and join-

preserving and that or is order-preserving with 0(0’) = 0. Then for any 2:’ E L’ we

have
u’(x’) = 2 11(31)-
yer-1W)
Proof. This is trivial when 2:’ = 0’, since the second hypothesis on 0 implies
r‘1(0’) = {0}. Let 2: = o(2:’). From the assumptions on 7' and a it is easy to
see that

[0,2]: L-iJ r—1(y'). (2.10)

y! 6 [GI ’2']

Now, by surjectivity of r and induction, we get
#'(m') = - X #'(y’)

vet—’(y')
yl<zl

= Z My). I

v61‘1(z')
Let L and L’ be generalized graded by p and p’, respectively. We say an order-
preserving map T : L -—> L’ is rank-preserving on a subset S Q L if p(2:,y) =

p’(r(2:), r(y)) for any x, y E S, 2: S y. Also we define a support set of L by

H(L) = {m E L | Min) #0}.

22

Theorem 2.2.7 If, in addition to the hypotheses of Theorem 2.2. 6, the map 7' is

rank-preserving on H (L) U {1} then

X(L)t) = X(Ll,t).
Proof. From (2.10) in the proof of Theorem 2.2.6, we know L = Ufa, T"(:r’).
Then by Theorem 2.2.6 and the rank-preserving nature of r, we have

x(L'.t> = Zrmrlti"

z’EL’

= Z Z H(yIt”'("”"

c’EL’ yEr‘1(:r’)

= Z Z ”(wtpwymin

z’EL’ yer—1(2’)

= Z p(yIt”(y”’

y€H(L)

= x(L,t). I

It is easy to generalize the previous theorem to arbitrary posets as long as the
map a is well defined. However, we know of no application of the result in this level
of generality.

Returning to our factorization theorem, we still need one more tool. For any given

a, b in a lattice, we define
an : [b,aVb] ——> [a/\b,a] by oa(u) : uAa,

Tb:[a/\b,a] —) [b,aVb] by Tb('U) =va.

The map Tb is the one we need to achieve x([b, bV2:], t) = x([0, 2:], t). We write H(2:, y)

for H ([2:, y]) which is the support set of the sublattice [2:, y].

Lemma 2.2.8 Let L be generalized graded and let 2: E L be a left-modular element.

Ifb E L is such that b /\ 2: = 0 and T5 is rank-preserving on H(0, 2:) U {2:}, then

X(Ib1b V 3:1: t) : X(I0i 23], 0°

23

Proof. We need only verify that the hypotheses of Theorem 2.2.7 are satisfied. By

left-modularity of 2:, we have
rbax(y) = bV (2: /\ y) = (b V 2:) /\ y = y (2.11)

for any y E [b,b V 2:]. So Tb is surjective. And it is easy to check that T5 is join-
preserving.
As for 0;, we must check that it satisfies the definition (2.9), i.e., for any y E
[b, b V 2:]
My) = max f(y).
Given z E rb’1(y) we have y = 77(2) 2 2 V b. So by the modular inequality (2.1) we
get

02(y)=y/\2:=(sz)/\2:ZzV(b/\2:)22

Since this is true for any such 2, we have oz(y) _>_ max rb-1(y). But equation (2.11)
implies oz(y) E Tb_1(y), so we have equality. Now 0pm,,” 2 b so o(b) = b /\ 2: = 0 as

desired. Noticing that o, is order-preserving, we complete the proof. I

We can now prove our main result.

Theorem 2.2.9 Let L be generalized graded by p and let 2: E L be an left-modular
element. If the map T5 is rank-preserving on H (0, 2:) U {2:} for every b E H (L)

satisfying b /\ 2: = 0. Then

X(Lit) = X([0,2:],t) Z ”(b)tp(i)-p(r)-P(b)

bEH(L)
bAz=0

: X([0 $1,323 p(b(b)t"(1)“ p(x)- p(b)
bAzr-O

Proof. By Lemma 2.2.8, we need only worry about the exponent on t in Theo—

rem 2.2.5. But since T5 is rank-preserving on H (0, 2:) U {2:}, we get
p(b V m) = p(é, b) + p(b. b V 2:)
= p(é. b) + p(fi. 1:) = W?) + p(x)- I

24

To apply this theorem, instead of H (0, 2:) and H (L) it is sometimes more convenient
to check the hypotheses for two sets containing them. For example, they can be
replaced by J(0, 2:) and J(L), or even by [0,2] and L.

Here we state a corollary of the previous result which has a weaker hypothesis
than Theorem 2.2.1. So Theorem 2.2.9 generalizes Stanley’s Partial Factorization

Theorem.

Corollary 2.2.10 Let L be a finite semimodular lattice graded by the ordinary rank
function p. If 2: is a modular element of L, then
xiL. t) = x20. 2:1, t) Z agrarian“).

beH(L)

b/\2:=0
Proof. To apply Theorem 2.2.9, it suffices to show that p(0, z) = p(b, sz) for every
z E [0,2]. Since (b, 2:) is a modular pair, we have (sz) A2: = 2 V (b/\2:) = 2V0 = 2.
By Corollary 2.1.6, we know z = (z Vb) /\ 2: is a modular element in [0, 2 V b], so (2, b)
forms a modular pair in the same interval. Thus p(z /\ b) + p(z V b) = p(z) + p(b),
because [0, 2 V b] is a semimodular lattice (see equation (2.3)). Since z /\ b = 0 we are

done. I

We take the divisor lattice D“ as an example. It is semimodular, but not atomic
in general, so Theorem 2.2.1 does not apply. However Corollary 2.2.10 can be used
for any 2: E D“, since all elements are modular.

We will now present two applications of the previous results in the following two

sections.

2.3 Non-crossing Partition Lattices

The non-crossing partition lattice was first studied by Kreweras [11] who showed its

Mbbius function is related to Catalan number. By using NBB sets (see Sec. 2.5 for the

25

7r : 123 /4578/6 (non-crossing) 134/ 256/ 78 (crossing)
1 .\2 1 2
8 3 8 3

60 5 6 5

 

Figure 2.1. Partitions and their graphs

definition), Blass and Sagan [3] combinatorially explained this fact. In this section
we will calculate the characteristic polynomial for a non-crossing partition lattice and
then offer another explanation for the value of its Mobius function.

Recall the definition of the partition lattice 11,, in Section 1.1. We say that a
partition 7r I- [n] is non-crossing if there do not exist i, k E B and j, l E G for two
distinct blocks B, C of 1r with i < j < k < l. Otherwise 7r is crossing.

Another way to view non-crossing partitions will be useful. Let G = (V, E) be
a graph with vertex set V = [n] and edge set E. We say that G is non-crossing if
there do not exist edges ik, jl E E with i < j < k < l. Equivalently, G is non-
crossing if, when the vertices are arranged in their natural order clockwise around
a circle and the edges are drawn as straight line segments, no two edges of G cross
geometrically. Given a partition r we can form a graph G,r by representing each block
B = {i1 < i,» < < i,} by a cycle with edges i1i2,i2i3,. . .,i1i1. (If |B| = l or 2 then
B is represented by an isolated vertex or edge, respectively.) Then it is easy to see
that 1r is non-crossing as a partition if and only if G, is non-crossing as a graph. In
Figure 2.1 we have displayed two partitions and their graphs.

The set of non-crossing partitions of [n] forms a meet-sublattice N 0,, of IL, with

the same rank function. However unlike II", the non-crossing partition lattice is not

26

semimodular in general, since if 7r = 13 and o = 24 then it /\ o = 0 and 1r V o =2 1234.
So we have

p(7r)+p(o)=2<3=p(7r/\o)+p(7rVo).

The join it VII" 0 = 13 / 24 also explains why N 0,, is not a sublattice of IL,.

Let 7r 2 12...(n — 1). We claim that it is left-modular in N C". It is well-
known [16] that 7r is modular in IL, and so left-modular there. Let a, b E N 0,, with
a < b and both incomparable to 7r. It is clear that aVrr = bV7r = 1 in IL, as well as in
N C". By Theorem 2.1.4 we get a/\7r < b/\ 7r in IL,. Since N 0,, is a meet-sublattice of
IL,, this inequality for the two meets still holds in N C". By Theorem 2.1.4 again, 1r is
left-modular in N C". In general, 1r is not modular in N C". If n _>_ 4, let a = 2n and
$2 1(n— 1)/23...(n-—2). Clear1y¢< 7r, 7r/\o =¢/\0‘ =0and 7rVa =¢Vo=1

in N C", so that (0', it) is not a modular pair.

Proposition 2.3.1 The characteristic polynomial of the non-crossing partition lat-

tice N 0,, satisfies

n—l

X(NC,,, t) = t X(NC,,_1, t) — Z x(NC,-, t)x(NC,,_,-, t).

i=1

Proof. Let it = 12... (n — 1). By Theorem 2.2.5 we have

x<Ncmt> = Z [u<b)r<i>-P<W">x(ib.bv no] .

bA1r=0
Note that b /\ 7r 2 0 if and only if any two numbers of [n — 1] are in different blocks
ofb, so eitherb=0orb=mnwith 1 SmSn—l.

If b = 0, then x([b,b V 7r],t) = x([0,7r],t) = x(NC,,_1,t). Thus we get the first
term of the formula. Now let b = mn. It is clear that b V it = 1, so we need to
consider the sublattice [b, 1]. Given any to E [b, 1], the edge mn (which may not be in
E(G,,,)) geometrically separates the graph G“, into two parts, G,“ and ng, which are

induced by vertex sets {1,2, . . . ,m, n} and {m, m + 1,. . . ,n - 1,n}, respectively. By

27

contracting the vertices m and n in both GM and Gw’g, we get two non-crossing graphs
GM and ng. It is easy to check that the map f : [b, 1] —-> N Cm x N Cum, defined

by f (Ga) 2 (Gw,1,Gw,2) is an isomorphism between these two lattices. Therefore
x([b, b V WI. t) = X(NCm, t)X(NCn-m. t),

and the proof is complete. I

For any to = Bl/B2/.../B;c E NC”, the interval [0,w] E” HiNCIBiI' Hence to
compute the Mbbius function of N Cm it suffices to do this only for 1. By Proposi-
tion 2.3.1 we have the recurrence relation

#(NCn) = X(NCm 0)

n-l

= _ Z X(NC,-, O)X(NC'.._.-, 0)

i=1
n—l

: _ Z ”(NC,)p(NCn—i)

z=1
with the initial condition p(NGl) = 1.

Consider a product 302:1 - - - 2:,,. In how many ways can we insert parentheses such
that there is no ambiguity as to the order of the multiplications? This number is called
the Catalan number and denoted by C“. For example, Co = 1 for 2:0; C; = 1 for 2:021;
02 = 2 for (2:021)2:2, 2:0(3132); C3 = 5 for ((2:021)2:2)2:3, (xo(xlxz))2:3, 230((2:12:2)2:3),
2:0(2:1(2:22:3)), (2:021)(2:22:3). It is routine to check that 0,, is uniquely determined by

the recurrence relation
n—l
Cu : E CiCn—l—i
.20

with the initial condition Co = 1. Therefore, by induction, p(NCn) = (—1)""IC,,_1.

An explicit expression for the Catalan number is
1 2
0,, = ( n).
n + 1 n

28

 

2.4 Shuffle Posets

The poset of shuffles was introduced by Greene [9], and he obtained a formula for its
characteristic polynomial
m n 1 .

x(w..,.,t) ——— (t — 1W}; (.)(,)(;:,)'.
In this section we will derive an equivalent formula by using Theorem 2.2.9. Before
doing this we need to recall some definitions and results which were given by Greene.
Let A be a set, called the alphabet of letters. A word over A is a sequence u =
u1u2.. . an of elements of A. All of our words will consist of distinct letters and we
will sometimes also use u to stand for the set of letters in the word, depending upon
the context. A subword of u is w = u,, . . . u,, where i1 < .. . < i1. If u, v are any two
words then the restriction of u to v is the subword uv of 11 whose letters are exactly
those of uflv. A shuffle of u and v is any word 8 such that s = uwv as sets (disjoint
union) and sn 2 u, SV 2 v as words.

Given nonnegative integers m and n, Greene defined the poset of shuffles Wm," as
follows. Fix disjoint words x = 2:1 . . . 2:", and y = y1 . . . y“. The elements of Wm," are
all shuffles w of a subword of x with a subword of y. The partial order is that v S w
if vx 2 wx, vy (_I w, as sets and vW =2 w" as words. The covering relation is more
intuitive: v -< w if w can be obtained from v by either adding a single y,- or deleting
a single 20,-. It is easy to see that Wm," has bottom element 0 = x, top element 1 = y

and is graded by the rank function
p(W) = (m - Ile) + IWyI-

For example, Wu is shown in Figure 2.2 where x 2 de and y = D.
It was shown by Greene that every shuffle poset is actually a lattice. To describe
the join operation in Wm,” Greene defined crossed letters as follows. Given u, v E

Wm,” then 2: E u (I v (I x is crossed in u and v if there exist letters y,, yj E y with

29

 

Figure 2.2. The lattice Wm

i g j and 2: appears before y,- in one of the two words but after y,- in the other. For
example, let x = def and y = DEF. Then in the two shuffles u = dDEe, v = Fde f ,
the only crossed letter is d. The join of u, v is then the unique word w greater than

both 11, v such that

wx = {2: E ux 0 VI | 2: is not crossed} (2.12)
w,, = 113. U vy.
In the previous example, u V v = DEFe. This join also shows that Wm,” is not
semimodular in general, because p(u) + p(v) = 3 + 1 < 5 = p(u V v) S p(u V v) +
p(u /\ v). Since (Wn,m)"‘ = Wmm, the meet operation in Wm,“ is as same as the join
operation in (Wn,m)‘. So to find the meet in the analogous way we need to consider
those letters y E 11 F) v n y crossed in u and v.
Greene also showed that subwords of x and subwords of y are modular elements -

of Wm". In particular, the empty set 0 is modular. It is also atomic since [0, 0] E Bm.

We now give our formula for the characteristic polynomial of Wm".

30

Proposition 2.4.1 The characteristic polynomial of the shuffle poset is

x<wm,.,t) = (t — 1>m;<—1)‘(’.’)(mf)t" *‘ (213)

Proof. If u/\ 0 = win Wm,” then wR 2 ux U 0,, = ux. So the meet uAQ) = 0 if
and only if x is a subword of u, i.e., the element 11 is a shuffle of x with a subword of
y. Phrthermore there is no crossed letter 2: in u and any v E [0, 0] since v3, = (ll. It
follows that (n V v)x = 11x 0 VI = v and (11 V v), = 113, U v3, 2 try as sets. Then we

get

p(u v v) — p(u) = [(m — Ivl) + luyli— [(172 — m) + Iuyli
= m—IVI = p(VI-p(0)-

Thus the map ru : [0, 0] —+ [u, (0 V 11] is rank-preserving.
Since [0, (21] E“ Bm, by Theorem 2.2.9 we get

X(Wm,nat) (t __ 1)m )2: p(u )t(m+n)—m—p(u).
uA0= 0
It is easy to see that the interval [0,u] is isomorphic to B,- where i = |uy|.

p(u) = (—1)luyl = (—1)"(“). Now we conclude that

" th h f t
X(Wm,mt) = (t“1m2[ enum ero ways 0

shume x with i letters of y

WE 1":f()(m:’)tn-i..

To determine the Mobius function of Wm,“ it suffices to compute p(l) since for

] <-1>*t"-‘

any w E Wm,” the interval [0,w] is isomorphic to a product of Wp,q’s for certain
p S m and q S n. For example, let x = defgh and y = DEFGHIJK then
p(DEeGhI K ) = p(W1,2)u(W2,1)u(Wo,2) because

[defgh, DECGhIK] ’5 Wd,DE X ngg X WQJK.

Simply plugging t = 0 into formula (2.13) gives us the Mbbius function p(Wmm).

31

Corollary 2.4.2 (Greene [9]) We have

W...) = (—1)m+"("’ + n). -

T1

2.5 NBB Sets and Factorization Theorems

Applying Theorem 2.2.9 we intend to inductively prove the Total Factorization The-
orem of the characteristic polynomial if L is an LL lattice. This theorem was given
by Blass and Sagan [3] and generalizes Stanley’s Total Factorization Theorem for SS
lattices. First of all, we would like to outline their work.

Given a lattice L, recall that A = A(L) is the set of atoms of L. Assign A an
arbitrary partial order, which we denote 3 to distinguish it from the partial order s
in L. A nonempty set D Q A is bounded below or BB if, for every d E D there is an
a E A such that

a<id and a<VD.

We say that B Q A is NBB (not bounded below) if B does not contain any D which
is bounded below. In this case we will call B an NBB base for the element 2: = V B.
One of the main results of Blass and Sagan’s paper is the following theorem which is
a simultaneous generalization of both Rota’s NBC and Crosscut Theorems (for the

crosscut A(L)).

Theorem 2.5.1 (Blass and Sagan [3]) Let L be a finite lattice and let 31 be any

partial order on A. Then for all 2: E L we have
Mm) = 2(4)“
B
where the sum is over all NBB bases B of 2:. I

Given an arbitrary lattice L, let A : 0 = $0 < 2:1 -< < 2:,, = 1 be a maximal

chain of L. Define the i”’ level of A by
A,={aEA|a§r, butafix,_1},

32

and we partially order A by setting a <1 b if and only if a E A,- and b E 11,- with i < j.
We say a is in lower level than b or b is in higher level than a if a <1 b. Note that the
level A,- is an empty set if and only if 2:,- is a non-atomic element. Also an atom a
cannot be S V S for any set S of atoms from strictly lower levels, since there is an
2:,- that is 2 all elements of S as well as V S but not 2 a. If all elements of A are
left-modular, then we say (L, A) (or simply L) is a left-modular lattice. In this case,

another property involving a join of atoms is given next.

Lemma 2.5.2 (Blass and Sagan [3]) If a and b are distinct atoms from the same

level A, in a left-modular lattice, then a V b is above some atom c E A,- with j < i. I

A pair (L, A) is said to satisfy the level condition if this partial order SI of A has

the following property.

I:
Ifa<b1<1b2<i...<1b,, thenaSVb,.

i=1

A pair (L, A) is called an LL lattice if it is left-modular and satisfies the level condition.

In this case, the characterization of NBB sets is described as follows.

Lemma 2.5.3 (Blass and Sagan [3]) In an LL lattice, a set B Q A is NBB if and

only if [B (I A] S 1 for every i. I
We define a generalized rank function p : L ——> N by
p(2:) = number of A,- containing atoms less than or equal to 2:.

Note that, for any 2: E L, we have p(2:) = p(6(2:)) where 6(2) is the maximum atomic
element in [0, 2:]. So p(1) is not necessary equal to n, the length of A. The following

lemma states the relationship between this p and NBB bases.

Lemma 2.5.4 (Blass and Sagan [3]) Let B be an NBB set in an LL lattice. Then
every atom a S VB is in the same level as some element of B. In particular, any

NBB base for 2: has eractly p(2:) atoms. I

33

Blass and Sagan generalized Stanley’s Total Factorization Theorem to LL lattices
using their theory of NBB sets. Here we present two inductive proofs for the LL
factorization theorem. In the first proof we will apply Theorems 2.2.9 as well as the

theory of NBB sets.

Theorem 2.5.5 (Total Factorization Theorem, Blass and Sagan [3]) If

(L, A) is an LL lattice then its characteristic polynomial factors as

X(L,t) = H(t — IAiI)
where the product is over all non-empty levels A,.

Proof of Theorem 2.5.5 I. We will induct on n, the length of A. The theorem is
trivial when n S 1. If A, = Q), then p(2:,,) = p(2:,,_1) and thus x(L, t) =2 x([0, 2:,,_1], t).
So we are done by induction.

If An 74 (0, consider y E H (L) Then, by Theorem 2.5.1, y must have an NBB
base. So if b E H(L) and b V 2:,,_1 then, by Lemma 2.5.3, b has an NBB base of
at most one atom from An. So b = 0 or b E An and p(b) S 1. Now it suffices to
check that T5 is rank-preserving on H (0, 2:,,_1) U {2:,,_1} for every b E A" since then
we get x(L,t) = x([0,2:,,_1],t)(t — |A,,|) by Theorem 2.2.9. Because An 95 Ill and
p(b) :2 1, T1, is rank-preserving on {2:,,_1}. Given any y E H (0,2:,,..1), suppose B
be an NBB base for y. By Lemma 2.5.3, B’ = B U {b} is an NBB base for rb(y).
Now p(rb(y)) = [B’| = [B] + 1 = p(y) + p(b) by Lemma 2.5.4. Hence p(b,rb(y)) =

p(n(y)) - p(b) = p(y) = p(é, y)- I
In a similar way, Corollary 2.2.10 provides us with an inductive proof for Theo-
rem 2.2.2. Note that the lattice in Theorem 2.2.2 is pure, so p(l) equals the length
of A. Therefore the product (2.5) is over all levels A, (including empty ones).
We will use Theorem 2.2.5 for the second proof. This demonstration sidesteps the
machinery of N BB sets and reveals some properties of LL lattices in the process. To

prepare we need the following two lemmas.

34

Lemma 2.5.6 If w is a left-modular element in L and v —< to, then v V u j w V u

for any u E L.

Proof. Suppose not and then there exists 3 E L such that vVu < s < qu. Taking
thejoin withw and usingva 2 w, we get wV(vVu) =st =wV(qu). So
we should have w A (v V u) < w A s < w A (w V u) = w by Theorem 2.1.4. Combining

this with v S w A (v V u), we have a contradiction to v < w. I

Lemma 2.5.7 If (L, A) is an LL lattice with A : 0 = 20 -< 21 < -< 2,, = 1 and
A,, # (0, then ([b, 1], A’) is also an LL lattice for any b E A,, where A’ consists of the

distinct elements of the multichain

I I l I I "
b220j21j2zj...j2n 2S2” 1=1

where 2: = 2:, V b, 0 S i S n — 1. Furthermore we have [A] = [A1] for such i, where
A; = {a E A(b,1)|a S 2: but a S 2L1}.

Proof. By Lemma 2.5.6, the chain A’ is indeed saturated. So A’ is a left-modular
maximal chain by Proposition 2.1.5.

Let 1(2) 2 rb(2) = 2 V b. It is surjective (see the proof of Lemma 2.2.8) and
order-preserving from [0,2,,_1] to [b, 1]. Also let A = A(0,2,,_1) and A’ = A(b,1).
First, We prove that the map 7' : A —> A’ is well-defined and bijective. Suppose that
there is an a E A,- such that b —< 2 < r(a) = a V b for some 2:. By the level condition
and Lemma 2.5.2, in L any atom c S a V b is in a level at least as high as a and
only one such c is in A,, namely a. Since 2: < a V b and a S 2, any atom d S 2
is in a higher level than a. It follows that 2,- A 2: = 0. Now b V (2,- A 2) = b and
(b V 2,) A 2 2 (b V a) A 2 = 2 contradicts the left-modularity of 2,. We conclude
that r : A —> A’ is well-defined. The restriction rlA is surjective since 7' is surjective

and order-preserving. To show injectivity of r] A, let us suppose there are two distinct

35

atoms u and U such that r(u) = r(v). If u and v are from two different levels then this
contradicts the level condition. If u and v are from the same level, by Lemma 2.5.2,
there exists an atom c in a lower level such that c S u V v S r(u) V r(v) = r(u),
contradicting the level condition again.

Now let us prove [A,[ = [A1]. This is trivial for i = 1. Let u E A,- for some
nonempty A,- with 2 S i S n — 1. It is clear that u V b S 2,- V b. Assuming that
qu S 2,-1Vb, we get (bV2,-_1)A(qu) = qu. But bV(2,-__1 A(qu)) = bV0 = b
contradicts the modularity of 2,4. Thus r(A,-) g A1 and then the bijectivity of r|A
implies that [A,[ = [A1[ for all i S n — 1.

Since TIA is bijective and level-preserving, if T(a) S V1;l r(b,-) for some 7(a) 4
r(b1) <ir(b2) <1...<ir(bk) in [b, 1], then a < aVb S(V1‘:1b,-)waith a<ib1<ib2<]...

<1 bk <1 b in L. Thus ([b, 1], A’) satisfies the level condition. I

Proof of Theorem 2.5.5 II. We will induct on n = €(A). The cases n S 1
and A,, = Q) are handled as before.

If A,, # (21 and b is atomic with b A 2:,,_1 = 0, then b can only be above atoms in
A,,. So by Lemma 2.5.2, b must be the join of at most one atom, i.e., either b = 0 or
b E A,,. Thus by Lemma 2.5.7 and induction we get, for any b E A,,

X(Ib.il,t) = H (t- IAiI) = x([0,x.._1],t)
iSn—l
where the product is over non-empty A,. Applying Theorem 2.2.5 gives x(L,t) =

x([0, 2,,_1], t)(t — [A,,I), so again we are done. .

To end this chapter, we depict the relationships between all factorization theorems
that we have discussed. In the following chart, “TF” means “Total Factorization

Theorem” and “PF” stands for “Partial Factorization Theorem.”

36

Theorem 2.2.5
1 Blass and Sagan’s TF
Theorem 2.2.9 Stanley’s TF
Corollary 2.2.10

Stanley’s PF

37

CHAPTER 3

EDGE LABELINGS OF POSETS

3.1 R—Labelings and Shellable Posets

This section is an introduction to the basic terminology and theorems for edge label-
ings of posets. The covering relation 2 -< y is also an edge in the Hasse diagram of P,
so the set £(P) 2 {2y | 2 < y for 2,y E P} is called the edge set of P. If [u, v] Q P
we write 8 (u, v) for £([u, v[). Sometimes, instead of using 2y, we will write the edge
pair as 2 -< y. An edge labeling of P is a map A : £(P) —-> A, where (A, S) is some
poset (usually the integers). We will use “S” for both P and A if there is no confusion;
otherwise we will write S A for A to distinguish from S for P. Given 2 -< y -< 2, if
A(2y) < A(yz) we will say A is strictly rising at y in this chain; otherwise A has a strict
descent at y. Note that at a strict descent we do not necessary have A(2y) 2 A(yz)
since A is a poset. “Weakly rising” and “weak descent” are defined in the analogous
way. Here we study two important concepts: R-labeling and lexicographic shelling.

Both of them unveil combinatorial properties of posets.

Definition 3.1.1 Let P be a bounded poset. An edge labeling A : 8 (P) —+ A is called

a strict R—labeling of P if, for every interval [2, y] of P, there is a unique saturated

38

chain 2 = 20 < 21 —< -< 2,, = y satisfying
A(2021) < A(IBlQIg) < ' ' ' < A($k_1$k). (3.1)

We will call this chain the rising chain from 2 to y and denote it by C,(2, y). A poset

P possessing a strict R-labeling A is called a strict R—poset.

Replacing “<” with “S” in (3.1) defines a weak R-labeling and a weak R-poset. A
strict R-labeling is not necessary a weak R-labeling, since one might have more than
one weakly rising chain. An R-labeling is one that is either a strict or weak R-labeling.
The concept of R-poset is defined analogously. Note that if [2, y] is an interval of an
R-poset P, then the restriction of A to 8 (2, y) is still an R-labeling. So any property
satisfied by an R-posets P is also satisfied by any interval of P.

Let P be an poset with a strict R-labeling A. A falling chain from 2 to y is a

saturated chain D : 2 = 20 < 21 < -- - < 2,, = y satisfying
A(2,-_12,-) 7t A(2,-2,-+1), for all 1 S i S k —— 1.

Replacing “5(” with “S” we can define a falling chain in a weak R-poset.
Let P be a bounded pure poset of rank n with the rank function p. If S Q [n —- 1]

then we define the poset
P5={2EP|2=0,lorp(2)ES},

called the S -rank-selected subposet of P. For instance, we have P0 = Cl and P[,,_1] =
P.
The following theorems give connections between R—labeling and the Mbbius func-

tion.

Theorem 3.1.2 (Stanley [17]) Let P be a pure R-poset of rank n and let S Q
[n — 1]. Then (—1)'S'+lp(P5) is equal to the number of ma2imal chains M : 0 = 20 <
21 -< < 2,, = 1 of P for which the labeling A has descents e2actly at those 2,- with

iES.I

39

Corollary 3.1.3 (Stanley [17]) IfP is a pure R-poset than for all 2, y E P
u(2,y) = (—1)p(y)‘p(’)(number offalling 2—y chains). I

Theorem 3.1.4 (Bjiirner and Wachs [6]) If P is an R-poset {not necessary a

pure one}, then for all 2, y E P

p(2:, y) = number of even length falling chains in [2, y]

— number of odd length falling chains in [2, y]. I

Shellability is studied for simplicial complexes in algebraic topology and also has
properties of a combinatorial nature. We will only treat this subject for posets because
we are focusing on combinatorics, not topology. A poset P is said to be shellable if
its maximal chains can be ordered M1, M2,. . . , M, in such a way that if 1 S i < j S t
then there exist 1 S k < j and 2 E MJ- such that M,- H M,- Q Mk (1 M, = M, — {2}.
Various types of edge-labelings were introduced by Bjérner and Wachs that imply
Shellability.

For the labeling poset A, let A°° denote the set of all strings ((11,... ,ap) with

a,- E A and variable length p. The lericographic order S, on A°° is the one such that

(a1,...,ap) <1(B1,...,Bq)
if and only if either
1. a, 2B,- fori= 1,2,...,qandq<p, or
2. a,- # B,- for some i and a,- < B,- for the least such i.

Given a saturated chain C : 20 -< 21 —< . . . < 2:,, in an edge-labeled poset we label the
chain by
A(C) = (A(2021), . . . , A(2,,_12,,)).

40

Definition 3.1.5 An edge labeling A of P is called an EL—labeling (edge lexicographic
labeling) if

1. A is an R-labeling, and

2. given any interval [2, y], the unique rising chain C, satisfies A(C,(2, y)) <1 A(G)

for any other ma2imal chain C in [2, y].

Building on the work of Bjorner [4] for pure posets, Bjdrner and Wachs [6] showed
that if any poset has an EL-labeling then it is shellable. So a poset admitting an
EL—labeling is said to be EL—shellable. An equivalent condition to EL—shellability is

as follows.

Proposition 3.1.6 (Bjiirner and Wachs [6]) Labeling A is an EL-labeling of P if

and only if
1. A is an R-labeling, and

2. given any interval [2,y], if C,(2,y) : 2 = 20 -< 21 < < 2,, 2 y then

A(221) < A(2z) for all z ¢ 21 such that 2 < 2 S y.

Some important EL-sellable posets have following stronger property which is the

dual of (2) in previous proposition.
Definition 3.1.7 An edge labeling A of P is called an SL-labeling if
1. A is an EL-labeling, and
2. given any interval [2,y], if C,(2,y) : 2 = 20 < 21 < < 2,, = y then
A(zy) < A(2,,_1y) for all z 74 2,,-1 such that 2 S 2 -< y.

A poset admitting an SL-labeling is said to be SL-shellable. Depending on whether
the R—labeling is strict or weak, the same will be said about the EL-labeling or SL-
labeling. However, the requirement (2) in Proposition 3.1.6, as well as in Defini-

tions 3.1.5 and 3.1.7, is always “strictly less” even for a weak EL— or SL—labeling.

41

3.2 Left-modular Lattices

Unless noted otherwise in this section we assume that the lattice L is left-modular
with a left-modular maximal chain A : 0 = 20 -< 21 —< < 2,, = 1. We define an

edge labeling AA of L by
AA(2y) = min{i [ 2, V 2 = 2:, V y}. (3.2)

Clearly AA(2,_12,-) = i for i = 1,2,. ..,n. So AA is a natural labeling induced by A.

Since all 2,- are left-modular, by Theorem 2.1.4 we have an equivalent definition
AA(2y) = min{i [ 2, A 2 75 2,- A y}.

It is easy to check that if 2, V 2: = 2, V y then 2,- V 2 = 2,- V y for any 3' > i. Thus we

have two more equivalent definitions

AA(2:y) = max{i + 1 [ 2,- V 2 ¢ 2, V y} (3.3)
: max{i + 1 [ 2, A 2 = 2, A y}. (3.4)

Combining (3.2) and (3.4), we get following property.

Lemma 3.2.1 The labeling AA(2y) = i if and only if both 2, V 2 = 2, V y and

2,-1 A2 = 2,-1 Ay. I

In the following proposition we do not require that all elements of A are left-

modular. The left-modularity of a single element 2,- is sufficient.

Proposition 3.2.2 1. U2, is left-modular and AA(2y) = ifor an edge 2y E €(P),
then

2,-1V2<2,_1Vy=2,V2=2,Vy, (3.5)

$i_1A$=$i_1Ay=$iA$'<$i/\y. (3.6)

42

2. If 2, is left-modular, then there are no u, v, 2, y E L such that u < v S 2 -< y

and AA(uv) = AA(2y) = i.

Proof. (1) By definition we have 2,-1 V 2 < 2,_., V y S 2, V y = 2, V 2, and
2,-1 V 2 S 2:, V 2 from Lemma 2.5.6. So (3.5) holds. The second statement follows
by a dual argument from the equivalent definition (3.4).

(2) Suppose AA(uv) = AA(2y) = i. Let s = 2,_1 V 2 and t = 2,_, V y. From part
(1) and v S 2, we get 2,Vv = 2,_1 Vv S s -< t = 2,Vy. Now take the meet with 2,
to get 2, =2,As =2,At=2,. On the other hand, 2,Vs =2,V2:=2,Vy=2,Vt.

This is a contradiction to Theorem 2.1.4. I

Property (2) shows that the number i cannot be a label twice on any saturated chain
of L.

Now we would like to introduce another induced labeling. Let L be any lattice.
Recall the definition of irreducible elements in Section 1.2 and let I (L) be the set of
irreducible elements of L. Given a map to : I (L) -—+ IP’, it induces an edge labeling by
the rule

A1(2y) = min{w(z) [ z E I(L) and 2 < 2 V 2 = y}.

This is well-defined, because every 2 E L can be written as a join of irreducibles. If
A I is an R-labeling then to is called an admissible map.

Now let (L, A) be a left-modular lattice, and let
21(2) 2 min{i [ 2 S 2,}

for any 2 E I (L) The values of to partition I (L) into n blocks (levels) 11, [2,. . ., 1,,
where I, = {z E I(L) [ w(z) = i}. We also denote I, = {z E I(L) [ 2 S 2} for any

2 E L. Clearly I,“ = Ugh, I, for i = 1,2,. . . ,n. An equivalent definition for A1 is

A1(2y) = min{w(z) [ z E Iy — It}.

43

We will show that the map a: induced by the left-modular chain A is admissible.
First of all, we would like to show that A; = AA on E (L) It is clear that A1(2,_12,) =

i = AA(2,_12,) for any i. Also if z is an irreducible element with y -< 2 then
MW) = w(2) = AMyZ). (3.7)
where the second equality is from Lemma 3.2.1.

Lemma 3.2.3 We have AA = A1.

Proof. If A1(2y) = i there is a z E I(L) such that 2 V 2 = y and w(z) = i, so
2, V 2 = (2, V 2) V 2 = 2, V y. This implies AA(2y) S i, so AA S A, on £(L).

We assume, towards a contradiction, that AA(2y) = j < i = A1(2y) for some
y E L with y > 2. By Proposition 322(2) no edge in [0,2] is labeled j by AA, so all
irreducibles in [0,2] are labeled other than 3' by (3.7), i.e., j E w(I,,). Also we know
that w(Iy — 1,.) Q [i,n[, soj E w(Iy) and then IJ-FIIy = 0. Thus 2jAy = V(I,,J. 01,) =

V(I,,J._1 H I,,) = 2:,--1 A y. This contradicts (3.6). I
Let 9,, = {22(2) | z E I(L), z S 2}. A new method of labeling is defined by

An(2y) = min (93, — (1,).

Since A, :2 AA, Proposition 322(2) gives An = A1. So from now on we will just use
A to represent all three labelings.

We need to state two lemmas before our main result.

Lemma 3.2.4 Let L be left-modular with z E I(L) and 2 < 2 V 2 for some 2 E L.

Then each edge in the interval [2, 2 V 2] is labeled by a number S w(z).

Proof. Let w(z) = i and pick any edge u < v in [2,2 V2]. It is easy to check that
zVu=2V2:sz,sowehaveuV2,=uV(zV2,)=vV(zV2,)=vV2,. Thus

A(uv) S i. I

44

Lemma 3.2.5 Given any 2 < y in a left-modular lattice L. Let 2, z’ E 1,, — I, be
two distinct irreducibles such that 22(2) 2 w(z’) = minw(Iy — 1,). Then we have

2-<zV2=z’V2:.

Proof. The covering relation is directly from the previous lemma and Proposi-
tion 322(2). In fact A(2 < 2 V 2:) = 22(2). If 2 V 2 75 2’ V 2 then 2’ E IZIV(,,V,,) — Izw.
By the result we have just proved, we should have 2 V 2 -< 2’ V (2 V 2) and

A(z V 2 < z’ V (z V 2)) = w(z’) but this contradicts Proposition 322(2). I

Theorem 3.2.6 Left-modular lattices are SL-shellable.

Proof. Given any interval [2, y] in L. If 2 < y, the edge itself is the unique rising
chain. If 2 72 y, let 2 E 1,, — I,c be an irreducible such that 22(2) = i = minI.v(Iy — It).
The chain formed by concatenating the edge 2 4 2 V 2 and C',([z V 2, y]) (which is
the unique rising chain obtained by induction) forms a rising chain from 2 to y. It is
strict by Proposition 322(2). Since the number i must be a label on some edge of
any maximal chain in [2, y], any rising chain must have its first edge labeled by i. So
Lemma 3.2.5 implies the uniqueness of the rising chain. By the same lemma, A is an
EL-labeling.

Applying what we have just shown to the dual lattice L“, which has left-modular
chain A‘, we see that L“ admits an EL-labeling A‘. Using (3.4) we see that A"(2y) 2:

n + 1 - A(y2). So EL-shellability of L‘ implies SL—shellability of L. I

It follows from Proposition 322(2) that A is a strict as well as a weak R-labeling.
This theorem is a generalization of one for supersolvable lattices [16], but left-modular
lattices are not always pure as supersolvable ones are. In the case of a non-pure lattice,
we see that A is labeled by [n] while any other maximal chain is labeled by a subset

of [n] without repetition. Thus we have following proposition.

Proposition 3.2.7 Let (L, A) be a left-modular lattice. The length of A is ma2imum

among all ma2imal chains in L. I

45

This result also follows from a general theory of Shellability [6]: the first maximal
chain of a shelling must be of maximum length among all maximal chains.

We now look at the Tamari lattice, Tn, as an example. Consider all proper paren-
thesizations 7r of the word 2021 . . . 2,,. It is well known that the number of these is
the Catalan number 0,, as was mentioned in Section 2.3. Partially order this set by

saying that 0 covers 1r whenever
7r=...((AB)C’)... and o=...(A(BC))...

for some subwords A, B, C. The corresponding poset turns out to be a lattice called
the Tamari lattice Tn.

A left bracket vector, (v1, . . . ,vn_1), is a vector of nonnegative integers satisfying
1.0 _<_ v,- _<_ i for all i, and

2. if S,- = [y,-,i] then for any pair 5,, 5',- either one set contains the other or

SiflSjZQ.

The number of left bracket vectors is also C“. In fact given a parenthesized word 17
we have an associated left bracket vector v = ('21, . . . ,vn_1) defined as follows. To
calculate 1),, start at 2,- in 1r and move left, counting the number of 2’s you pass
(including 2,- itself) and comparing it with the number of left parentheses you pass
until these two numbers are equal. Then 1), = j where 2,- is the last 2 passed before
the numbers balance. It is not hard to show that this gives a bijection between
parenthesizations and left bracket vectors, thus inducing a partial order on the latter.
In fact this induced order is just the component-wise one. The elements covering
(v1,...,v,,_1) are those (w1,...,w,,_1) such that w,- = v,- for all except one value
j, and w,- is the least number > v,- that does not violate hypotheses (1) and (2).

Figure 3.1 gives the parenthesized and bracket vector versions of T3.

46

($o($1($2$3))) (1, 2)

($0(($1$2)$3)) (1,1)
(($0($1$2))$3) (($031)(1‘2$3)) (1,0) (0,2)
(“3093032)933) (0,0)
(a) Parenthesized version (b) Left bracket version

Figure 3.1. The Tamari lattice T3

Given left bracket vectors 2) = (211,. . . , on) and w = (221,. . . ,m,) then
1) V w = (max{v1,w1}, . . . ,max{v,,,w,,}).

The Tamari lattice Tn is left-modular and a left-modular chain was given in [3] as
follows.
A:(0,...,0) <(1,0,...,0) < (1,1,0,...,0)
< (1,2,0,...,0) < (1,2,1,0...,O) < < (1,2,3,...,n— 1).
For an edge 1) = (121,...,vj,...,v,,_1) < w = (v1,...,vj_1,wj,vj+1,...,v,,_1), we
consider
2,c = (1,2,...,j—1,wj,0,...,0), and
11%-] = (1,2,...,j — 1,22,- —1,0,...,O)
wherek=1+2+...+(j—1)+w,~,andcompute
vV2,c = (1,2,...,j — 1,wj,vj+1,...,v,,_1) = wV2k, but

’UVSEk_1=(1,2,...,j— 1,1.UJ' -' 1,’Uj+l,...,’Un_1)

#wV2k_1 = (1,2,...,j— 1,wj,vj+1,...,v,,_1)

Therefore A(vw) = k is the explicit SL-labeling for the edge vw. Figure 3.2 shows
this labeling for T4.

47

 

Figure 3.2. The Tamari lattice T4 and its SL—labeling

3.3 Shellability of Rank-selected Posets

Let P be a bounded pure poset with rank function p and p(L) = n. Recall the
definition of rank-selected poset P5 in Section 3.1. In particular, if 0 S k + 1 < l S n

and S = [1, k] U [l, n — 1] we have the truncation
Pi = P5 = {1‘ E P | PM E [0,k] U {Mil}-

If P admits an R-labeling A : E (P) —-> A, we would like to construct an R—labeling for
P,:. Let us write A for A with a I and f) adjoined on top and bottom and order ll x A
component-wise, i.e., (a, b) S (c, d) if and only if a S c and b g d in ll.
Define a labeling }\ : P; —+ A x A by
(Mics/W) if p(y) S k.
may) = (i, Macy» 1222) 21,
(A(22'),/\(y’y)) else, where C',(2,y) = 2, 2’, . . . , y’, y.
Lemma 3.3.1 3‘ is an R-labeling for P; if P is an R-poset.

48

Proof. The only interesting case is for an interval [2,y] where p(2) = p _<_ k and
p(y) = q 2 l. Suppose that C = C,(2,y) : 2 = 2,,, 2p+1,..., 2., = y in P, then
C',’c : 2p, . . ., 2k, 2;, . . ., 2,, is a rising chain in Pi. Given any other chain D; : 2 =
yp, yp+1,..., yk, y,,..., yp 2: y in Pi, it can be extended to be a chain D : 2 =
yp, yp+1, . . ., yk_1, C,(yk,y;), yz+1, . . ., yp = y in P. This chain D must be different
from 0,.(2, y), so it has descents at some of yp+1, . . . , yk and y,, . . ., y,,_1, and then so

does Di. Thus the rising chain C}c is unique. I

Note that this lemma works for both strict and weak R—posets.

Theorem 3.3.2 If P, a pure poset of rank n, has an R-labeling then so does P5 for

anyS§[n—1]. I

Suppose SU{O,n} : [11,k1]U[l2,k2]U...U[lp,k,,] with 0 =11 < k1+1 < I; < k2+1<
l3 < . .. < l? g k, = n. Now we merely truncate ranks in the intervals (hi, 2+1) one

by one. A much simpler R-labeling for P5 is 5‘ : £(P5) -—+ A? defined by

A A A

(1, . . . , 1, A(2y),0, . . . ,0) if p(2) E [l,-,k, — 1], where A(2y)
is the ith term of the string,

A A

...,1, A(22’), A(y'y),0, . . . ,0) ifp(2) = k,, where A(22’) is the it”

I

term and C',(2,y) = 2, 2’,..., y, y.
Example 3.3.3 Let B = B", the Boolean algebra on [n]. A natural R—labeling for
anedgeU-<V(UCVand |U|+1=|V|)is

A(UV) = V— U

where V — U represents the single number in the set. This labeling is a strict as well
as weak one.

We can count the falling chains C in B]c to compute the Mobius function. Let U,

V E C and WI 2 k, IV] =2 I. There are unique (2) - U and V - [n] falling chains. So

49

we need only ensure descents at both U and V where U C V. By definition of 5‘, this

amounts to
(a) minU > min(V — U) and (b) max(V — U) > max([n] — V).
Elementary set theory shows this is equivalent to
(a') minV E U and (b') n E V, [n — i + 1,n] Q U

where [n — i + 1,n] = {n — i + 1,n— i + 2,...,n} is the final run in V for some

1 S i S l. So |u(B,’¢)| equals

1
Z (# of V with final run [n — i + 1, n]) (# of corresponding U)

' = . (”Ii:1)[(’;1)-(’;:;l)l

i=1
t

=(’2:i)(’;l)—:(“;::1)(’;::-1)-

This sum has no closed form, but when k = 0 it zeros out and we obtain the same

result as in [20]:

“(33) = (—1>"-‘+1(’,‘_‘11).

If P is shellable so is P5. But whether a rank-selected poset preserves EL- or
SL—shellability remains open. To inherit these two properties by using the induced
labeling :\ we need a stronger hypothesis. A thrifty labeling is a strict R-labeling such

that
|A(5(93,y))| = PM?!)
for any 2, y E P. Since A(C’,(6, 1)) = A(£(L)) as sets in this case, the labeling poset
A must be a total order.
Theorem 3.3.4 If P admits a thrifty EL-labeling (resp. SL-labeling) then P5 is EL-

shellable (resp. SL-shellable) for any 5' g [n — 1].

50

Proof. It suffices to prove this for Pi. By Theorem 3.3.2, we need only show that A
satisfies Proposition 316(2) for those intervals [2, y] with p(2) = k and p(y) = q > I.
In Pi, suppose 22' is the first edge in the 2 —- y rising chain and 2” E P; with
2 -< 2” S y, 2” ¢ 2’. By the thrifty condition in P, A(C,(2,2’)) is an increasing
string consisting of the l — k least numbers in A(£(2,y)) while A(C’,(2,2”)) is also
an increasing string consisting of some other I — k distinct numbers in the same set.

Therefore A(22’) < A(22”). SL-shellability can be prove in an analogous manner. I

Many lattices have edge labelings satisfying the thrifty hypothesis, for example,
the natural labeling for the Boolean algebra B”. In fact, the labeling AA for any pure
left-modular lattice (L, A) is a thrifty SL—labeling.

For the rest of this section we will discuss a thrifty edge labeling for the non-
crossing partition lattice N 0,, which is not a left-modular lattice. The partition
lattice IL, is a supersolvable lattice with a left-modular maximal chain A : f) < 12 <
123 < < [n] =1. We will label each edge 1...(i— 1) < 1...i on this chain by
i instead of i - 1, for example A(O < 12) = 2. The induced labeling A = AA is a
thrifty SL-labeling with A(£(l'l,,)) = [2, n]. In fact, there is an explicit formula for A.

If 7r < o with two blocks B, C in 7r merged into one in a then
A(7ro) = max{min B, min C}.

Suppose 71' < o in IL,, and let 1r = Al/Bl/C1/.../A2/Bz/C'2/.../..., o =
Zl/Z2/... where Z, = A, EH B,- tfl 0,- w We also assume that a,- = minA, <
b,- = min B,- < c,- = min C,- < for each i. Then C',(1r,o) in 11,, is the unique chain
by only merging blocks with the same subscript such that A(C',(1r,o)) is the sequence
gotten from {b1, c1, . . . , b2, 0,», . . .} by rearranging the numbers in increasing order. If

both it and o are non-crossing, it is clear that C,(7r, 0‘) Q N C". So A is still a thrifty
SL-labeling for N C“.

51

3.4 CR—labelings and CL-labelings

Let M(P) be the set of maximal chains of P, and M8 (P) be the set of pairs (M, 2y) E
M(P) x 8 (P) consisting of a maximal chain M and an edge 2y along that chain. A

chain-edge labeling of P is a map A : ME (P) ——) A, where A is some poset, satisfying

A2iom CE: If two maximal chain M : f) = 20 -< 21 < < 2;, == 1 and
M’ : f) = 26 -< 2’1 —< -< 2] = 1 coincide along their first d edges, then

A(M,2,-_12,-) = A(M',2§_12:) for i = 1,. . . ,d.

An edge labeling A naturally induces a chain-edge labeling A’ by letting A’ (m, 2y) =
A(2y) for any maximal chain m containing 2 and y.

If [2, y] is an interval and R is a saturated chain from f) to 2, then the pair ([2, y], R)
will be called a rooted interval with root R, and will be denoted [2, y] R. If M is any
maximal chain of [2,y], we shall also consider it as a maximal chain of the rooted
interval [2, y] R and denote it by M R. Then R U M is maximal chain of [6, y].

Let A be a chain-edge labeling of P and [2, y] R a rooted interval. By axiom CE,
if M is a maximal chain of [2, y] and M ' , M " are maximal chains of P that contain
R U M, then the first d entries of A(M') and A(M”) coincide where d = ((R U M).
Hence the labeling on M depends only on a given root R of [2,y] but not on an
extended maximal chain M’ in P. Like an edge labeling, with each maximal chain
M : 2 = 20 —< 21 -< .. . —< 2,, = y in a rooted interval [2, y] R we associate the ordered
string

A(MR) = (A(M', 2021), . . . , A(M', 2k_12k))

where M’ is any maximal chain containing R n M. Note that the length of the tuple
A(MR) depends on the length of the chain M. We will use the lexicographic order on

these strings.

Definition 3.4.1 Let A : MS —> A be a chain-edge labeling of a bounded poset P.

52

1. A is called a CR-labeling if in every rooted interval [2,y]R there is a unique

ma2imal rising chain which is denoted by Cr([$, y] R).

2. A CR-labeling A is called CL—labeling if for every [2, y] R the unique rising chain
is strictly le2icographically first, i.e., A(C’,([2,y]R)) <1 A(NR) for any other

ma2imal chain N in [2, y] R.

A poset admitting a CL—labeling (resp. CR—labeling) is called a CL-shellable poset
(resp. CR-poset). The definitions of CR- and CL-labeling generalize the notion of R-
and EL-labeling, respectively. Bjéirner and Wachs [5] introduced these generalizations
and proved that CL-shellable posets are shellable. They also gave the analog of the

main result in Section 3.3 in this context.

Theorem 3.4.2 (Bjfirner and Wachs [5]) IfP is a pure CL-shellable poset (resp.
CR-poset) of rank n, then P5 is still a CL-shellable poset (resp. CR-poset) for all

S§[n—1].I

53

BIBLIOGRAPHY

BIBLIOGRAPHY

[1] G. Birkhoff, A determinant formula for the number of ways of coloring a map,
Ann. of Math., II Ser 14 (1913), 42—46.

[2] G. Birkhoff, “Lattice Theory,” Third Edition, American Mathematical Society,
1967.

[3] A. Blass and B. Sagan, Mc'ibius functions of lattices, Adv. in Math. 127 (1997),
no. 1, 94—123.

[4] A. Bj6rner, Shellable and Cohen-Macaulay partially order sets, Trans. Amer.
Math. Soc. 260 (1980), no. 1, 159—183.

[5] A. Bjéirner and M. Wachs, Bruhat order of Coxeter group and Shellability, Adv.
in Math. 43 (1982), 87—100.

[6] A. Bjérner and M. Wachs, Shellable nonpure complexes and posets I, Trans.
Amer. Math. Soc. 348 (1996), no. 4, 1299—1327.

[7] A. Bjéirner and M. Wachs, Shellable nonpure complexes and posets II, Trans.
Amer. Math. Soc. 349 (1997), no. 10, 3945—3975.

[8] H. Crapo, The M6bius function of a lattice, J. Combin. Theory 1 (1966), 126—
131.

[9] C. Greene, Posets of shuffles, J. Combin. Theory Ser. A 47 (1988), 191-206.
[10] P. Hall, The Eulerian functions of a group, Quart. J. Math. 7 (1936), 134—151.

[11] G. Kreweras, Sur les partitions non-croisées d’un cycle, Discrete Math. 1 (1972),
333—350.

[12] G.-C. Rota, On the fundations of combinatorial theory I. Theory of Mobius
functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340—368.

54

. agan, y t e c aracterrstlc po ynomla actors, u . mer. at . oc.
[13BS Whhh "1 '1f BllA MhS
(NS) 36 (1999), No. 2, 113—133.

[14] R. Stanley, Modular elements of geometric lattices, Alg. Univ. 1 (1971), 214—217.

[15] R. Stanley, Ordered structures and partitions, Memoirs Amer. Math. Soc. 119
(1972).

[16] R. Stanley, Supersolvable lattices, Alg. Univ. 2 (1972), 197—217.
[17] R. Stanley, Finite lattices and Jordan-Hiilder sets, Alg. Univ. 4 (1974), 361-371.

[18] R. Stanley, “Enumerative Combinatorics, Volume 1,” Wadsworth & Brooks/
Cole, Pacific Grove, CA, 1986.

[19] L. Weisner, Abstract theory of the inversion of finite series, Trans. Amer. Math.
Soc. 2 (1935), 474—484.

[20] P. Zhang, Truncated Boolean algebra as subspace arrangements, Proc. of the
Twenty-eighth Southeastern International Conference on Combinatorics, Graph

Theory and Computing (Boca Raton, FL, 1997), Congr. Numer. 128 (1997),
121—127. '

55

"llllllllll[lllllll