QUOTIENT POSETS AND THE CHARACTERISTIC POLYNOMIAL
By
Joshua William Hallam

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
Mathematics - Doctor of Philosophy
2015

ABSTRACT
QUOTIENT POSETS AND THE CHARACTERISTIC POLYNOMIAL
By
Joshua William Hallam
In this dissertation we consider the generating function for the M¨obius function of finite
partially ordered sets. This generating function is called the characteristic polynomial of
the partially ordered set. We are primarily interested in explaining why certain families of
partially ordered sets have characteristic polynomials where all the roots are nonnegative
integers. To this end we introduce the concept of a homogeneous quotient. These quotients
allow us to give new proofs of some well-known results in the literature as well as give
generalizations of them. We finish by showing how to use homogeneous quotients to give
unified proofs of some classic results about the M¨obius function.

ACKNOWLEDGMENTS

First and foremost I would like to thank my advisor, Dr. Bruce Sagan, for all the support
and encouragement he has given me. It has truly been an honor to learn from him both
about mathematics as well as how to be a mathematician.
I would also like to thank all the graduate students at Michigan State, past and present.
In particular, I want to thank Dave Bramer for all the encouragement over the years.
Additionally, I would like to thank my parents, William and Kelly Hallam, who always
encouraged learning and supported me in all my endeavors. Finally, I would like to thank
my wife, Mobashera Hallam. Without her constant support, I would have never been able
to complete this work.

iii

TABLE OF CONTENTS
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Chapter 1 Introduction . . . . . .
1.1 Poset Basics . . . . . . . . . .
1.2 The M¨obius Function . . . . .
1.3 The Characteristic polynomial

.
.
.
.

.
.
.
.

v

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

1
1
7
10

Chapter 2 Quotient Posets . . . . . . .
2.1 The Basics . . . . . . . . . . . . . .
2.2 The Standard Equivalence Relation
2.3 Rooted Trees . . . . . . . . . . . .
2.4 Partitions Induced by a Multichain
2.5 Transversal Functions . . . . . . . .
2.6 Complete Transversal Functions . .
2.7 Crosscut-simplicial Lattices . . . .
2.8 LL lattices . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

16
16
20
28
32
41
47
53
57

Chapter 3 Classic Results About the M¨
obius Function . . . . . . . . . . . .

62

BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

iv

LIST OF FIGURES
Figure 1.1:

The Boolean algebra, B3 . . . . . . . . . . . . . . . . . . . . . . . .

2

Figure 1.2:

The poset of binary words, P3 . . . . . . . . . . . . . . . . . . . . .

3

Figure 1.3:

The claw with n atoms . . . . . . . . . . . . . . . . . . . . . . . . .

13

Figure 1.4:

Hasse diagrams for the partition lattice example . . . . . . . . . . .

14

Figure 2.1:

Hasse diagrams for partition lattice example with new labelings . . .

21

Figure 2.2:

Hasse diagrams for rooted trees . . . . . . . . . . . . . . . . . . . .

29

Figure 2.3:

A lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

Figure 2.4:

The Tamari lattice T3 . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Figure 2.5:

The weighted partition poset Πw
3 . . . . . . . . . . . . . . . . . . . .

51

Figure 2.6:

The Tamari lattice T3 with an SB-labeling . . . . . . . . . . . . . .

56

Figure 2.7:

A crosscut-simplicial lattice which does not have an SB-labeling . .

57

v

Chapter 1
Introduction

1.1

Poset Basics

We will use the following standard notation for certain sets of numbers.
• The nonnegative integers will be denoted by N.
• The integers will be denoted by Z.
• The set {1, 2, . . . , n} will be denoted by [n].
Let us now review some background material on partially ordered sets. See [14, Chapter 3]
for a more complete overview.
Definition 1.1.1. A partially ordered set or poset is a set P and binary relation ≤ on P
such that the following three properties hold for all x, y, z ∈ P :
1. x ≤ x (reflexivity),
2. if x ≤ y and y ≤ x then x = y (antisymmetry),
3. if x ≤ y and y ≤ z then x ≤ z (transitivity).
It is common to represent the poset P with binary relation ≤ as either (P, ≤) or just P
if the binary relation is clear from context. Additionally, it will sometimes be useful to write
≤ as ≤P , especially in the case when several posets are being considered.
1

{1, 2, 3}

{1, 2}

{1, 3}

{2, 3}

{1}

{2}

{3}

∅
Figure 1.1: The Boolean algebra, B3

We now consider an example of a poset. Let Bn be the set of subsets of {1, 2, . . . , n}.
For S, T ∈ Bn , define a binary relation ≤ on Bn as S ≤ T if and only if S ⊆ T . It is easy to
verify that all three properties of a poset are satisfied and so (Bn , ⊆) is a poset. It is called
the Boolean algebra.
It is often useful to consider a graphical representation of a poset. We do this by using
Hasse diagrams. Before we can define such a diagram, we will need to develop some more
terms associated with posets. If P is a poset and x, y ∈ P , we say y covers x, and write
x

y, if x < y and there is no z with x < z < y. We call a poset finite if the underlying set

is finite. Given a finite poset, P , the Hasse diagram of P is a directed graph such that the
vertices of the graph are the elements of P and there is a directed edge from x to y whenever
x

y in P . We typically do not write arrows on the directed edges, instead we draw the

graph so that the edges are directed upwards. Figure 1.1 depicts the Hasse diagram of B3 .
Let P and Q be posets. We say a map ϕ : P → Q is order preserving if x ≤P y implies
that ϕ(x) ≤Q ϕ(y) for all x, y ∈ P . We say P and Q are isomorphic if there is a bijection
ϕ : P → Q such that ϕ and ϕ−1 are order preserving. In other words, we must have x ≤P y
2

111

110

101

011

100

010

001

000
Figure 1.2: The poset of binary words, P3

if and only if ϕ(x) ≤Q ϕ(y) for all x, y ∈ P . If P and Q are isomorphic, then we write
P ∼
= Q. If P and Q are finite posets, then checking if P and Q are isomorphic is equivalent
to checking that their Hasse diagrams are isomorphic as directed graphs.
We now give an example of a poset isomorphism. Let Pn be the set of all binary sequences
of length n ordered by saying a1 a2 . . . an ≤ b1 b2 . . . bn if and only if ai ≤ bi for all i. We
claim that Pn and Bn are isomorphic. To see why, define ϕ : Pn → Bn so that ϕ(a1 a2 . . . an )
is the subset of {1, 2 . . . , n} obtained by including i if and only if ai = 1. So for example,
ϕ(10100) = {1, 3}. First, it is obvious that ϕ is a bijection. Now suppose that a1 a2 . . . an ≤
b1 b2 . . . bn , then bi = 0 implies that ai = 0. Therefore, ϕ(a1 a2 . . . an ) only contains elements
that are also in ϕ(b1 b2 . . . bn ) and so ϕ is order preserving. Finally, suppose that S ⊆ T
and let ϕ−1 (S) = a1 a2 . . . an and ϕ−1 (T ) = b1 b2 . . . bn . Since S ⊆ T it must be that bi = 0
implies that ai = 0 for all i. This implies that a1 a2 . . . an ≤ b1 b2 . . . bn . It follows that
Pn ∼
= Bn . Figure 1.2 is the Hasse diagram of P3 . Comparing this with Figure 1.1 gives a
graphical verification that the two posets are indeed isomorphic when n = 3.

3

It will be useful to have names for some special elements of a poset. If a poset, P , has a
minimum element then we denote it by ˆ0P or just ˆ0 if P is clear from context. Similarly if
P has a maximum element we denote it by ˆ1P or ˆ1. In the example of Bn , ˆ0 is ∅ since every
set contains the empty set. Also, the ˆ1 of Bn is {1, 2, . . . , n} because every set is contained
in this set. For the rest of the paper, unless otherwise noted, we will assume that all of our
posets are finite and have a ˆ0. We, however, do not assume that all of our posets have a ˆ1.
Another set of important elements of a poset are the atoms. Let P be a poset, we say
a ∈ P is atom if a

ˆ0. The atoms of Bn are exactly the singleton subsets of {1, 2, . . . , n}.

The set of atoms of a poset P will be denoted by A(P ).
Let P be a poset and let S be a subset of P . The lower order ideal generated by S is

L(S) = {x ∈ P | x ≤ s for some s ∈ S}.

Similarly, we have the upper order ideal generated by S which is defined by

U (S) = {x ∈ P | x ≥ s for some s ∈ S}.

We say a set, S, is totally ordered if x, y ∈ S implies that either x ≤ y or y ≤ x. A
totally ordered subset of a poset is called a chain of the poset. If C : x0 < x1 < · · · < xn is a
chain, we say C is saturated if xi
chain in Bn is ∅

{1}

{1, 2}

xi+1 for all i = 0, 1, . . . , n − 1. An example of a saturated
...

{1, 2, . . . , n − 1}

{1, 2, . . . , n − 1, n}. In terms of a

Hasse diagram, a saturated chain of a poset is a directed path. The length of a chain, C, is
|C| − 1 where | · | denotes cardinality. The previous example of the saturated chain in Bn
has length n. We will also need the notion of a multichain. A multichain of a poset is like

4

a chain where we allow repetition of the elements. We say a multichain is saturated if the
underlying set forms a saturated chain.
If P has a ˆ0 then we say P is ranked if, for each x ∈ P , every saturated ˆ0–x chain has
the same length. Given a ranked poset, we get a rank function ρ : P → N defined by setting
ρ(x) to be the length of a ˆ0–x saturated chain. We then define

ρ(P ) = max ρ(x).
x∈P

In the case when P has a ˆ1, we have that ρ(P ) = ρ(ˆ1). Returning to our example of Bn ,
one can see that ρ(S) = |S| for all S ∈ Bn and that ρ(Bn ) = n.
If P and Q are posets, we define the product of P and Q written as P × Q as the set
P × Q with the binary relation ≤P ×Q such that (p1 , q1 ) ≤ (p2 , q2 ) if and only if p1 ≤p p2
and q1 ≤Q q2 . It is not hard to prove the following lemma.
Lemma 1.1.2. Let P and Q be posets, then P × Q is a poset. Moreover, if both P and Q
are ranked, then P × Q is ranked as well. In this case, the rank function is given by

ρP ×Q (p, q) = ρP (p) + ρQ (q).

Our running example, Bn , is in fact a product of smaller posets. To see why, define
Ck to be the poset whose elements are {0, 1, . . . , k} and whose order is the normal ordering
of the integers. We call Ck the chain of length k. For the Boolean algebra we have that
Bn ∼
= C1 × C1 × · · · × C1 . The isomorphism is essentially the isomorphism we gave before
n times
between Bn and the binary sequences of length n.

5

Given two elements x, y of a poset P , the meet or greatest lower bound of x and y (if it
exists) is the element z such that z ≤ x, y with the property that if w ≤ x, y, then w ≤ z. It
is denoted by x ∧ y. The join of x and y or least upper bound (if it exists) is the element z
such that z ≥ x, y with the property that if w ≥ x, y , then w ≥ z. It is denoted by x ∨ y.
A poset is called a lattice if every pair of elements has a meet and a join. Note that in the
case of finite posets this is equivalent to saying that every subset of elements has a meet and
a join. Moreover, note that every lattice has a ˆ0 and a ˆ1. The poset Bn is a lattice with
S ∧ T = S ∩ T and S ∨ T = S ∪ T .
Let L be a lattice. We say an element x ∈ L is atomic if there exists atoms a1 , a2 , . . . , an
where x = a1 ∨ a2 ∨ · · · ∨ an . As a convention, we will let ˆ0 be the join of the empty set. We
say a lattice, L, is atomic if every element of L is atomic. The lattice Bn is atomic since the
empty set is the empty union and since every nonempty set is the union of singleton sets.
On the other hand, we claim that for k > 1, the chain Ck is not atomic. Recall, that there
is at most one atom in any Ck . It follows that there are at most 2 elements of Ck which are
atomic. Therefore if k > 1, then Ck is not atomic.
Let L be a ranked lattice. We say L is (upper) semimodular if for all x, y ∈ L we have

ρ(x) + ρ(y) ≥ ρ(x ∧ y) + ρ(x ∨ y).

Note that we will suppress the adjective “upper” and just call such lattices semimodular as
is commonly done in the literature. We claim that Bn is semimodular. To see why, let S
and T be elements of Bn . Then the Principle of Inclusion-Exclusion implies that

|S| + |T | = |S ∪ T | + |S ∩ T |.

6

Recall that if R ∈ Bn , then ρ(R) = |R|. Also recall that S ∪ T = S ∨ T and S ∩ T = S ∧ T .
The previous equation now implies that for all S, T ∈ Bn we have

ρ(S) + ρ(T ) ≥ ρ(S ∧ T ) + ρ(S ∨ T ).

We conclude that Bn is semimodular.
Let L be a lattice and let x ∈ L. We say x is left-modular if for all y, z ∈ L with y ≤ z
we have
y ∨ (x ∧ z) = (y ∨ x) ∧ z.
If C is a multichain of L, then we say C is left-modular if all the elements of C are leftmodular. It is not hard to see that every element of Bn is a left-modular element and so any
multichain of Bn is left-modular.
If L is semimodular and contains a saturated ˆ0–ˆ1 left-modular multichain, then L is called
supersolvable. Note that it is typical to define supersolvable using saturated left-modular
chains as opposed to saturated left-modular multichains. Since saturated multichains always
contain an underlying saturated chain, this will not lead to any problems. Recalling that Bn
is semimodular and that every multichain is left-modular, we have that Bn is supersolvable.

1.2

The M¨
obius Function

One of the most important functions on a finite poset is its M¨obius function, µ. It is a
far-reaching generalization of the M¨obius function from number theory. While there is a
two-variable version of the M¨obius function, we will only need the one-variable version.
Definition 1.2.1. The (one-variable) M¨obius function of P is a map µ : P → Z defined
7

recursively so that
µ(x) = δˆ0,y .

(1.1)

x≤y

It is sometimes convenient to use the following equivalent formulation of µ.

µ(y) =






1




−

if y = ˆ0,
(1.2)
µ(x)

otherwise.

x<y

If we are using more than one poset, we may also use the notation µP to denote the M¨obius
function of P .
Let us consider the M¨obius function of Bn . We claim that µ(S) = (−1)|S| for every
S ∈ Bn . This can be seen by inducting on |S|. The base case is true by definition of µ.
Using the inductive hypothesis, we know that if T

S, then µ(T ) = (−1)|T | . Therefore,

equation (1.2) implies that
(−1)|T | .

µ(S) = −
T S

The number of subsets of S with size k is

|S|
k

and so

|S|−1

(−1)k

µ(S) = −
k=0

|S|
.
k

The binomial theorem now implies that µ(S) = (−1)|S| .
One of the most important results about the M¨obius function is the M¨obius Inversion
Theorem (see [14, Proposition 3.7.1]). We do not discuss it here since we will not need
it, but rather just mention of few well-known corollaries of the theorem. The Principle
of Inclusion-Exclusion, the Fundamental Theorem of Difference Calculus and the M¨obius

8

Inversion Theorem in number theory are all consequences of the poset M¨obius Inversion
Theorem.
The M¨obius function behaves nicely with respect to products of posets and isomorphisms.
More specifically, we have the next lemma. We will use these facts often in the next chapter
of the paper.
Lemma 1.2.2. Let P and Q be posets. Then we have the following.
1. If P ∼
= Q, then µP = µQ .
2. The product P × Q has M¨obius function

µP ×Q (p, q) = µP (p)µQ (q).

It is not hard to see that the M¨obius function for the chain, Cn , is given by





1
if x = 0,





µ(x) = −1 if x = 1,








0
otherwise.
Therefore the previous lemma and the fact that Bn ∼
= C1 × C1 × · · · × C1 implies that
n times
µ(S) = (−1)|S| for any S ∈ Bn , giving a second and more conceptual proof of this result.

9

1.3

The Characteristic polynomial

We are primarily interested in the M¨obius function because of its generating function. To
define it, let P be a poset and let ρ : P → N be any function. Given ρ, define

ρ(P ) = max ρ(x).
x∈P

(The choice of ρ to denote this function is done because it replaces the rank function which is
typically used in the definition of the characteristic polynomial.) Additionally, let m be any
integer such that m ≥ ρ(P ). The generalized characteristic polynomial of P with respect to
ρ and m is
µ(x)tm−ρ(x) .

χ(P, t) =

(1.3)

x∈P

In the case when ρ is the rank function of P and m = ρ(P ), then we call the polynomial
the characteristic polynomial to distinguish it from the more general definition. Most of the
literature on characteristic polynomials is about this case, however, many of the results we
prove in this dissertation do not need this assumption.
The main goal of the first half of this dissertation is to identify posets with generalized
characteristic polynomials having only nonnegative integer roots. Additionally, we wish to
explain this factorization in these cases. Before we continue, let us mention some previous
work done by others on the factorization of the characteristic polynomial. For a more
complete overview, we suggest reading the survey paper by Sagan [12]. In [15], Stanley
showed that the characteristic polynomial of a semimodular supersolvable lattice always
has nonnegative integer roots. Additionally, he showed these roots were given by the sizes
of blocks in a partition of the atom set of the lattice. Blass and Sagan [1] extended this

10

result to LL lattices. In [19], Zaslavsky generalized the concept of coloring of graphs to
coloring of signed graphs and showed how these colorings were related to the characteristic
polynomial of certain hyperplane arrangements. This permits one to factor characteristic
polynomials using techniques for chromatic polynomials of signed graphs. Saito [13] and
Terao [17] studied a module of derivations associated with a hyperplane arrangement. When
this module is free, the characteristic polynomial has roots which are the degrees of its basis
elements.
Let us return to our example of Bn . We have already shown that µ(S) = (−1)|S| and
the rank function is given by ρ(S) = |S|. Thus, if χ(Bn , t) is the characteristic polynomial
we have
(−1)|S| tn−|S| .

χ(Bn , t) =
S∈Bn

Since there are nk subsets of {1, 2 . . . , n} with size k, we get
n

χ(Bn , t) =

(−1)k
k=0

n n−k
t
.
k

The binomial theorem now implies that

χ(Bn , t) = (t − 1)n .

If we calculate the characteristic polynomial of the 1-chain, C1 , we get

χ(C1 , t) = t − 1.

The fact that Bn is isomorphic to the n-fold product of C1 suggests that the characteristic

11

polynomial of the product of posets is the product of the individual characteristic polynomials. Indeed, this is true and is the basis for our approach to explaining factorization of the
characteristic polynomial. Consider the following well-known lemma which can be shown
using Lemma 1.1.2 and Lemma 1.2.2.
Lemma 1.3.1. Let P and Q be posets. If χ is the characteristic polynomial then we have
the following.
1. If P ∼
= Q, then χ(P, t) = χ(Q, t).
2. χ(P × Q, t) = χ(P, t)χ(Q, t).
This lemma explains the factorization of the characteristic polynomial of Bn . Let us now
consider a different family of lattices whose characteristic polynomials have only nonnegative integer roots. We will often refer back to this example in the sequel. A set partition
of [n] is family of nonempty disjoint sets B1 , B2 , . . . , Bk whose union is [n]. The subsets
B1 , B2 , . . . , Bk are called the blocks of the partition. We will denote the partition with
blocks B1 , B2 , . . . , Bk by π = B1 /B2 / . . . /Bk . The partition lattice, Πn , is the lattice whose
elements are the set partitions π = B1 /B2 / . . . /Bk of [n] under the refinement ordering. In
other words, we say
B1 /B2 / . . . /Bk ≤ C1 /C2 / . . . /Cm
provided each Ci is a union of some of the Bj ’s. It is well-known that the characteristic
polynomial of Πn is given by

χ(Πn , t) = (t − 1)(t − 2) · · · (t − n + 1).

All the roots of the characteristic polynomial of Bn are 1 which is reflected in the fact
12

a1 a2 · · · an

ˆ0

Figure 1.3: The claw with n atoms
that the characteristic polynomial of C1 is χ(C1 , t) = t − 1. However, as we have seen in
the case of Πn we need to consider other posets whose characteristic polynomial are single
linear factors.
Definition 1.3.2. The claw with n atoms is the poset with a ˆ0, n atoms and no other
elements. It will be denoted CLn and is the poset which has Hasse diagram depicted in
Figure 1.3.
Clearly,
χ(CLn , t) = t − n
where χ is the characteristic polynomial.
Now let us look at the special case of Π3 . We wish to show that

χ(Π3 , t) = (t − 1)(t − 2).

in a way which mimics the second proof for Bn . Since the roots of χ(Π3 , t) are 1 and 2, we
consider CL1 × CL2 which, by the first part of Lemma 1.3.1, has the same characteristic
polynomial. Figure 1.4 contains the Hasse diagrams of Π3 and CL1 × CL2 . Unfortunately,
these two posets are not isomorphic since one contains a maximum element and the other
does not. We now wish to modify CL1 × CL2 without changing its characteristic polynomial
13

(a, b)

123

(ˆ0, b)

12/3 13/2 1/23

(a, c)
(a, ˆ0)

1/2/3

(ˆ0, ˆ0)

Π3

CL1 × CL2

(ˆ0, c)

(a, b) ∼ (a, c) = d
(ˆ0, b)

(a, ˆ0)

(ˆ0, c)

(ˆ0, ˆ0)
CL1 × CL2 after identifying (a, b) and (a, c)
Figure 1.4: Hasse diagrams for the partition lattice example

and in such a way that the resulting poset will be isomorphic to Π3 . It will then follow from
the second part of Lemma 1.3.1 that

χ(Π3 , t) = χ(CL1 × CL2 ) = (t − 1)(t − 2).

Let CL1 have its atom labeled by a and let CL2 have its two atoms labeled by b and c. Now
suppose that we identify (a, b) and (a, c) in CL1 ×CL2 and call this new element d. After this
collapse, we get a poset isomorphic to Π3 as can be seen in Figure 1.4. Note that performing
this collapse did not change the characteristic polynomial since µ(d) = µ((a, b)) + µ((a, c))
and ρ(d) = ρ((a, b)) = ρ((a, c)). Thus we have fulfilled our goal.
It turns out that we can use this technique of collapsing elements to find the roots of a
characteristic polynomial in a wide array of posets, P . The basic idea is that it is trivial
14

to calculate the characteristic polynomial of a product of claws. Moreover, under certain
conditions which we will see later, we are able to identify elements of the product and form
a new poset without changing the characteristic polynomial. If we can show the product
with identifications made is isomorphic to P , then we will have succeeded in showing that
χ(P, t) has only nonnegative integer roots.

15

Chapter 2
Quotient Posets
In this chapter we consider how to use quotient posets to prove factorization theorems for
the characteristic polynomial. In Sections 2.1–2.4we will consider the case when our posets
are ranked and we are dealing with the characteristic polynomial. Unless otherwise noted, in
Sections 2.1–2.4 whenever we use ρ we mean the rank function of the poset. After considering
the ranked case, we will deal with the more general case where our posets need not be ranked.
This material is contained in Sections 2.5–2.8.

2.1

The Basics

We begin this section by defining, in a rigorous way, what we mean by collapsing elements
in a Hasse diagram of a poset. We do so by putting an equivalence relation on the poset and
then ordering the equivalence classes.
Definition 2.1.1. Let P be a poset and let ∼ be an equivalence relation on P . We define
the quotient P/ ∼ to be the set of equivalence classes with the binary relation ≤ defined by
X ≤ Y in P/ ∼ if and only if x ≤ y in P for some x ∈ X and some y ∈ Y .
Note that this binary relation on P/ ∼ is reflexive and transitive, but is not necessarily
antisymmetric. For example, let P be the chain with elements 0 < 1 < 2 and take X = {0, 2}
and Y = {1}. Then in P/ ∼ we have that X ≤ Y and Y ≤ X, but X = Y . Since we want

16

the quotient to be a poset, it is necessary to require two more properties of our equivalence
relation.
Definition 2.1.2. Let P be a poset and let ∼ be an equivalence relation on P . Order the
equivalence classes as in the previous definition. We say the poset P/ ∼ is a homogeneous
quotient if
(1) ˆ0 is in an equivalence class by itself, and
(2) if X ≤ Y in P/ ∼, then for all x ∈ X there is a y ∈ Y such that x ≤ y.
Lemma 2.1.3. If P is a poset and P/ ∼ is a homogeneous quotient, then P/ ∼ is a poset.
Proof. As previously mentioned, the fact that ≤ in P/ ∼ is reflexive and transitive is clear.
To see why it is antisymmetric, suppose that X ≤ Y and Y ≤ X. By definition, there is a
x ∈ X and y ∈ Y with x ≤ y. Since Y ≤ X there is a x ∈ X with x ≤ y ≤ x . Since X ≤ Y
there is a y ∈ Y with x ≤ y ≤ x ≤ y . Continuing, we get a chain

x ≤ y ≤ x ≤ y ≤ ...

If any of the inequalities are equalities then we are done since the equivalence classes partition
P . If all are strict, then we would have an infinite chain in P , but this contradicts the fact
that P is finite. Therefore it must be that X = Y.
Since we would like to use quotient posets to find characteristic polynomials, it would be
quite helpful if the M¨obius value of an equivalence class was the sum of the M¨obius values of
the elements of the equivalence class. This is not always the case when using homogeneous
quotients, however we only need one simple requirement on the equivalence classes so that
17

this does occur. Note the similarity of the hypothesis in the next result to the definition of
the M¨obius function (equation (1.1)).
Lemma 2.1.4 ([6]). Let P/ ∼ be a homogeneous quotient poset. Suppose that for all nonzero
X ∈ P/ ∼,
µ(y) = 0

(2.1)

y∈L(X)

where L(X) is the lower order ideal generated by X in P . Then, for all equivalence classes
X
µ(X) =

µ(x).
x∈X

Proof. We induct on the length of the longest ˆ0–X chain to prove the result. If the length
is zero, then X = ˆ0. Since P/ ∼ is a homogeneous quotient, there is only one element in X
and it is ˆ0. The M¨obius value of the minimum of any poset is 1 and so the base case holds.
Now suppose that the length is positive. Then X = ˆ0 and so by assumption,

µ(y) = 0.
y∈L(X)

Breaking this sum into two parts and moving one to the other side of the equation gives

µ(x) = −
x∈X

µ(y).

(2.2)

y∈L(X)\X

Using the definition of µ and the induction hypothesis, we have that

µ(X) = −

µ(Y ) = −
Y <X

µ(y) .


Y <X

18


y∈Y

Since P/ ∼ is a homogeneous quotient poset, we have that if Y < X then for every y ∈ Y
there is an x ∈ X with y < x. Therefore the previous sum ranges over all y such that there
is an x ∈ X with y < x. Thus y ∈ L(X) \ X. Conversely, for each y ∈ L(X) \ X there is an
x ∈ X with y < x. By the definition of ≤ in P/ ∼, we have that this implies Y < X where
Y is the equivalence class of y. It follows that

µ(X) = −

µ(y).

(2.3)

y∈L(X)\X

Combining this equation with (2.2) completes the proof.
For the remainder of the paper, we shall refer to the condition given by equation (2.1)
as the summation condition. From the previous lemma, we know how the M¨obius values
behave when taking quotients under certain circumstances. We also need to know how the
rank behaves under quotients.
Lemma 2.1.5. Let P be a ranked poset and let P/ ∼ be a homogeneous quotient poset.
Suppose that for all x, y ∈ P , x ∼ y implies ρ(x) = ρ(y). Then P/ ∼ is ranked and
ρ(X) = ρ(x) for all x ∈ P .
Proof. We actually prove a stronger result. We show that X

Y (where

covering relation) implies there is a x ∈ X and a y ∈ Y such that x
this implies the lemma, suppose that there were two chains ˆ0 = X1

X2

denotes a

y. To see why
...

Xn and

ˆ0 = Y1 Y2 . . . Ym with Xn = Ym . Then for the corresponding chains ˆ0 = x1 x2 . . . xn
and ˆ0 = y1 y2 . . . ym we have that ρ(xn ) = ρ(ym ) since elements in the same equivalence
class have the same rank. This forces n = m and so P/ ∼ must be ranked. Additionally, it
is easy to see that this implies that ρ(X) = ρ(x) for all x ∈ X.
19

By the definition of a homogeneous quotient, if X

Y then there is a x ∈ X and y ∈ Y

with x < y. Suppose that there was some z ∈ P with x < z < y. Then ρ(x) < ρ(z) < ρ(y)
and X ≤ Z ≤ Y where Z is the equivalence class of z. Since all elements in an equivalence
class have the same rank this implies that X < Z < Y in P/ ∼, which contradicts the fact
that Y covered X.
Applying Lemma 2.1.4, Lemma 2.1.5 and the definition of the characteristic polynomial
we immediately get the following corollary.
Corollary 2.1.6 ([6]). Let P be a ranked poset and let P/ ∼ be a homogeneous quotient.
If the summation condition (2.1) holds for all nonzero X ∈ P/ ∼, and x ∼ y implies
ρ(x) = ρ(y) and χ is the characteristic polynomial, then

χ(P/ ∼, t) = χ(P, t).

We now have conditions under which the characteristic polynomial does not change when
taking a quotient. However, the previous results do not tell us how to choose an appropriate
equivalence relation for a given poset. It turns out that when the poset is a lattice, there is
a canonical choice for ∼, as we will see in the next section.

2.2

The Standard Equivalence Relation

Let us look at the partition lattice example again and give new labelings to CL1 × CL2
which will be helpful in determining an equivalence relation. First, we set up some notation
for the atoms of the partition lattice. For i < j, let (i, j) denote the atom which has i and
j in one block and all other elements in singleton blocks. Let CL1 have its atom labeled by
20

((1, 2), (1, 3))
(ˆ0, (1, 3))

((1, 2), (2, 3))
((1, 2), ˆ0)

(ˆ0, (2, 3))

123
13/2

123
12/3

(ˆ0, ˆ0)

1/2/3

CL1 × CL2

CL1 × CL2

1/23

Figure 2.1: Hasse diagrams for partition lattice example with new labelings
(1, 2) and CL2 have its atoms labeled by (1, 3) and (2, 3). In both of the claws, label the
minimum element by ˆ0. The poset on the left in Figure 2.1 shows the induced labeling on
CL1 × CL2 .
Now relabel CL1 × CL2 by taking the join in Π3 of the two elements in each pair. The
poset on the right in Figure 2.1 shows this step. Finally, identify elements which have the
same label. In this case, this means identifying the top two elements as we did before. Upon
doing this, we get a poset which is isomorphic to Π3 and has the same labeling as Π3 .
In order to generalize the previous example, we will be putting an equivalence relation
on the product of claws whose atom sets come from partitioning the atoms of the original
lattice. We need some terminology before we can define our equivalence relation.
An ordered partition of a set S is a set partition where we put an order on the blocks
of the partition. If B1 , B2 , . . . , Bn are the blocks of the partition where we order them so
B1 < B2 < · · · < Bn , then we write the ordered partition as (B1 , B2 , . . . , Bn ).
Suppose that L is a lattice and (A1 , A2 , . . . , An ) is an ordered partition of the atoms of
L. We will use CLAi to denote the claw whose atom set is Ai and whose minimum element
is labeled by ˆ0L (or just ˆ0 if L is clear from context). The elements of

n
i=1 CLAi

will be

called atomic transversals and written in boldface. (The reason for the adjective “atomic”
21

is because we will be considering more general transversals in Section 2.3.) Since the rank
of an element in the product of claws is just the number of nonzero elements in the tuple,
it will be useful to have a name for the elements of a transversal which are nonzero. For
t∈

n
i=1 CLAi

define the support of t as the set of nonzero elements in the tuple t. We

will denote it by supp t.
We will use the notation t(ei ) to denote the ordered tuple obtained by replacing the ith
coordinate of t = (t1 , t2 , . . . , tn ) with an element e. That is,

t(ei ) = (t1 , t2 , . . . , ti−1 , e, ti+1 , . . . , tn ).

We will also need a notation for the join of the elements of t which will be

t = t1 ∨ t2 ∨ · · · ∨ tn .

With this new terminology we are now in a position to define a natural equivalence
relation on the product of the claws. Since we are trying to show that the characteristic
polynomial of a lattice has certain roots, we will need to show that the quotient of the product
of claws is isomorphic to the lattice. Therefore it is reasonable to define the equivalence
relation by identifying two elements of the product of claws if their joins are the same in L.
Definition 2.2.1. Let L be a lattice and let (A1 , A2 , . . . , An ) be an ordered partition of the
atoms of L. The standard equivalence relation on

n
i=1 CLAi

is defined by

n

s ∼ t in

CLAi ⇐⇒

s=

t in L.

i=1

Note that in the previous definition, we did not assume that L is ranked. We will use the
22

standard equivalence relation later when we will not make assumptions about if the lattice
ranked or not.
We will use the notation
n

Txa

=

t∈

CLAi :

t=x

i=1

and call the elements of this set atomic transversals of x. Therefore, the equivalence classes
of the quotient

n
i=1 CLAi

/ ∼ are of the form Txa for some x ∈ L. It is obvious that

the standard equivalence relation is an equivalence relation. To be able to use any of the
theorems from the previous section, we need to make sure that taking the quotient with
respect to the standard equivalence relation gives us a homogeneous quotient. Moreover, we
will need a way to determine if the summation condition (2.1) holds for all nonzero elements
of the quotient. We do this in the next lemma. For the rest the paper we will use the
notation Ax for the set of atoms below x.
Lemma 2.2.2. Let L be a ranked lattice and let (A1 , A2 , . . . , An ) be an ordered partition of
the atoms of L. Let ∼ be the standard equivalence relation on

n
i=1 CLAi .

Suppose that the

following hold.
(1) For all x ∈ L, Txa = ∅.
(2) If t ∈ Txa , then | supp t| = ρ(x).
Under these conditions,
(a) The lower order ideal generated by the set Txa in

n
i=1 CLAi

L(Txa ) = {t : ti ≤ x for all i}.
23

is given by

(b) The quotient

n
i=1 CLAi

/ ∼ is homogeneous.
n
i=1 CLAi

(c) For all nonzero Txa ∈

/ ∼ the summation condition (2.1) holds if and

only if for each nonzero x ∈ L there is an i such that |Ai ∩ Ax | = 1.
Proof. First, we show (a). We claim that assumptions (1) and (2) imply that if a ∈ Ax then
there is an atomic transversal for x which contains a. To verify the claim, use assumption (1)
to pick t ∈ Txa and let r = t(ai ). By construction and assumption (2), ρ(
| supp t| = ρ(x). But also

r ≤ x which forces

r) = | supp r| ≥

r = x. Thus a is in the atomic transversal

r for x.
The definition of Txa gives us the inclusion L(Txa ) ⊆ {t : ti ≤ x for all i}. The reverse
inclusion holds by the previous claim.
Next, we verify (b). It is clear that t ∈ Tˆa if and only if t = (ˆ0, ˆ0, . . . , ˆ0) and so part (1)
0

of Definition 2.1.2 is satisfied. To show part (2), suppose that Txa ≤ Tya as in Definition 2.1.1.
Then there is some t ∈ Txa and s ∈ Tya with t ≤ s. It follows that

t≤

s and so x ≤ y.

Let t ∈ Txa . Using the fact that ti ≤ x ≤ y and part (a), we have that t ∈ L(Tya ). It follows
that there is some s ∈ Tya with t ≤ s and so part (2) of Definition 2.1.2 holds.
Finally, we demonstrate (c). Fix x ∈ L and let Ni be the number of atoms below x in Ai .
Let I be the set of indices i such that Ni > 0. By relabeling, if necessary, we may assume that
I = {1, 2, . . . , k}. It follows from part (a) that the number of atomic transversals in L(Txa )
with support size i is ei (N1 , N2 , . . . , Nk ) where ei is the ith elementary symmetric function.
For each atomic transversal t ∈ L(Txa ) we have that µ(t) = (−1)| supp t| . Therefore,
k

µ(t) =
t∈L(Txa )

k

(−1)i e

i (N1 , N2 , . . . , Nk )

i=0

=

(1 − Ni ).
i=1

24

Thus the summation condition (2.1) holds for each nonzero element in the quotient if and
only if for each nonzero x ∈ L there is an index i such that |Ai ∩ Ax | = 1.
Combining the previous result with Corollary 2.1.6 gives conditions under which the
product of claws and its quotient have the same characteristic polynomial. We also need to
show that there is an isomorphism between L and this quotient. This will give us the desired
factorization.
Theorem 2.2.3 ([6]). Let L be a ranked lattice and let (A1 , A2 , . . . , An ) be an ordered
partition of the atoms of L. Let ∼ be the standard equivalence relation on

n
i=1 CLAi

and

let χ(L, t) be the characteristic polynomial. Suppose the following hold.
(1) For all x ∈ L, Txa = ∅.
(2) If t ∈ Txa , then | supp t| = ρ(x).
(3) For each nonzero x ∈ L there is some i with |Ai ∩ Ax | = 1.
Then we can conclude the following.
(a) For all x ∈ L, µ(x) = (−1)ρ(x) |Txa |.
n

(t − |Ai |).

(b) χ(L, t) =

i=1

Proof. Let P =

n
i=1 CLAi .

First, we show that L ∼
= P/ ∼. Define a map ϕ : (P/ ∼) → L

by ϕ(Txa ) = x. It is easy to see that ϕ is well-defined. Define ψ : L → (P/ ∼) by ψ(x) = Txa .
By assumption Txa = ∅ and so ψ is well-defined. Moreover, it is clear that ϕ and ψ are
inverses of each other.
To show that ϕ is order preserving, suppose that Txa ≤ Tya . Then just as in the proof of
Lemma 2.2.2 part (b), we have that x ≤ y and so ϕ is order preserving.
25

To show that ψ is order preserving, suppose that x ≤ y. Then applying the same
technique in the proof of Lemma 2.2.2 part (b) we get that there is a t ∈ Txa and s ∈ Tya
with t ≤ s. By the definition of ≤ in P/ ∼ we get that Txa ≤ Tya and so ψ is order preserving.
To obtain (a), note that the M¨obius value of an element in the product of claws is
µ(t) = (−1)| supp t| . Therefore, using Lemma 2.1.4, we get

µ(Txa ) =

(−1)| supp t| .

µ(t) =
t∈Txa

t∈Txa

Using the isomorphism between L and the quotient as well as the fact that, by assumption
(2), all the atomic transversals for x have size ρ(x), we have

µ(x) = µ(Txa ) = (−1)ρ(x) |Txa |

as desired.
Finally, to verify (b) apply Corollary 2.1.6 and Lemma 2.2.2 to get that
n

(t − |Ai |) = χ(P, t) = χ(P/ ∼, t).
i=1

Now part (b) follows immediately since L ∼
= P/ ∼.
Let us return to the partition lattice and see how we can apply Theorem 2.2.3 Label the
atoms (i, j) as before. Partition the atoms as (A1 , A2 , . . . , An−1 ) where

Aj = {(i, j + 1) | i < j + 1}

With each atomic transversal t we will associate a graph, Gt on n vertices such that there
26

is an edge between vertex i and vertex j if and only if (i, j) is in t. We will use the graph to
verify the assumptions of Theorem 2.2.3 are satisfied for Πn .
First, let us show assumption (1) holds. In the case when there is a single block B = {b1 <
b2 < · · · < bm }, the elements (b1 , b2 ), (b2 , b3 ), . . . , (bm−1 , bm ) form an atomic transversal and
their join is B. Now to get the elements which have more than one nontrivial block, follow
the same procedure for each block and take the union of the atomic transversals. It follows
every element has an atomic transversal.
Next, we prove that assumption (2) holds. We claim that if t ∈ Tπa then Gt is a forest.
To see why, suppose that there was a cycle and let c be the largest vertex in the cycle. Then
c must be adjacent to two smaller vertices a and b which implies that both (a, c) and (b, c)
must be in t. This is impossible since both come from Ac−1 .
Since Gt is forest, if Gt has k components then the number of edges in Gt is n − k. It
is not hard to see that i and j are in the same block in

t if and only if i and j are in the

same component of Gt . Moreover, it is well known that if π ∈ Πn and π has k blocks then
ρ(π) = n − k. It follows that if t ∈ Tπa and π has k blocks then | supp t| = |E(Gt )| = n − k =
ρ(π). We conclude that assumption (2) holds.
Finally, to verify assumption (3), let π ∈ Πn with π = ˆ0. Then π contains a nontrivial
block. Let i be the second smallest number in this block. We claim that there is only one
atom in Ai−1 below π. First note that there is some atom below π in Ai−1 namely (a, i)
where a is the smallest element of the block. Suppose there was more than one atom below
π in Ai−1 and let (a, i), (b, i) ∈ Ai−1 with (a, i), (b, i) ≤ π. Then (a, i) ∨ (b, i) ≤ π and so a,
b and i are all in the same block in π which is impossible since a, b < i but i was chosen to
be the second smallest in its block.

27

Now applying the theorem we get that

χ(Πn , t) = (t − 1)(t − 2) · · · (t − n + 1)

since |Ai | = i for 1 ≤ i ≤ n − 1.
More generally, Theorem 2.2.3 can be used to prove Terao’s result [16] about the characteristic polynomial of a hyperplane arrangement with a nice partition. In fact the notion of
nice partition is the combination of assumptions (2) and (3) of Theorem 2.2.3 in the special
case of a central hyperplane arrangement.

2.3

Rooted Trees

One of the drawbacks of Theorem 2.2.3 is that assumption (1) requires that every element of
the lattice has an atomic transversal. This forces L to be atomic. However, by generalizing
the notion of a claw to that of a rooted tree, we will be able to remove this assumption and
derive Theorem 2.3.2 below which applies to a wider class of lattices.
Definition 2.3.1. Let P be a poset and S be a subset of P containing ˆ0. Let C be the
collection of saturated chains of P which start at ˆ0 and use only elements of S. The rooted
tree with respect to S is the poset obtained by ordering C by inclusion and will be denoted
by RTS .
It is easy to see that given any subset S of a poset containing ˆ0, the Hasse diagram of
RTS always contains a ˆ0 and has no cycles. This explains the choice of rooted tree for the
name of the poset.
Strictly speaking the elements of RTS are chains of L. However, it will be useful to think
28

123

123

123

12/3

13/2

1/23

1/2/3

1/2/3

RTS1

RTS2

Figure 2.2: Hasse diagrams for rooted trees
of the elements of RTS as elements of L where we associate a chain C with its top element.
One can still recover the full chain by considering the unique path from ˆ0 to C in RTS .
Let us consider an example in Π3 . As before, partition the atom set as A1 = {12/3} and
A2 = {13/2, 1/23}. Let S1 , S2 be the upper order ideals generated by A1 , A2 , respectively,
together with ˆ0. Then we we get RTS1 and RTS2 as in Figure 2.2. Note that we label the
chains ˆ0 < 12/3 < 123, ˆ0 < 13/2 < 123 and ˆ0 < 1/23 < 123 in S1 and S2 all by 123 in RTS1
and RTS2 since each of these chains terminates at 123.
In the previous sections, we used a partition of the atom set to form claws. In this section,
we will use the partition of the atom set to form rooted trees. Given an ordered partition of
the atoms of a lattice (A1 , A2 , . . . , An ), for each i we form the rooted tree RTUˆ (A ) where
i
Uˆ (Ai ) is the upper order ideal generated by Ai together with ˆ0. We will call rooted trees of
the form RTUˆ (A ) complete rooted trees. We will study them in more detail in Section 2.6.
i
Note that since (A1 , A2 , . . . , An ) is a partition of the atoms, every element of the lattice
appears in an RTUˆ (A ) for some i.
i
Given (A1 , A2 , . . . , An ), we call t ∈

n
ˆ (A )
i=1 RTU
i

a transversal. We will use the notation,

n

Tx =

t∈

RTUˆ (A ) :
i

i=1

29

t=x

and call such elements transversals of x. If t consists of only atoms of L or ˆ0 then t is called
an atomic transversal. This agrees with the terminology we used for claws. The set of atomic
transversals for x will be denoted Txa as before.
There is very little change in the approach using rooted trees as opposed to claws. As
before, given a partition (A1 , A2 , . . . , An ) of the atom set of L, we will put the standard
equivalence relation on

n
ˆ (A ) .
i=1 RTU
i

Note that one can take the join using all the elements

of a chain or just the top element as the results will be equal. Since we are using rooted trees,
n
ˆ (A )
i=1 RTU
i

the natural map from

/ ∼ to L is automatically surjective. In other words,

we can remove the condition that every element of L has an atomic transversal. Additionally,
since each Hasse diagram is a tree, when we take the product of the trees, the M¨obius value
of any transversal which is not atomic is zero and so does not affect χ. Therefore, we get
the following improvement on Theorem 2.2.3.
Theorem 2.3.2 ([6]). Let L be a ranked lattice and let (A1 , A2 , . . . , An ) be an ordered
partition of the atoms of L. Let ∼ be the standard equivalence relation on

n
ˆ (A )
i=1 RTU
i

and let χ be the characteristic polynomial. Suppose the following hold.
(1) If t ∈ Txa , then | supp t| = ρ(x).
(2) For each nonzero x ∈ L there is some i with |Ai ∩ Ax | = 1.
Then we can conclude the following.
(a) For all x ∈ L, µ(x) = (−1)ρ(x) |Txa |.
n

(b) χ(L, t) =

tρ(L)−n

(t − |Ai |).
i=1

Proof. Let P =

n
ˆ (A ) .
i=1 RTU
i

We need to show that P/ ∼ is homogeneous. The first

condition of the definition is obvious. For the second, suppose that Tx ≤ Ty and t ∈ Tx . It
30

follows that x ≤ y. Let i be an index such that Ai ∩ Ay = ∅ so that y ∈ Uˆ (Ai ). If t ∈ Tx ,
then tj ≤ x ≤ y for all j. Therefore, t(y i ) ∈ Ty and t ≤ t(y i ). It follows that P/ ∼ is
homogeneous.
In the proof of Theorem 2.2.3, we showed that the lattice and the quotient of the product
of claws were isomorphic. The proof that L and P/ ∼ are isomorphic is essentially the same.
If we define ϕ and ψ analogously, then the only difference is showing ψ is order preserving
in which case one can use the same ideas as in the previous paragraph to complete the
demonstration.
Now we verify that the summation condition (2.1) holds for all nonzero elements of P/ ∼.
We only need to modify the proof that we gave in Lemma 2.2.2 part (c) slightly. Analogously
to the proof of part (a) of that lemma, one sees that L(Tx ) = {t : ti ≤ x for all i}. Using
this and the fact that only atomic transversals have nonzero M¨obius values, the proof of
Lemma 2.2.2 part (c) goes through as before with Txa replaced by Tx .
Now applying Lemma 2.1.4 and the fact that µ(t) = 0 if t is not atomic, we get

µ(Tx ) =

µ(t) =

µ(t).

(2.4)

t∈Txa

t∈Tx

Then applying the same proof as in Theorem 2.2.3 gives us (a).
To finish the proof we define a modification of the characteristic polynomial for any
ranked poset P ,
µ(x)t−ρ(x) .

χ(P,
¯ t) =
x∈P

We claim that χ(P,
¯ t) = χ(P/
¯
∼, t). Applying assumption (1) and the isomorphism L ∼
=

31

P/ ∼, we get that for every t ∈ Txa we have

ρ(t) = | supp t| = ρ(x) = ρ(Tx ).

This combined with equation (2.4), proves the claim.
Now if RT is a rooted tree with k atoms then χ(RT
¯
) = t−1 (t − k). It follows that
n

χ(P,
¯ t) =

t−n

(t − |Ai |).
i=1

Since χ¯ is preserved by isomorphism,
n

χ(L,
¯ t) = χ(P/
¯
∼, t) = χ(P,
¯ t) =

t−n

(t − |Ai |).
i=1

Multiplying by tρ(L) gives us part (b).

2.4

Partitions Induced by a Multichain

It turns out that under certain circumstances we can show that assumption (2) of Theorem 2.3.2 and factorization of the characteristic polynomial are equivalent. To be able to
prove this equivalence, we will not be able to take an arbitrary partition of the atoms, but
rather we will need the partition to be induced by a multichain in the lattice.
If L is a lattice and C : ˆ0 = x0 ≤ x1 ≤ · · · ≤ xn = ˆ1 is a ˆ0–ˆ1 multichain of L we get an
ordered partition (A1 , A2 , . . . , An ) of the set A(L) of atoms of L by defining the set Ai as

Ai = {a ∈ A(L) | a ≤ xi and a

32

xi−1 }.

In this case we say (A1 , A2 , . . . , An ) is induced by the multichain C. Note that we do
not insist that our multichain be a chain nor does it need to be saturated as is usually done
in the literature. This also implies that some of the Ai ’s can be empty. Partitions induced
by multichains have several nice properties. The first property will apply to any lattice
(Lemma 2.4.2), but for the second we will need the lattice to be semimodular (Lemma 2.4.5).
Before we get to these properties, we need a modification of Lemma 2.1.4.
Lemma 2.4.1. Suppose that P/ ∼ is a homogeneous quotient and that for all non-maximal,
nonzero X ∈ P/ ∼ we have that
µ(y) = 0
y∈L(X)

Then for all X ∈ P/ ∼

µ(X) =






µ(x)




x∈X















if X is not maximal,

µ(x) −
x∈X

µ(y)

if X is maximal.

y∈L(X)

Proof. If X is not maximal, then the proof of Lemma 2.1.4 goes through as before.
Now suppose that X is maximal. If X = ˆ0 then the result holds because the quotient is
homogeneous. So suppose X = ˆ0. In the proof of Lemma 2.1.4, we derived equation (2.3)
without using the summation condition (2.1) and so it still holds. Moreover, it is easy to see
that this equation is equivalent to the one for maximal X in the statement of the current
result.
Given a lattice and a partition of the atoms, it will be useful to know when elements

33

of a lattice do not satisfy condition (2) of Theorem 2.3.2. This is possible to do when the
partition of the atoms is induced by a multichain.
Lemma 2.4.2. Let L be a lattice and let (A1 , A2 , . . . , An ) be induced by a multichain C :
ˆ0 = x0 ≤ x1 ≤ · · · ≤ xn = ˆ1. Let Ni be the number of atoms below an element x ∈ L in Ai .
If Ni = 1 for all i and x = ˆ0 is minimal with respect to this property, then for all but one i,
Ni = 0.
Proof. Suppose that x is minimal, but that Ni > 1 for at least two i. Let k be the smallest
index with Nk = 0, and B ⊆ Ak be the atoms below x in Ak so |B| ≥ 2. Let y =

B. So,

by the choice of B, y ≤ xk which implies that the atoms below y are in Ai for i ≤ k. So the
choice of Ak forces the set of atoms below y to be B which is a proper subset of the set of
atoms below x, and thus y < x. Since |B| ≥ 2, this contradicts the choice of x.
The next definition gives one of the conditions equivalent to factorization when the atom
partition is induced by a multichain.
Definition 2.4.3. Let L be a lattice and let C : ˆ0 = x0 ≤ x1 ≤ · · · ≤ xn = ˆ1 be a ˆ0–ˆ1
multichain. For atomic x ∈ L, x neither ˆ0 nor an atom, let i be the index such that x ≤ xi
but x ≤ xi−1 . We say that C satisfies the meet condition if, for each such x, we have
x ∧ xi−1 = ˆ0.
We are now in a position to give a list of equivalent conditions to factorization.
Theorem 2.4.4. Let L be a ranked lattice and let (A1 , A2 , . . . , An ) be induced by a ˆ0–ˆ1
multichain, C. Suppose that if t ∈ Txa , then

| supp t| = ρ(x).
34

Under these conditions the following are equivalent.
1. For every nonzero x ∈ L, there is an index i such that |Ai ∩ Ax | = 1.
2. For every element which is the join of two elements from the same Aj , there is an
index i such that |Ai ∩ Ax | = 1.
3. The multichain C satisfies the meet condition.
4. We have that
n

χ(L, t) =

tρ(L)−n

(t − |Ai |)
i=1

where χ is the characteristic polynomial.
We note that it is possible to have n > ρ(L) in part 4 of the previous theorem. In this
case the exponent on the outside of the factorization will be negative. This is possible since
we are using multichains and so repeating elements in the chain will give rise to as many
empty blocks in the partition of the atom set as we wish. However, for each such block, we
get a corresponding factor (t − 0). Thus χ(L, t) is still a polynomial since the negative power
of t on the outside of the product will be canceled by the positive powers of t on the inside
of the product.
Proof. (1) ⇒ (4) This is Theorem 2.3.2.
(4) ⇒ (2) We actually show that (4) ⇒ (1) (the fact that (1) ⇒ (2) is trivial). We do so
by proving the contrapositive. By assumption, there must be a nonzero x ∈ L such that for
each i the number of atoms below x in Ai is different from one. Let k be the smallest value
of ρ(x) for which elements of L have this property. We show that the coefficients of tρ(L)−k
in χ(L, t) and in χ(P, t) = tρ(L)−n

n
i=1 (t − |Ai |)

35

are different, where P =

n
ˆ (A ) .
i=1 RTU
i

Using the same proof as we did in Theorem 2.3.2, we can show that L ∼
= P/ ∼. So it suffices
to show that the coefficient of tρ(L)−k in χ(P/ ∼, t) is different from the coefficient in χ(P, t).
Let Q be the poset obtained by removing all the elements of P/ ∼ which have rank
more than k. Let x1 , x2 , . . . , xl be the elements of L at rank k such that the number of
atoms below xi in each block of the partition is different from one. Then by Lemma 2.4.2,
each xi has atoms above exactly one block. Now let S = {Tx1 , Tx2 , . . . , Txl } be the set
of the corresponding transversals. In Q, the elements of S are maximal and all the other
non-maximal elements in Q satisfy the hypothesis of Lemma 2.4.1 which can be verified as
in the proof of Theorem 2.3.2. Therefore we can calculate the M¨obius values of the elements
of rank k in Q using Lemma 2.4.1. Once we know these values we can find the coefficient of
tρ(L)−k in χ(P/ ∼, t).
Each xi is above at least two atoms and is above only atoms in one block. Therefore
the only atomic transversals which are in L(Txi ) are transversals with single atoms and the
transversal with only zeros. Since only atomic transversals have nonzero M¨obius values we
get that for all elements of S,

def

µ(t) = 1 − |Axi | < 0.

ci =

t∈L(Txi )

We know that ci < 0 since the number of atoms below each xi is at least two. Let Qk be
the set of elements of Q at rank k. Using Lemma 2.4.1, we see that the sum of the M¨obius

36

values of Qk is
l

µ(Tx ) =
Tx ∈Qk

µ(Txi ) +
i=1
l

=
i=1

µ(Tx )
Tx ∈Qk \S








µ(t) − ci  +



t∈Txi


Tx ∈Qk \S


µ(t) .

t∈Tx

As recently noted, only elements of L which have atomic transversals have nonzero M¨obius
values. Using this and the assumption that | supp t| = ρ(x) = ρ(Tx ), we get that the
coefficient of of tρ(L)−k in χ(P/ ∼, t) is
l

µ(t) −

ci
i=1

| supp t|=k

where the first sum is over atomic t. As we saw before, each ci is negative and all are nonzero
and so the coefficient of tρ(L)−k is different from

µ(t)
| supp t|=k

which is the coefficient of tρ(L)−k in χ(P, t). This completes the proof that (4) ⇒ (2).
(2) ⇒ (3) We show the contrapositive holds. Suppose that C does not satisfy the meet
condition. Then there is some atomic x which is neither an atom nor ˆ0 such that x ≤ xi ,
x ≤ xi−1 , and x ∧ xi−1 = ˆ0. It follows that x is only above atoms in Ai . Since x is atomic,
but not an atom, there are at least two atoms, a, b below x in Ai . Let y = a ∨ b. Since
y ≤ x, y can only be above atoms in Ai . Therefore, for all indices j, |Aj ∩ Ay | = 1 and y is
the join of two atoms.

37

ˆ1
c

d

a

b
ˆ0

Figure 2.3: A lattice

(3) ⇒ (1) First let us note that if x is an atom then the result is obvious. For x ∈ L let
i be the index such that x ≤ xi and x ≤ xi−1 . We now induct on i. If i = 1 then it suffices
to show that |A1 | = 1 since then every nonzero x ≤ x1 is only above the unique element of
A1 . However if a, b are distinct atoms in A1 then x = a ∨ b is atomic but not an atom or
zero. Further x ≤ x1 but x ∧ xi−1 = x ∧ ˆ0 = ˆ0 which contradicts the meet condition. This
finishes the i = 1 case.
Now suppose that i > 1 and x is not an atom. Let z =

Ax . Then z is atomic and

Az = Ax . Let y = z ∧ xi−1 . Since C satisfies the meet condition, y = ˆ0. By construction
y < xi−1 and so by induction, there is some index j ≤ i − 1 with Aj ∩ Ay = {a}. Suppose
that there was some other atom b ∈ Aj ∩ Az . Then y ∨ b is less than or equal to both z and
xi−1 and so y ∨ b ≤ z ∧ xi−1 = y. However, this is impossible since then Aj ∩ Ay ⊇ {a, b}.
It follows that 1 = |Aj ∩ Az | = |Aj ∩ Ax | and so (1) holds.
It would be nice if all atomic transversals had the correct support size when using a
partition induced by a multichain since then we could remove this assumption from the
previous theorem. Unfortunately this does not always occur. To see why, consider the
lattice in Figure 2.3. The left-most saturated ˆ0–ˆ1 chain induces the ordered partition

({a}, {b}).
38

It is easy to see that the support size of the transversal with both elements is not the rank
of their join. Note, however, that if we had the relation a < d, then the support size would
be the rank of the join. Moreover, note that this would also make the lattice semimodular.
We see in the next lemma that semimodularity always implies transversals induced by a
multichain have the correct support size.
Lemma 2.4.5. Let L be a semimodular lattice and let (A1 , A2 , . . . , An ) be induced by the
multichain C : ˆ0 = x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn = ˆ1. If ∼ is the standard equivalence, then for
all x ∈ L we have that t ∈ Txa implies

| supp t| = ρ(x).

Proof. Given an atomic t ∈ Txa we induct on | supp t|. If | supp t| = 0 the result is obvious.
Now suppose that | supp t| = k > 0. Let i be the largest index in supp t. Let s = t(ˆ0i ),
then | supp s| = k − 1. Suppose that s ∈ Tya , then ρ(y) = k − 1 by induction. Let j be the
largest index such that j ∈ supp s. Then y =
i > j. Thus x =

s ≤ xj by definition of j and ti ≤ xj since

t = ( s) ∨ ti > y. Therefore ρ(x) > ρ(y) = k − 1 and so ρ(x) ≥ k. Since

| supp t| = k, ρ(x) ≤ k as L is semimodular. We conclude that ρ(x) = k = | supp t| and so
our result holds by induction.
Let us now consider supersolvable semimodular lattices. Recall that every supersolvable
semimodular lattice contains a saturated ˆ0–ˆ1 left-modular chain. It turns out that saturated
ˆ0–ˆ1 left-modular chains satisfy the meet condition as we see in the next lemma.
Lemma 2.4.6. Let L be a lattice. If C : ˆ0 = x0 ≤ x1 ≤ x2 < · · · ≤ xn = ˆ1 is a left-modular
saturated ˆ0–ˆ1 multichain then C satisfies the meet condition.

39

Proof. We claim that it is without loss of generality to assume that C is a chain as opposed
to a multichain. To see why, suppose D is a multichain and that xj = xj+1 in D. Moreover,
suppose that there was some x which was atomic and not an atom with x ≤ xj+2 , but
x ≤ xj+1 . Then x ∧ xj = x ∧ xj+1 and so x ∧ xj = ˆ0 if and only if x ∧ xj+1 = ˆ0. It follows
that we can remove the repeated element without changing whether or not D satisfies the
meet condition.
Let x ∈ L be atomic and neither an atom nor ˆ0. Let i be such that x ≤ xi and x ≤ xi−1 .
Then we claim that there is some atom a with a < x and a ≤ xi−1 . To verify the claim,
suppose that no such a existed. Since x is not an atom, it must be that all the atoms below
x are also below xi−1 . However, x being atomic implies that x =

Ax and so x ≤ xi−1

which is impossible.
By the claim, xi−1 < a ∨ xi−1 ≤ xi . Since xi−1

xi we have that a ∨ xi−1 = xi . Now

(xi−1 , x) is a modular pair and a < x so, by the definition of a modular pair,

a ∨ (xi−1 ∧ x) = (a ∨ xi−1 ) ∧ x = xi ∧ x = x.

But a < x so xi−1 ∧ x = ˆ0 and thus C satisfies the meet condition.
We now get Stanley’s Supersolvability Theorem as a corollary of Theorem 2.4.4, Lemma 2.4.5,
and Lemma 2.4.6.
Theorem 2.4.7 (Stanley’s Supersolvability Theorem [15]). Let L be a semimodular lattice
with partition of the atoms (A1 , A2 , . . . , An ) induced by a saturated ˆ0–ˆ1 left-modular multichain. Then
n

χ(L, t) =

tρ(L)−n

(t − |Ai |).
i=1

40

(x1 (x2 (x3 x4 )))

(x1 ((x2 x3 )(x4 ))
((x1 x2 )(x3 x4 ))
((x1 (x2 x3 ))(x4 )

(((x1 x2 )x3 )x4 )
Figure 2.4: The Tamari lattice T3

2.5

Transversal Functions

In the previous sections we had to make the assumption that our poset was a lattice and
that it was ranked. In this section we develop the tools to deal with the general case when
P is not necessarily a lattice nor ranked.
To start, let us do an example and calculate the generalized characteristic polynomial of
an unranked poset. We will consider the Tamari lattices [3, 8], which will be denoted by
Tn . One way to define Tn is as the set of parenthesizations of the word x1 x2 · · · xn+1 with
ordering given by saying π is covered by σ if there exists subwords A, B, and C such that

π = . . . ((AB)C) . . .

and σ = . . . (A(BC)) . . .

Figure 2.4 displays the Hasse diagrams for T3 .
As one can see from the Hasse diagram, T3 is not ranked. In order to calculate the
generalized characteristic polynomial for T3 we need a function, ρ. We will use generalized
rank which was introduced in [1]. To define generalized rank, let us set up some notation. As
done previously, let Ax be the set of atoms below x in P . If (A1 , A2 , . . . , An ) is an ordered

41

partition of the atoms of P , the generalized rank of an element x is given by

ρ(x) = |{i : Ai ∩ Ax = ∅}|.

(2.5)

In other words, ρ(x) counts the number of blocks in the partition that x is above.
Returning to the T3 example, let us partition the atoms into

A1 = {((x1 x2 )(x3 x4 ))}, A2 = {((x1 (x2 x3 ))(x4 )}).

Given this partition, we see that the generalized rank of the bottom element is 0, the three
middle elements all have generalized rank 1 and the top element has generalized rank 2. We
take m = 3 which is the the length of the longest chain in T3 . Using the definition of the
generalized characteristic polynomial (equation (1.3)), we get

χ(T3 , t) = t3 − 2t2 + t = t(t − 1)2 .

We see that χ(T3 , t) factors with roots 0 and 1. One might ask if we can decompose T3
into the product of two smaller posets. Using this reasoning, we might guess that T3 is the
product of two chains since chains have characteristic polynomials with roots 0 and 1. Of
course, this cannot be the case since chains are ranked and so their products are too, but T3
is not ranked. However, it is possible to take the product of the chains, collapse elements
in the Hasse diagram without changing the characteristic polynomial and also get a poset
isomorphic to T3 . However, unlike the method we explained when our posets were ranked,
we will need to collapse elements of different ranks. In order to accomplish, we introduce
the notion of a transversal function.
42

As we did in Section 2.3 we will be using rooted trees. When the poset we are interested
in is a lattice, the standard equivalence relation (Definition 2.2.1) is the canonical choice for
taking quotients. Since we are interested in posets which are not necessarily lattices we need
to generalize this idea. To do this, we quotient out by the kernel of a special type of map
from the product of rooted trees to the poset.
Definition 2.5.1. Let P be a poset and let (S1 , S2 , . . . , Sn ) be an ordered collection of subsets
of P each containing ˆ0. We say f :

n
i=1 RTSi

→ P is a transversal function if it has the

following properties:
1. The function f is order preserving.
2. The function f is surjective.
3. If f (t) = ˆ0, then ti = ˆ0 for all i.
If f is a transversal function, the kernel of f , denoted ker f , is the equivalence relation
∼ given by s ∼ t if and only if f (s) = f (t). Since we will often be referring to equivalence
classes and the elements of these classes we need names for these objects. Some of the
names we use were defined in earlier sections, but we use the same names since they are
generalizations.
Definition 2.5.2. Let P be a poset and let (S1 , S2 , . . . , Sn ) be an ordered collection of subsets
of P . Let f :

n
i=1 RTSi

→ P be a transversal function. If t ∈

n
i=1 RTSi

then we say t

is a transversal for x if f (t) = x. We say t is atomic or an atomic transversal if all the
elements of t are atoms of RTSi or ˆ0. The set of all transversals for x will be denoted by Tx
and the set of all atomic transversals will be denoted by Txa . We also define the support of
a transversal, t, as
supp t = {i : ti = ˆ0}.
43

From the definitions it is evident that the set of equivalence classes of

n
i=1 RTSi / ker f

is {Tx : x ∈ P }. Moreover, it is clear that the size of the support of an atomic transversal
for x is also its rank in the product of the rooted trees.
We are now in a position to give another factorization theorem. The factorization result
we provide in Section 2.6 will be a special case of this one. Recall that we are using the
notation A(P ) to denote the atom set of a poset P . In particular, A(RTS ) denotes the atoms
in the rooted tree RTS .
Theorem 2.5.3. Let P be a poset with ρ : P → N and let m ∈ N such that ρ(P ) ≤ m.
Moreover, let (S1 , S2 , . . . , Sn ) be an ordered collection of subsets of P which contain ˆ0 and
let f be a transversal function. Suppose the following hold.
(1) If x ≤ y and s ∈ Tx , there exists t ∈ Ty with s ≤ t.
(2) If t ∈ Txa , then | supp t| = ρ(x).
(3) The summation condition (2.1) holds for all Tx .
We can conclude the following.
(a) We have an isomorphism
n

P ∼
=

RTSi

/ ker f.

i=1

(b) For each x ∈ P ,
µ(x) = (−1)ρ(x) |Txa |.

(c) The generalized characteristic polynomial of P with respect to ρ and m (equation (1.3))
is given by
n

χ(P, t) = tm−n

(t − |A(RTSi )|).
i=1

44

Proof. First, we need to show the quotient is a homogeneous quotient. Conditions (2)
and (3) in the definition of a transversal function (Definition 2.5.1) imply condition (1)
of a homogeneous quotient (Definition 2.1.2). To show condition (2) holds, suppose that
Tx ≤ Ty . Then there is a q ∈ Tx and a r ∈ Ty with q ≤ r. Since f is order preserving,
x = f (q) ≤ f (r) = y. By assumption (1) of the theorem, given a s ∈ Tx there is a t ∈ Ty
with s ≤ t and so condition (2) of a homogeneous quotient is satisfied.
Now we show (a). Let f¯ :

n
i=1 RTSi

/ ker f → P be the induced quotient map sending

Tx to x. Since f is surjective, it follows easily that f¯ is a bijection and so has an inverse say
g.
Next we show that f¯ is order preserving. Recall that the elements of the quotient,
( n
i=1 RTSi )/ ker f , are of the form Tx for some x ∈ P . Suppose that Tx ≤ Ty . Then again,
since f is order preserving, x ≤ y and so f¯ is order preserving.
To finish the proof of (a), we show g is order preserving. Suppose that x ≤ y. Since f is
surjective, Tx = ∅. Therefore, by assumption (1), there are s ∈ Tx and t ∈ Ty with s ≤ t.
Using the definition of a quotient poset, we get that that Tx ≤ Ty and so g(x) ≤ g(y).
Now we verify (b). By Lemma 2.1.4, assumption (3), and the fact that isomorphisms
preserve M¨obius values, we have that

µ(x) =

µ(t).
t∈Tx

Since only atomic transversals have nonzero M¨obius value we have

µ(x) =

µ(t).
t∈Txa

45

By assumption (2), all the atomic transversals have the same support size which is the rank
of x. It follows that each atomic transversal for x has M¨obius value (−1)ρ(x) . Therefore we
have that
µ(x) = (−1)ρ(x) |Txa |.
Finally we show (c). By definition,

µ(x)tm−ρ(x) .

χ(P, t) =
x∈P

Using part (b), we get
(−1)ρ(x) |Txa |tm−ρ(x) .

χ(P, t) =
x∈P

We can break this sum into parts, depending on the rank of x. Note that by assumption (2)
and part (b), every element with rank larger than n has M¨obius value zero. Thus we have,


n

χ(P, t) =


(−1)k |Txa |tm−k  .


k=0

ρ(x)=k

Neither (−1)k nor tm−k depend on x so we can pull them out to get,


n

χ(P, t) =



(−1)k tm−k 
k=0

|Txa | .
ρ(x)=k

Using assumption (2) and denoting the k th elementary symmetric function as ek , we have
the inner sum is exactly ek (|A(RTS1 )|, |A(RTS2 )|, . . . , |A(RTSn )|). It follows that,
n

(−1)k ek (|A(RTS1 )|, |A(RTS2 )|, . . . , |A(RTSn )|)tm−k .

χ(P, t) =
k=0

46

Pulling out a factor of tm−n permits us to rewrite the sum as a product
n

χ(P, t) =

tm−n

(t − |A(RTSi )|)
i=1

completing the proof.

2.6

Complete Transversal Functions

By definition, a transversal function must be surjective. However, if we impose more structure on the choice of subsets used to build the rooted trees, we can remove this assumption.
In order to show this, we begin with a definition.
Definition 2.6.1. Let P be a poset and let A be a set of atoms. The complete tree (with
respect to A) is the rooted tree RTUˆ (A) where Uˆ (A) is the upper order ideal generated by the
set A together with ˆ0.
Along with this new definition, we have a new type of function.
Definition 2.6.2. Let P be a poset and let (A1 , A2 , . . . , An ) be an ordered partition of A(P ).
We say f :

n
ˆ (A )
i=1 RTU
i

→ P is a complete transversal function if it is order preserving

and has the property that if in t we have ti = ˆ0 or ti = x for all i, then f (t) = x.
Note that it may appear that complete transversal functions are not transversal functions
because we dropped the condition that they are surjective. However, we will see in the next
lemma that, among other nice properties, the surjectivity of the function is a consequence of
the definition. We also note that if we have a lattice, then f (t) = ∨t is a complete transversal
function where ∨t = t1 ∨ . . . · · · ∨ tn .

47

Lemma 2.6.3. Let P be a poset and let (A1 , A2 , . . . , An ) be an ordered partition of A(P ).
Let f be a complete transversal function. Then we can conclude the following.
(a) The function f is surjective and f is a transversal function.
(b) For all j, tj ≤ f (t1 , t2 , . . . , tn ).
(c) If x ≤ y and s ∈ Tx , there exists t ∈ Ty with s ≤ t.
(d) For x ∈ P , let Ni be the number of atoms below x in Ai , then
n

(1 − Ni ).

µ(s) =

(2.6)

i=1

s∈L(Tx )

(e) The summation condition (2.1) holds for all Tx if and only if for all nonzero x ∈ P ,
there is an index i such that |Ai ∩ Ax | = 1.
Proof. First we show (a). Let ˆ
0 be the transversal having all components equal to ˆ0. Since
we are using complete trees and a partition of the atom set, for every x ∈ P there exists some
i such that ˆ
0(xi ) is a transversal. It follows from the definition of a complete transversal
function that f (ˆ
0(xi )) = x and so f is surjective.
To show that the third condition for a transversal function holds, suppose that f (t) = ˆ0.
By definition of a complete transversal function, f (ˆ
0(tii )) = ti . Since f is order preserving
and ˆ
0(tii ) ≤ t we get that ti = f (ˆ
0(tii )) ≤ f (t) = ˆ0. Therefore, if f (t) = ˆ0, then t = ˆ
0. This
completes the proof that f is a transversal function.
For (b), we noted in the previous paragraph that

j

f (ˆ
0(tj )) = tj .

48

Using the fact that f is order preserving, we get that

j
tj = f (ˆ
0(tj )) ≤ f (t1 , t2 , . . . , tn ).

Next we prove (c). This is trivial if x = ˆ0 so assume x is nonzero. Let s ∈ Tx . Then by
by part (b), si ≤ x for all i. Let t be given by ti = y for all i with i ∈ supp s and ti = ˆ0 for
all other i. Such a t is a valid transversal since si ≤ x ≤ y and we are using complete trees.
Note also that since x = ˆ0 it must be that t has at least one nonzero coordinate. It follows
that t ∈ Ty and s ≤ t.
Next, let us show (d). We start by showing that

L(Tx ) = {t a transversal : ti ≤ x for all i}.

(2.7)

To see that L(Tx ) is contained in the other set, let t ∈ L(Tx ). Then for each i we have
ˆ
0(tii ) ∈ L(Tx ). By definition of a complete transversal function, f (ˆ
0(tii )) = ti . Since f is
order preserving, ti = f (ˆ
0(tii )) ≤ f (t) = x.
For the reverse inclusion, suppose that t is a transversal with ti ≤ x for all i. Let s be
the transversal obtained from t by replacing all the nonzero ti with x. We know that s is
a valid transversal because we are using complete trees. Since f is a complete transversal
function, f (s) = x and so s ∈ L(Tx ). By construction, t ≤ s and therefore t ∈ L(Tx ).
Let I be the set of indices, i, such that there is an atom below x in Ai . By relabeling, if
necessary, we may assume that I = {1, 2, . . . , j}. Since Ni = 0 implies that 1 − Ni = 1,
j

n

(1 − Ni ) =
i=1

(1 − Ni ).
i=1

49

From equation (2.7) we can conclude that the number of atomic transversals in L(Tx )
with support size i is ei (N1 , N2 , . . . , Nj ) where ei is the ith elementary symmetric function.
Now for each atomic transversal s ∈ L(Tx ) we have that µ(s) = (−1)| supp(s)| and all other
transversals have M¨obius value zero. Therefore,
j

j

(−1)i ei (N1 , N2 , . . . , Nj )

µ(s) =
s∈L(Tx )

=

i=0

(1 − Ni )
i=1

which completes part (d).
Finally, (e) follows immediately from (d) and the definition of the summation condition.

Given this lemma, we can use Theorem 2.5.3 to immediately obtain the following.
Theorem 2.6.4. Let P be a poset with ρ : P → N and let m ∈ N such that ρ(P ) ≤ m.
Moreover, let (A1 , A2 , . . . , An ) be an ordered partition of A(P ) and let f be a complete
transversal function. Suppose the following hold.
(1) If t ∈ Txa , then | supp t| = ρ(x).
(2) For all nonzero x ∈ P , there is an index i such that |Ai ∩ Ax | = 1.
We can conclude the following.
(a) We have an isomorphism
n

P ∼
=
i=1

RTUˆ (A )
i

/ ker f.

(b) For each x ∈ P ,
µ(x) = (−1)ρ(x) |Txa |.
50

1230

120 /30

1231

130 /20

10 /230

1232

121 /30

131 /30

10 /231

10 /20 /30
Figure 2.5: The weighted partition poset Πw
3

(c) The generalized characteristic polynomial of P with respect to ρ and m is given by
n

χ(P, t) =

tm−n

(t − |Ai |).
i=1

The reader may be wondering why we did not just assume from the start that we were
using complete transversal functions. By doing so, we reduce the number of things we need
to check and we still get the same conclusions as in Theorem 2.5.3. However, there are
situations where the first theorem applies but the second does not.
Let us give an example were the summation condition (2.1) for Tx needed in Theorem 2.5.3
holds, but the second condition of Theorem 2.6.4 does not. We will consider the weighted
w
partition poset, Πw
n introduced in [2]. The elements of Πn are set partitions of [n] where

each block Bi has one of the following weights {0, 1, . . . , |Bi | − 1}. The weighted partitions
w

w

will be denoted by B1 1 /B2 2 / . . . /Bnwn where wi is the weight of block Bi . The ordering is
given by
v

v

v

w

w

A11 /A22 / . . . /Akk ≤ B1 1 /B2 2 / . . . /Bnwn
if and only if

51

1. We have
A1 /A2 / . . . /Ak ≤ B1 /B2 / . . . /Bn
in the (unweighted) partition lattice Πn .
2. If Bl = Ai1 ∪ Ai2 ∪ · · · ∪ Aim , then

vl − (wi1 + wi2 + · · · + wim ) ∈ {1, 2, . . . , m − 1}.

The weighted partition poset Πw
3 is shown in Figure 2.5. It is easy to check that the
characteristic polynomial of this poset factors as

2
χ(Πw
3 , t) = (t − 3) .

Consider the sets
A1 = {120 /30 , 130 /20 , 121 /30 , ˆ0}
and
A2 = {10 /230 , 131 /30 , 10 /231 , ˆ0}.
Additionally, consider the transversal function f :

2
i=1 RTAi

→ Πw
3 which sends any pair

which contains ˆ0 to the other element in the pair and sends any pair with two non-zero elements to 123i where i is the sum of their exponents. It is easy to check that f is a transversal
function and that the summation condition (2.1) is satisfied. However, the element 1231 is
above every atom so it is impossible that it is above only one atom of either A1 or A2 . One
can also check that all the conditions of Theorem 2.5.3 are satisfied and so we have verified
that the characteristic polynomial does factor using our method.
52

We should also point out that, as was shown in [4], the characteristic polynomial of the
w
n−1 . This was shown using different
weighted partition poset Πw
n factors as χ(Πn , t) = (t−n)

methods than presented here. As of now, we do not have a transversal function which gives
us the factorization.

2.7

Crosscut-simplicial Lattices

As defined in [9], a crosscut-simplicial lattice is a lattice, L, such that if [x, y] is an interval
of L then any proper subset of the atoms of [x, y] has a join different from y. Examples of
crosscut-simplicial lattices include the Tamari lattices, the weak Bruhat order on Coxeter
groups and more generally the Cambrian lattices [10]. In this section we show that a lattice
is crosscut-simplicial if and only if the generalized characteristic polynomial, with respect to
a function we define below, of every interval only has roots 0 and 1.
In addition to using Theorem 2.6.4 to prove this result, we will also make use of a special
case of Rota’s Crosscut Theorem [11]. We will give a proof of the full theorem using quotient
posets in Chapter 3.
Theorem 2.7.1 (Rota’s Crosscut Theorem [11]). Let L be a lattice. For x ∈ L, let ai (x) be
the number of subsets of A(L) of size i whose join is x. Then

(−1)i ai (x).

µ(x) =
i≥0

Theorem 2.7.2. Let L be lattice and let I be any interval in L. Let ρI (x) be the number
of atoms below x in I and let m(I) be the length of the longest chain in I. Suppose that
χ(I, t) is the generalized characteristic polynomial with respect to ρI and m(I). The lattice

53

L is crosscut-simplicial if and only if

χ(I, t) = tm(I)−|A(I)| (t − 1)|A(I)|

for every interval I of L.
Note that if we partition the atoms of an interval I into singleton blocks, then ρI is just
the generalized rank of I. However, since “generalized” is ambiguous without knowing the
partition of the atom set, we have decided to define it differently.
Proof. (⇒) Given an interval I, partition the atoms of I as (A1 , A2 , . . . , Ak ) where each Ak
has exactly one atom. Let f be the complete transversal function defined as f (t) = ∨t. With
this partition we trivially get condition (2) of Theorem 2.6.4. By the definition of ρI , we
must show that the join of any j atoms is above exactly j atoms in order to show condition
(1).
Suppose there was some subset of j atoms of I whose join is above at least j + 1 atoms.
Let x be the meet of these j + 1 atoms and y be the join of the j + 1 atoms. Then L cannot
be crosscut-simplicial since there is a proper subset of atoms in [x, y] whose join is y. Thus
we have a contradiction and so condition (1) of Theorem 2.6.4 is satisfied.
Finally, we must show that m(I) ≥ ρI (I) where m(I) is the length of the longest chain in
I since this was required in the definition of the generalized characteristic polynomial. Let
x0 be the ˆ0 element of I and for each 1 ≤ i ≤ k define
i

xi =

al
l=1

where ai is the unique element of Ai . Since the join of j atoms is above exactly those j
54

atoms, we know that all the xi ’s are distinct. It follows that I contains a chain of length k,
namely the chain x0 < x1 < · · · < xk . Using the definition of ρI , we see that if m(I) is the
length of the longest chain in I then ρI (I) = k ≤ m(I). Applying Theorem 2.6.4 now yields
this direction.
(⇐) We prove the contrapositive. Suppose that L is not crosscut-simplicial. Then there
must be some interval I of L where there is a set of atoms whose join is above more than
just those atoms.
Let j be the minimum number of atoms needed to form a set whose join is above more
than just those j atoms. We claim that the coefficient of tm(I)−j in χ(I, t) cannot be the same
as the coefficient of tm(I)−j in tm(I)−|A(I)| (t − 1)|A(I)| . Suppose that {a1 , a2 , . . . , al } ⊆ A(I)
with ρI (a1 ∨a2 ∨· · ·∨al ) = j. By the definition of ρI , we have that l ≤ j since ai ∨a2 ∨· · ·∨al
is above at least a1 , a2 , . . . , al . If l < j, then there would be a subset of A(I) with l < j
elements whose join was above more than l elements. This contradicts the definition of j.
It follows that if ρI (a1 ∨ a2 ∨ · · · ∨ al ) = j, then l = j. In other words, any subset of A(I)
whose join has rank j has exactly j atoms in it. Applying Theorem 2.7.1, we get that the
coefficient of tm(I)−j in χ(I, t) is (−1)j multiplied by the number of j-element subsets of
A(I) which are above exactly those j atoms.
Since there is at least one j-element subset whose join is above more than j atoms, it must
be that the coefficient of tm(I)−j in χ(I, t) is not (−1)j |A(I)|
. However, (−1)j |A(I)|
is the
j
j
coefficient of tm(I)−j in tm(I)−|A(I)| (t − 1)|A(I)| and so χ(I, t) = tm(I)−|A(I)| (t − 1)|A(I)| .
While the Cambrian lattices provide a large family of crosscut-simplicial lattices, we now
discuss another way to find such lattices. To do so, we will consider the notion of an edge
labeling of a poset. Let P be a poset, let H be its Hasse diagram and let E(H) be the set

55

(x1 (x2 (x3 x4 )))
3
2
(x1 ((x2 x3 )(x4 ))
((x1 x2 )(x3 x4 ))
3

3
((x1 (x2 x3 ))(x4 )
2

(((x1 x2 )x3 )x4 )
Figure 2.6: The Tamari lattice T3 with an SB-labeling

of edges of H. An edge labeling of P is a map λ : E(H) → S, where S is some set. In other
words, we label the edges of the Hasse diagram of the poset. Introduced in [7, Definition
3.4], an SB-labeling of a lattice L is an edge labeling of L such that for all u, v, w ∈ L with
u

v, w then we have the following.
1. If λ(u, v) and λ(u, w) are the labels of the edges from u to v and u and w respectively,
then λ(u, v) = λ(u, w).
2. Every inclusion-maximal chain in the interval [u, v ∨ w] uses only the labels λ(u, v) and
λ(u, w) with each label occurring at least once.
An example of an SB-labeling of the Tamari Lattice T3 is given in Figure 2.6 where

the labels are in boldface. This labeling is the labeling explained in [7, Theorem 5.5]. The
authors in [7, Theorem 3.7] showed that if L has an SB-labeling, then it is crosscut-simplicial.
As pointed out in [9], the converse of this theorem is not true. One way to see this is to
let P be the poset formed by starting with B2 and and replacing one of its atoms with
copy of B3 . Figure 2.7 contains the Hasse diagram of P . It is not hard to check that P is
crosscut-simplicial. Since P only has two atoms whose join is ˆ1, only 2 labels are allowed to
be used to label the entire poset. However, the B3 that we inserted needs at least 3 different
56

.
.
.

.

.

.

.

.

.

.
.
Figure 2.7: A crosscut-simplicial lattice which does not have an SB-labeling

labels and so there is no SB-labeling of P . The author of [9] suggested a generalization
of an SB-labeling which avoids this type of problem. He then goes on to ask the question
if a lattice being crosscut-simplicial is equivalent to having one of these generalizations of
SB-labeling. It would interesting if one could use the equivalent formulation of crosscutsimplicial we described earlier using generalized characteristic polynomials to investigate this
question.

2.8

LL lattices

Having shown what Theorem 2.6.4 can say about crosscut-simplicial lattices, we now turn
our attention to seeing how it implies a theorem of [1]. Earlier we showed how to use the
fact that partitions induced by saturated ˆ0–ˆ1 left-modular multichains imply assumption
(2) of Theorem 2.6.4 to prove Stanley’s Supersolvability Theorem [15]. We will use this
fact to prove Blass and Sagan’s result about LL lattices [1] which is a generalization of the
supersolvability result.
In order to explain this result, we need to define the level condition. Let (A1 , A2 , . . . , An )

57

be induced by C : ˆ0 = x0 ≤ x1 ≤ x2 ≤ · · · ≤ xn = ˆ1 . This multichain also induces a partial
ordering on the atoms denoted by

. It is defined by saying a

b if a ∈ Ai and b ∈ Aj with

i < j. We say that a lattice L with multichain C satisfies the level condition if

a

b1

···

b2

bk

implies that
k

a≤

bi .
i=1

The lattice L is called an LL lattice if it contains a left-modular multichain C and L
together with C satisfy the level condition. We are now in a position to state Blass and
Sagan’s result.
Theorem 2.8.1 ([1]). Let L be a lattice and let (A1 , A2 , . . . , An ) be induced by a left-modular
saturated multichain such that L is an LL lattice. Let ρ be generalized rank and let m be the
length of the longest ˆ0–ˆ1 chain. Then
n

χ(L, t) = tm−n

(t − |Ai |).
i=1

Proof. We wish to use Theorem 2.6.4. First, note that since we are using generalized rank
we have that ρ(P ) is at most the number of nonempty blocks in the partition. Since our
partition is induced by a multichain and since m is the length of the largest chain in the
lattice, we have that ρ(P ) ≤ m.
Define the complete transversal function to be f (t) = ∨t. Although it is not worded
in the same way, the authors in [1, Theorem 6.3 and Lemma 6.4] proved assumption (1)
of Theorem 2.6.4 holds. Finally, as noted before, it was shown in Lemma 2.4.6 that satu58

rated left-modular multichains satisfy the meet condition and so satisfy assumption (2) of
Theorem 2.6.4.
The theorems presented so far have provided conditions which imply factorization. We
would like to finish this section with a theorem where we provide a condition which is
equivalent to factorization.
Theorem 2.8.2. Let P be a poset and let ρ : P → N with m ∈ N such that ρ(P ) ≤
m. Let χ(P, t) be the generalized characteristic polynomial with respect to ρ and m. Let
(A1 , A2 , . . . , An ) be an ordered partition of A(P ) and let f :

n
ˆ (A )
i=1 RTU
i

complete transversal function. Finally, define

T = {x ∈ P \ ˆ0 : |Ai ∩ Ax | = 1 for all i}.

Suppose that the following hold.
1. If t ∈ Txa then | supp(t)| = ρ(x).
2. If x, y ∈ P and x < y, then ρ(x) < ρ(y).
3. For all minimal elements x, y ∈ T , the cardinality of the sets

{i : |Ai ∩ Ax | = 0} and {i : |Ai ∩ Ay | = 0}

have the same parity.
Under these conditions,
n

χ(P, t) =

tm−n

(t − |Ai |)
i=1

59

→ P be a

if and only if for every nonzero x ∈ P there is an index i such that |Ai ∩ Ax | = 1.
This theorem is a generalization of Theorem 2.4.4. The two proofs are quite similar so
we only provide a sketch below.
Sketch of proof. First, note that the backwards direction is Theorem 2.6.4. For the forward
direction, we will prove the contrapositive. Note that the assumption in this direction implies
that T = ∅. Let k be the smallest value of ρ applied to the elements of T . We show that the
coefficient of tm−k in χ(P, t) and in tm−n
Define R =

n
ˆ (A )
i=1 RTU
i

n
i=1 (t − |Ai |)

are different.

/ ker f . We claim that R is a homogeneous quotient and

that P ∼
= R. Since f is a complete transversal function, Lemma 2.6.3 part (c) implies that
assumption (1) of Theorem 2.5.3 is satisfied. Note that the proof of part (a) of Theorem 2.5.3
only requires assumption (1). Therefore, R is homogeneous and P ∼
= R. Since P ∼
= R, it is
enough to show that the coefficient of tm−k in χ(R, t) and in tm−n

n
i=1 (t − |Ai |)

are not

the same.
Let x1 , x2 , . . . , xl be the set of elements of T with ρ(xi ) = k for all i and let S =
{Tx1 , Tx2 , . . . , Txl } be the corresponding equivalence classes. Moreover, define Q to be the
poset obtained from R by removing all elements of R with ρ value larger than k. Using assumption (2), we can see that the M¨obius value of elements with ρ at most k in R and Q are
the same. In Q all elements with ρ value k are maximal. By assumption (2) and the assumption on k any element of Q which is not maximal cannot be in the set T . Then Lemma 2.6.3
part (e) implies that every non-maximal element satisfies the summation condition (2.1).
Thus, we can apply Lemma 2.4.1 to conclude that

µ(t) −

µ(Txi ) =
t∈Txi

µ(s).
s∈L(Txi )

60

Let
ci =

µ(s).
s∈L(Txi )

We claim that all the ci ’s are either 0 or have the same sign. By equation (2.6), if ci = 0,
then the sign of ci is (−1)ki where ki is the number of blocks with atoms below xi . By
assumption (3), for the ci ’s which are not equal to 0, the corresponding ki ’s have the same
parity. Therefore, the signs of the nonzero ci ’s are the same. Since there is at least one
element of T = ∅ in Q, there is at least one ci = 0.
Using the same argument as in the proof of Theorem 2.4.4, we get the coefficient of tm−k
in χ(R, t) is
l

µ(t) −

ci
i=1

| supp t|=k

in which the first sum ranges over atomic transversals. Since there is at least one ci which
is nonzero and all the nonzero ci ’s have the same sign, we see that this coefficient is not the
same as
µ(t).
| supp t|=k

However, the previous expression is the coefficient of tm−k in tm−n
that
n

χ(P, t) =

tm−n

(t − |Ai |)
i=1

which is what we wished to show.

61

n
i=1 (t − |Ai |).

It follows

Chapter 3
Classic Results About the M¨
obius
Function
In this chapter, we will give a new method to prove an array of classic results about the
M¨obius function. To explain the idea, we need a definition. Let P be a poset with a ˆ1. A
coatom of L is an element c ∈ P such that c

ˆ1. The idea of this new method is to use

induction on the size of the poset. In order to do this, we will collapse a coatom and the ˆ1
of the poset.
We begin with a lemma that explains the simple nature of the values of µ for the original
poset and the poset obtained by collapsing a coatom and ˆ1. In the lemma and throughout
the rest of the section, we will use [x] to denote the equivalence class which contains x.
Lemma 3.0.3 ([6]). Let P be a poset with a ˆ0 and ˆ1 and at least 3 elements. Suppose c is a
coatom and let ∼ be the equivalence relation identifying c and ˆ1. Then P/ ∼ is homogeneous
and
µ([ˆ1]) = µ(c) + µ(ˆ1).
Moreover, if P is a lattice, then P/ ∼ is a lattice with [x] ∨ [y] = [x ∨ y] for all x, y ∈ P and
[x] ∧ [y] = [x ∧ y] provided [x], [y] = [ˆ1].
Proof. First, let us show that P/ ∼ is homogeneous. Since there are at least 3 elements
and we are collapsing a coatom and ˆ1, we have that ˆ0 is in its own equivalence class. Now
62

suppose that [x] < [y]. It follows that [x] = {c, ˆ1} since [x] < [y] and [c] = [ˆ1] is the ˆ1 of the
quotient. Therefore, [x] = {x} and so it is obvious that P/ ∼ is a homogeneous quotient.
To show that µ([ˆ1]) = µ(c) + µ(ˆ1) note that since every element of P is below ˆ1 and every
other equivalence class has only one element, we get

µ(y) =

µ(y) = 0
y≤x

y∈L([x])

for all nonzero x = c. By Lemma 2.1.4 this implies that

µ([ˆ1]) = µ(c) + µ(ˆ1)

which is what we wished to prove.
Now suppose that P is a lattice. It is not hard to see that (P/ ∼) ∼
= (P \{c}). Therefore,
if x ∨ y = c, we immediately get that [x] ∨ [y] exists and [x] ∨ [y] = [x ∨ y]. If x ∨ y = c, then
ˆ1 is the only element in P \ {c} which is an upper bound for both x and y. It follows that
[x] ∨ [y] = [ˆ1] = [c] = [x ∨ y]. Since P \ {c} clearly has a ˆ0, we conclude P/ ∼ is a lattice.
Finally, if [x], [y] = [ˆ1] then [x] = {x} and [y] = {y} and so [x] ∧ [y] = [x ∧ y].
Let us now use Lemma 3.0.3 to prove some classic results.
Corollary 3.0.4 (Hall’s Theorem [5]). Let P be a finite poset, then

(−1)i ci

µ(x, y) =
i≥0

where ci is the number of chains of length i which start at x and terminate at y.
Proof. Without loss of generality we may assume that x = ˆ0 and y = ˆ1 since all chains which
63

start at x and terminate at y are in the interval [x, y]. We prove the theorem by inducting
on |P |. If |P | = 1 or |P | = 2 then the result is obvious.
Now suppose that |P | > 2. Let P/ ∼ be obtained by identifying a coatom c and ˆ1.
Consider the sum
(−1)i ci
i≥0

where ci is the number of ˆ0–ˆ1 chains of length i in P . Let ai be the number chains of length
i which do not contain c and let bi be the number chains of length i containing c. Then

(−1)i ci =
i≥0

(−1)i ai +
i≥0

(−1)i bi .
i≥0

There exists a bijection between ˆ0–ˆ1 chains in P not containing c and [ˆ0]–[ˆ1] chains in P/ ∼
which preserves length. Moreover, there is a bijection between ˆ0–ˆ1 chains in P containing c
and ˆ0–c chains in [0, c]. Note that in this bijection, the chains decrease by one in length.
Since |P/ ∼ | < |P |, using induction we get that

(−1)i ai .

µ([ˆ1]) =
i≥0

Similarly since |[0, c]| < |P | we get that

(−1)i bi

µ(c) = −
i≥0

where we have multiplied the sum by −1 since the chains have decreased by one in length.

64

By Lemma 3.0.3, we have that

µ([ˆ1]) = µ(c) + µ(ˆ1)

or equivalently
µ(ˆ1) = µ([ˆ1]) − µ(c).
Therefore,
(−1)i ai +

µ(ˆ1) =
i≥0

(−1)i bi =
i≥0

(−1)i ci
i≥0

which is what we wished to prove.
Next, we prove a theorem of Weisner.
Corollary 3.0.5 (Weisner’s Theorem [18]). Let L be a lattice and let ˆ0 = a ∈ L. If |L| ≥ 2,
then
µ(ˆ1) = −

µ(x).
x=ˆ1,x∨a=ˆ1

Proof. Let us note that if a = ˆ1, then the result is just restating the definition of µ, so we
assume that a = ˆ1 for the rest of the proof. We prove the result by induction. We have
already covered the case |L| = 2, since then a must be ˆ1.
Now suppose that |L| > 2. Let c be a coatom such that a ≤ c. Consider, the lattice
L/ ∼ obtained by identifying c and ˆ1. Since |L/ ∼ | < |L|, we get that

µ([ˆ1]) = −

µ([x]).
[x]=[ˆ1],[x]∨[a]=[ˆ1]

65

Using the facts that [ˆ1] = {c, 1}, [x] ∨ [a] = [x ∨ a], and µ([x]) = µ(x) for [x] = [ˆ1], we obtain,

µ([ˆ1]) = −

µ(x).
x=c,ˆ1,x∨a=c,ˆ1

Since joins are unique, we can break the sum into two parts as,

µ([ˆ1]) = −

µ(x) −
x=c,ˆ1,x∨a=c

µ(x).
x=c,ˆ1,x∨a=ˆ1

If x ∨ a = c, then it is clear that x ∈ [0, c]. Moreover, since a ≤ c, it is clear that c ∨ a = ˆ1.
Thus, we can remove the x = ˆ1 condition in the first sum and remove the x = c condition
in the second. This gives,

µ([ˆ1]) = −

µ(x) −
x=c,x∨a=c

µ(x).
x=ˆ1,x∨a=ˆ1

Now the first sum is only over [0, c] and |[0, c]| < |L| so by induction,

µ([ˆ1]) = µ(c) −

µ(x).
x=ˆ1,x∨a=ˆ1

Using the fact that µ([ˆ1]) = µ(ˆ1) + µ(c), we immediately obtain the result.
Our next corollary will make use of crosscuts. We remind the reader of a few definitions
here. Let P be a poset, a subset C ∈ P is called an antichain if whenever x, y ∈ C, then
x ≤ y and x ≥ y.
Definition 3.0.6. Let L be a lattice. A crosscut of L is a set C with the following properties:
1. ˆ0, ˆ1 ∈
/ C.
66

2. C is an antichain.
3. Every maximal ˆ0–ˆ1 chain intersects C.
Although we will not need it to state the next theorem, we will need the notion of the
dual of a poset in the proof. Let P be a poset. The dual of P , written as P ∗ , is the poset
with the same underlying set and binary relation given by saying x ≤P ∗ y if and only if
y ≤P x.
Theorem 3.0.7 (Rota’s Crosscut Theorem [11]). Let L be a lattice and let C be a crosscut.
Then
(−1)|B|

µ(ˆ1) =

∨B=ˆ1,∧B=ˆ0

where the sum ranges over all B ⊆ C such that ∨B = ˆ1 and ∧B = ˆ0.
Proof. We first consider the special case when every coatom is also an atom. In this case, the
crosscut must be the atom set. Moreover, a subset of the crosscut has meet ˆ0 and join ˆ1 if
and only if it has at least two elements. Therefore, if L has n atoms we obtain the following
n

(−1)|B|

=

∨B=ˆ
1,∧B=ˆ
0

(−1)|B|
|B|≥2

(−1)k

=
k=2

n
k

= n − 1.

This agrees with the value of µ(ˆ1) when L has n atoms and every coatom is an atom. Thus,
the result holds in this special case.
Recall that if L∗ is the dual lattice of L, then µL (ˆ1) = µL∗ (ˆ1). Moreover, in L∗ , joins
and meets reverse roles. Therefore, if we have a crosscut consisting of only coatoms, then
we can consider the dual lattice. As a result, we may now assume that there is always at
least one coatom in the lattice which is not in the crosscut. With this in mind we proceed
67

by induction on |L|.
If |L| ≤ 3, then it must be that |L| = 3 since smaller lattices do not have crosscuts. We
have already done the case when |L| = 3. Suppose that |L| > 3 and let c be a coatom that
is not in the crosscut. Consider the lattice L/ ∼ where we collapse c and ˆ1. Since c was not
in the crosscut we still have the same crosscut. By induction, we know that

(−1)|B| .

µ([ˆ1]) =

∨B=[ˆ1],∧B=[ˆ0]

Lemma 3.0.3 implies that ∨B = [ˆ1] in L/ ∼ if and only if ∨B = c or ∨B = ˆ1 in L.
Additionally, since C does not contain c nor ˆ1, Lemma 3.0.3 also implies that ∧B = [ˆ0] in
L/ ∼ if and only if ∧B = ˆ0 in L. Therefore, we can break the previous sum as follows

(−1)|B| +

µ([ˆ1]) =
∨B=c,∧B=ˆ0

(−1)|B| .
∨B=ˆ1,∧B=ˆ0

Note that if ∨B = c, then B must only have elements in [ˆ0, c]. Thus the first sum in the
previous equation is over B contained in [ˆ0, c] ∩ C such that ∨B = c and ∧B = ˆ0. Since
|[ˆ0, c]| < |L|, induction implies that

(−1)|B| .

µ([ˆ1]) = µ(c) +

∨B=ˆ1,∧B=ˆ0

Subtracting µ(c) from both sides and applying Lemma 3.0.3 we see that

(−1)|B|

µ(ˆ1) =
∨B=ˆ1,∧B=ˆ0

68

which completes the proof.

69

BIBLIOGRAPHY

70

BIBLIOGRAPHY
[1] Andreas Blass and Bruce E. Sagan. M¨obius functions of lattices. Adv. Math., 127(1):94–
123, 1997.
[2] V. V. Dotsenko and A. S. Khoroshkin. Character formulas for the operad of a pair of
compatible brackets and for the bi-Hamiltonian operad. Funktsional. Anal. i Prilozhen.,
41(1):1–22, 96, 2007.
[3] Haya Friedman and Dov Tamari. Probl`emes d’associativit´e: Une structure de treillis
finis induite par une loi demi-associative. J. Combinatorial Theory, 2:215–242, 1967.
[4] R. S. Gonz´alez D’Le´on and M.L. Wachs. On the (co)homology of the poset of weighted
partitions. preprint.
[5] P. Hall. The eulerian functions of a group. Quart J. Math, 7(1):134–151, 1936.
[6] Joshua Hallam and Bruce Sagan. Factorization of the Characteristic Polynomial of a
Lattice using Quotient Posets. 26th International Conference on Formal Power Series
and Algebraic Combinatorics. DMTCS Proceedings 2014, 125-136.
[7] Patricia Hersh and Karola M´esz´aros. SB-labelings and posets with each interval homotopy equivalent to a sphere or a ball. preprint arXiv:1407.5311
[8] Samuel Huang and Dov Tamari. Problems of associativity: A simple proof for the lattice
property of systems ordered by a semi-associative law. J. Combinatorial Theory Ser.
A, 13:7–13, 1972.
[9] Thomas McConville. Crosscut-simplicial Lattices preprint arXiv:1409.6269.
[10] Nathan Reading. Cambrian Lattices Advances in Mathematics, 205(2): 313–353, 2006.
[11] Gian-Carlo Rota. On the foundations of combinatorial theory. I. Theory of M¨obius
functions. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2:340–368 (1964), 1964.
[12] Bruce E. Sagan. Why the characteristic polynomial factors. Bull. Amer. Math. Soc.
(N.S.), 36(2):113–133, 1999.

71

[13] Kyoji Saito. Theory of logarithmic differential forms and logarithmic vector fields. J.
Fac. Sci. Univ. Tokyo Sect. IA Math., 27(2):265–291, 1980.
[14] R. P. Stanley. Enumerative combinatorics. Volume 1 Cambridge Studies in Advanced
Mathematics, 2012.
[15] R. P. Stanley. Supersolvable lattices. Algebra Universalis, 2:197–217, 1972.
[16] Hiroaki Terao. Factorizations of the Orlik-Solomon algebras Adv. Math. 91:45–53, 1992.
[17] Hiroaki Terao. Generalized exponents of a free arrangement of hyperplanes and
Shepherd-Todd-Brieskorn formula. Invent. Math., 63(1):159–179, 1981.
[18] Louis Weisner. Abstract theory of inversion of finite series. Trans. Amer. Math. Soc.,
38(3):474–484, 1935.
[19] Thomas Zaslavsky. Signed graph coloring. Discrete Math., 39(2):215–228, 1982.

72