¨
THE MOBIUS FUNCTION OF GENERALIZED FACTOR ORDER
By
Robert Willenbring

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
DOCTOR OF PHILOSOPHY
Mathematics
2011

ABSTRACT
¨
THE MOBIUS FUNCTION OF GENERALIZED FACTOR ORDER
By
Robert Willenbring
We use discrete Morse theory to determine the M¨bius function of posets ordered by generalized
o
factor order. Ordinary factor order on the Kleene closure A∗ of a set A is the partial order defined
by letting u ≤ w if w contains u as a subsequence of consecutive letters. The M¨bius function
o
of ordinary factor order was determined by Bj¨rner. Using Babson and Hersh’s application of
o
Robin Forman’s discrete Morse theory to lexicographically ordered chains, we are able to gain
new understanding of Bj¨rner’s result and its proof. We generalize the notion of factor order
o
to take into account a partial order on the alphabet A and, relying heavily on discrete Morse
theory, give a formula in the case where each letter of the alphabet covers a unique letter.

For my parents
Mike and Joan Willenbring

iii

ACKNOWLEDGMENT

I would like to thank my advisor, Dr. Bruce Sagan, for his dedication and commitment to my
education, regardless of his physical proximity to it.

iv

TABLE OF CONTENTS

List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
List of Figures

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 Introduction

vi
vii
1

2 Ordinary Factor Order

14

3 Generalized Factor Order on P

24

4 Generalized Factor Order on Trees and Forests

59

5 Future Research and Open Problems
5.1 Generalizing and Simplifying this Formula . . . . . . . . . . . . . . . . . . . . .
5.2 The Topology of P∗ and F ∗ Under Generalized Factor Order. . . . . . . . . . .
5.3 The Consecutive Pattern Poset and Ordinary Factor Order . . . . . . . . . . . .

77
77
78
79

A The Matching of Babson and Hersh

82

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

v

LIST OF TABLES

1

A poset lexicographic ordering of the eight maximal chains of [b, bbabb] . . . . .

8

2

The same ordering of the maximal chains of [b, bbabb] with information about the
chain ids. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3

The MSIs of the maximal chains of [b, bbabb]. . . . . . . . . . . . . . . . . . . . .

11

4

Comparing I(C), J(C) for the maximal chains of [a, abbabb]. . . . . . . . . . . .

13

5

The MSIs of the maximal chains of [121, 1221] in P∗ . . . . . . . . . . . . . . . .

30

6

The MSIs of the maximal chains of [2, 2212] in P∗ . . . . . . . . . . . . . . . . . .

31

vi

LIST OF FIGURES

1

The interval [b, bbabb]. The M¨bius value µ(b, v) is given to the lower left of each
o
word v. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

2

An example of a Morse function on a simplicial complex . . . . . . . . . . . . .

5

3

The interval [121, 1221]. The M¨bius value µ(121, v) is given below of each word v. 25
o

4

The interval [2, 2212]. The M¨bius value µ(2, v) is given below of each word v. .
o

vii

26

Chapter 1
Introduction
The M¨bius function µ is an important invariant providing a bridge amongst various diverse
o
areas of mathematics, such as combinatorics, number theory, and algebraic topology. The
M¨bius function of factor order was determined by Anders Bj¨rner [4]. This research was
o
o
motivated by a desire to give a proof of Bj¨rner’s result which provides a deeper explanation
o
of the concepts he used to state his recursive formula, and to generalize these concepts so that
they apply to a wider class of posets. These investigations utilize discrete Morse theory, which
also provides a useful context in which to consider the topology of posets. The major result is
a formula for the M¨bius function when factor order is generalized to include a partial ordering
o
of letters, provided each letter covers a unique element. Since it is clear this formula would have
been nearly impossible to discover using other techniques of investigating M¨bius functions, this
o
paper illustrates the ability of discrete Morse theory to simplify complex combinatorial problems
of this nature.
Let A be any set. The Kleene closure, A∗ , is the set of all finite length words over A. So if
w is a word and w(i) is the ith letter in w, then
A∗ = {w = w(1)w(2) . . . w(n) : ∞ > n ≥ 0 and w(i) ∈ A for all i}.
The length of w, denoted |w|, is the number of letters in w. Ordinary factor order on A∗ is the
partial order on A∗ defined by letting u ≤ w if w contains a subsequence of consecutive letters
w(i + 1)w(i + 2) . . . w(i + n) such that u(j) = w(i + j) for 1 ≤ j ≤ n = |u|. When u ≤ w, we
1

call u a factor of w. A word u is flat if u(1) = . . . = u(n), where n = |u|.
For example, if A = {a, b}, then bbabb is an element of A∗ of length |bbabb| = 5. Factors of
bbabb include words such as bbab, abb, and bb. Notice the word bb is flat.
A closed interval [u, w] in A∗ is the subposet consisting of all v ∈ A∗ satisfying u ≤ v ≤ w.
The open interval (u, w) is defined similarly. If the interval [u, w] consists of the two elements u
and w, we say w covers u and write w → u. The Hasse diagram of a poset P is the graph whose
vertices are the elements of P , and in which an edge is found between two vertices w and u if
w → u. For example, if A = {a, b}, the Hasse diagram of [b, bbabb] in A∗ is given in Figure 1.
Let u < w be two elements in a poset P . The M¨bius function µ is a map from P × P to
o
the integers defined recursively as follows:
µ(u, u) = 1
µ(u, w) = −

µ(u, v)
u≤v<w

µ(w, u) = 0.
Figure 1 contains the M¨bius value µ(b, v) for each word v in the interval [b, bbabb]. Working
o
from the bottom of the diagram to the top, we see that µ(b, b) = 1 by the first condition in the
definition. Using the recursive definition, we can calculate µ(b, bb) = −µ(b, b) = −1. In higher
rows, we again use the recursive definition to calculate µ(b, abb) = −(µ(b, bb)+µ(b, ab)+µ(b, b)) =
1, and µ(b, babb) = −(µ(b, abb) + µ(b, bab) + µ(b, bb) + µ(b, ab) + µ(ba, b) + µ(b, b)) = 0.
To state Bj¨rner’s formula, we need a few more definitions. A prefix of a word w ∈ A∗ is
o
a factor of w that includes the first letter of w. Similarly, a suffix of w is a factor of w that
contains the last letter of w. A prefix or suffix is proper if it is not equal to w. Define the outer
word o(w) of w to be the longest factor that appears as both a proper prefix and suffix in w.
2

bbabb
−1
babb
0

bbab
0

abb
1

bab
1

bba
1

bb
−1

ab
−1

ba
−1

b
1
Figure 1: The interval [b, bbabb]. The M¨bius value µ(b, v) is given to the lower left of each
o
word v.

Notice that o(w) can be the empty word. Define the inner word i(w) of w to be the factor
i(w) = w(2)...w(n − 1), where n = |w|.
For example, prefixes of bbabb include bb and bba, while suffixes include bb and b. Note
o(bbabb) = bb and i(bbabb) = bab. The word abb has the empty word as its outer word.
The following theorem of Bj¨rner gives a formula for the M¨bius function in ordinary factor
o
o
order.
Theorem 1 ([4]). In ordinary factor order, if u ≤ w then

µ(u, w) =




µ(u, o(w))








1



(−1)|w|−|u|








0


if |w| − |u| > 2 and u ≤ o(w) ≤ i(w),
if |w| − |u| = 2, w is not flat, and u = o(w) or u = i(w),
if |w| − |u| < 2,
otherwise.

Using this formula, we see that µ(b, bbabb) = µ(b, bb) = −1. Since b is the outer word of
3

bab, we get µ(b, bab) = 1 by the second condition. Notice that since o(babb) = b < ab = i(w),
µ(b, babb) = 0. The reader is encouraged to verify the remaining values implied by the definition
of the M¨bius function for the example in Figure 1 are consistent with those found by using this
o
formula. Notice this formula indicates the only possible values for the M¨bius function in A∗
o
are −1, 0, and 1.
To prove his result, Bj¨rner relied on successively removing irreducible elements in an interval,
o
where an irreducible element is one covered by or covering exactly one element. Bj¨rner also
o
considered the M¨bius function of subword order [3]. In [7], Sagan and Vatter expanded upon
o
his results in the subword order case. In one proof of their result, they used the technique of
critical maximal chains introduced by Babson and Hersh in [1]. This technique uses discrete
Morse theory, which was developed by Forman [5]. Since our first goal is to apply the result of
Babson and Hersh to reprove Bj¨rner’s formula, we will introduce the notation and definitions
o
we need to make use of the relevant theorem. For a more complete introduction to discrete
Morse theory, see Forman’s primer [6].
Discrete Morse theory is an adaptation of Morse theory that can be used to analyze the
topology of a simplicial complex. An abstract simplicial complex is a set of vertices V and a set
K of subsets of V satisfying the following conditions:
if v ∈ V , then {v} ∈ K,
and
if α ∈ K and γ ⊆ α, then γ ∈ K.
Each α is called a simplex, and if α < β, α is called a face of β. The dimension of a simplex
α is the number of vertices in α minus 1. Writing αd will indicate the simplex α has dimension
d.
4

4

3

0

6

5

7

1

8

9

2

Figure 2: An example of a Morse function on a simplicial complex

Let K be a simplicial complex and assume K has an empty simplex of dimension −1 which
is contained in every other simplex. A function f : K −→ R is a discrete Morse function if
every simplex αd satisfies the following conditions:
#{β d+1 > α|f (β) ≤ f (α)} ≤ 1

(1.1)

#{γ d−1 < α|f (γ) ≥ f (α)} ≤ 1

(1.2)

We denote the set in (1.1) by α+ and the set in (1.2) by α− .
A simplex α is critical if #α+ = #α− = 0. Note this definition states that with at most
one local exception, a Morse function increases with respect to the dimension of a simplex.
Figure 2 contains an example of a simplicial complex K consisting of 4 simplices of dimension
0, 5 simplices of dimension 1, and 1 simplex of dimension 2. The values of a Morse function
f appear next to each simplex. Note that the edge labeled 9 and vertex labeled 0 are the
only critical simplices because locally, they are the only simplices for which the Morse function
increases with respect to dimension.
One can prove that at most one of the sets α+ and α− has size 1. This result is crucial
in proving the results concerning discrete Morse functions in this introduction. Note that since
β ∈ α+ implies α ∈ β− , it follows that simplices which are not critical come in pairs, and these
5

pairs satisfy f (αd ) > f (β d+1 ). A Morse matching is a partition of the simplices of K into
sets of size one or two such that each one element set contains a critical simplex of a Morse
function f and each two element set consists of two non-critical simplices αd < β d+1 satisfying
f (αd ) > f (β d+1 ).
The Morse matching of the simplices for the function shown in Figure 2 is {0}, {2, 1},
{4, 3}, {7, 5}, {8, 6}, {9}, where, as an abuse of notation, each number refers to the simplex
to which it is assigned.
Critical simplices are important from a topological viewpoint because Forman shows in [5]
that K is homotopy equivalent to a CW-complex with exactly one cell of dimension d for each
critical simplex α of dimension d. Forman also proves the following Theorem in [5].

Theorem 2 (Weak Morse Inequalities). Let md be the number of critical simplices of dimension
˜
d, ˜d be the d-th reduced Betti number over the integers, and χ be the reduced Euler characteristic.
b
˜
Then
˜ ≤ m for d ≥ −1
bd
˜d
and
χ(W ) =
˜

(−1)d md .
˜
d≥−1

Discrete Morse theory can be used to find information about the M¨bius function of a poset
o
by using the connection between it and the reduced Euler characteristic of the order complex
of a poset. A chain in a poset is set of elements {v0 , v1 , . . . , vn } such that v0 > v1 > . . . > vn .
For clarity, we write a chain C as C : v0 > v1 > . . . > vn . Given two elements u and w of a
poset P , the order complex ∆(u, w) is the abstract simplicial complex whose simplices are the
chains in the open interval (u, w). An important fact about the M¨bius function [8] is
o
6

µ(u, w) = χ(∆(u, w)).
˜
Therefore, by using discrete Morse theory to investigate the chains of (u, w), it is possible to
calculate the M¨bius function and obtain additional information about the topology of the order
o
complex.
Given two elements u, w in a poset P , Babson and Hersh have developed a way of finding
a Morse matching for ∆(u, w) which gives a relatively small number of critical simplices. We
need to develop a considerable amount of terminology to properly state their result.
Let C : v0 → v1 → . . . → vn be a chain in a poset P . Since each pair of adjacent elements
are related by a cover, C is called a saturated chain. The closed interval of C from vi to vj is
the chain C[vi , vj ] : vi → vi+1 → . . . → vj . The open interval of C from vi to vj , C(vi , vj ),
and the half open intervals C[vi , vj ) and C(vi , vj ] are defined similarly. The closed interval
C[vi , vi ] consisting of the single element vi will also be written vi , but the context will always
indicate whether we are referring to the element or the interval. Notice that the interval [u, w]
is non-empty when u ≤ w in the poset P , while C[vi , vj ] is non-empty when vi ≥ vj . A chain
C of the interval [u, w] is a maximal chain if v0 = w and vn = u.
Given two maximal chains C : v0 → v1 → . . . → vn and D : w0 → w1 → . . . → wn in
an interval [u, w], we say C and D agree to index k if vi = wi for all i ≤ k. We say C and D
diverge from index k if C and D agree to index k and vk+1 = wk+1 .
In Table 1, we have listed the eight maximal chains of [b, bbabb]. The first two maximal
chains agree to indices 0, 1, and 2. These two chains diverge from index 2.
A total ordering C1 < C2 < . . . < Cn of the maximal chains of an interval is a poset
lexicographic order if it satisfies the following: suppose C < D and C and D diverge from index
7

v0
v1
bbabb −→ babb −→
bbabb −→ babb −→
bbabb −→ babb −→
bbabb −→ babb −→
bbabb −→ bbab −→
bbabb −→ bbab −→
bbabb −→ bbab −→
bbabb −→ bbab −→
Table 1: A poset lexicographic ordering

v2
v3
v4
abb −→ bb −→ b
abb −→ ab −→ b
bab −→ ab −→ b
bab −→ ba −→ b
bab −→ ab −→ b
bab −→ ba −→ b
bba −→ ba −→ b
bba −→ bb −→ b
of the eight maximal chains of [b, bbabb]

k; if C and D agree to index k + 1 with C and D, respectively, then C < D .
To illustrate the definition, let us investigate one case in Table 1. Note the first chain and
eighth chain agree to index 0. Since the second chain agrees with the first to index 1, and the
seventh chain agrees with the eighth to index 1, we would need to have the second chain appear
earlier than the seventh in order for this to be a poset lexicgoraphic order. In fact, the ordering
given in Table 1 is a poset lexicographic ordering of the maximal chains of [b, bbabb].
To verify we have given a poset lexicographic ordering of the maximal chains of [b, bbabb], it
is easiest to informally discuss how it was created. The formal construction appears in Section 2.
To get this ordering, we record the positions li , relative to w, removed to get from vi−1 to vi .
The sequence l1 − l2 − . . . − ln is called the chain id of the maximal chain. By lexicographically
ordering these chain ids, we get a poset lexicographic order (in terms of Babson and Hersh, this
is a chain labeling). To clearly indicate where each li comes from, we can zero out the positions
removed in each word, creating an embedding of the word vi into w. If a word consists entirely
of one letter (such as bb), removing any letter gives the same word, so by convention, we only
allow the first (non-zero) position to be removed.
In Table 2, we give same poset lexicographic order as above with this extra information about
8

Chain Id
v0
l1
v1
l2
v2
l3
1-2-3-4 bbabb 1 0babb 2 00abb 3
1-2-5-3 bbabb 1 0babb 2 00abb 5
1-5-2-3 bbabb 1 0babb 5 0bab0 2
1-5-4-3 bbabb 1 0babb 5 0bab0 4
5-1-2-3 bbabb 5 bbab0 1 0bab0 2
5-1-4-3 bbabb 5 bbab0 1 0bab0 4
5-4-1-3 bbabb 5 bbab0 4 bba00 1
5-4-3-1 bbabb 5 bbab0 4 bba00 3
Table 2: The same ordering of the maximal chains of
about the chain ids.

v3
l4
v4
000bb 4 0000b
00ab0 3 000b0
00ab0 3 000b0
0ba00 3 0b000
00ab0 3 000b0
0ba00 3 0b000
0ba00 3 0b000
bb000 1 0b000
[b, bbabb] with information

the order. Notice that when only one digit numbers are used for each label li , lexicographically
ordering the chain ids is equivalent to ordering n digit numbers by size.
Recall we need to consider the chains of the open interval (u, w) because the order complex
∆(u, w) is defined in terms of the open interval. Note that the maximal chains of (u, w) are in
a one to one correspondence with those of [u, w]: by removing the first and last vertex from a
maximal chain in [u, w], we get a maximal chain in (u, w). Thus, we will continue to list v0 and
vn in our examples to make it easier to identify the labels l1 and ln .
Suppose C1 < C2 < . . . < Cn is a lexicographic ordering of the maximal chains of (u, w).
Recall that the chains of (u, w) are the simplices in the order complex ∆(u, w). Call a simplex
contained in C new if it is not contained in any C for C < C. We can inductively define a
Morse matching on ∆(u, w) by extending the matching at the k th step to the new simplices of
C. In fact, Babson and Hersh show in [1] that a matching can be constructed in this manner so
that during each step k, at most one new simplex is a critical simplex. So, using this process,
adding each maximal chain adds at most one critical simplex. We will refer to a maximal chain
that contributes a critical simplex as a critical chain.
9

To motivate the next set of definitions, we consider which subchains of a maximal chain C
appear in a lexicographically earlier chain, and which ones are new simplices. In a maximal
chain C of a poset lexicographic ordering, Babson and Hersh prove that each maximal subchain
of C which appears in a lexicographically earlier chain consists of a subchain of C given by a
skipping a single interval of consecutive ranks. This is because the poset lexicographic ordering
assures that if C and C diverge from index k, but later are the same at index , there is some
chain D < C, possibly equal to C , such that C and D are the same outside the interval
C(vk , v ). These skipped intervals are referred to as minimally skipped intervals. Therefore,
a simplex in C entirely belongs to a lexicographically earlier chain if it entirely misses any of
the minimally skipped intervals. Equivalently, the new simplices of C are those subchains of C
which intersect every minimally skipped interval of C non-trivially.
Formally, given an ordering of the maximal chains of [u, w], a non-empty interval (vi , vj ) is
a skipped interval of a maximal chain C if
C − C(vi , vj ) ⊂ C for some C < C.
It is a minimally skipped interval (MSI) if it does not properly contain another skipped interval.
We write I(C) for the set of all MSIs of a chain C. To find the set I(C), consider each interval
I ⊆ C and see if C −I ⊂ C for any C ⊂ C, then throw out any such interval that is nonminimal.
For an example of both MSIs and new simplices, see Table 3. In this table, we have placed
brackets around each interval which is minimally skipped, and placed the corresponding brackets
into the chain id. For example, the intervals D[bb, bb] and D[bbab, bba] are minimally skipped
intervals of chain D with chain id 5 − 4 − 3 − 1. To see how one determines the minimally
skipped intervals, consider the third chain C with chain id 1 − 5 − 2 − 3. The only intervals
I satisfying C − I ⊂ C for some C < C are C[bab, ab], since C − C[bab, ab] is in the first
10

Chain Id
v0
l1
v1
l2
v2
l3
v3
l4
v4
MSIs
1-2-3-4 bbabb 1 0babb 2 00abb 3 000bb 4 0000b
1-2-5[-]3 bbabb 1 0babb 2 00abb 5 [00ab0] 3 000b0 [ab, ab]
1-5[-]2-3 bbabb 1 0babb 5 [0bab0] 2 00ab0 3 000b0 [bab, bab]
1-5-4[-]3 bbabb 1 0babb 5 0bab0 4 [0ba00] 3 0b000 [ba, ba]
5[-]1-2-3 bbabb 5 [bbab0] 1 0bab0 2 00ab0 3 000b0 [bbab, bbab]
5[-]1-4[-]3 bbabb 5 [bbab0] 1 0bab0 4 [0ba00] 3 0b000 [bbab, bbab] [ba, ba]
5-4[-]1-3 bbabb 5 bbab0 4 [bba00] 1 0ba00 3 0b000 [bba, bba]
5[-4-]3[-]1 bbabb 5 [bbab0 4 bba00] 3 [bb000] 1 0b000 [bbab, bba] [bb, bb]
The new simplices, which are in C \ (∪C <C C ), for selected maximal chains C:
1 − 5 − 2 − 3 : bab, babb − bab, bab − ab, babb − bab − ab
5 − 4 − 3 − 1 : bba − bb, bbab − bb, bbab − bba − bb
Table 3: The MSIs of the maximal chains of [b, bbabb].

chain, and C[bab, bab], since C − C[bab, bab] is in the second chain. Since the second interval is
contained in the first, the only MSI in the third chain is C[bab, bab]. So the new simplices in this
chain, which intersect this MSI, are the subchains bab, babb − bab, bab − ab, and babb − bab − ab.
The set of MSIs I(C) covers C if its union equals the open interval C(v0 , vn ). This last
definition reflects the fact that the order complex of an interval is constructed without the
maximum and minimum elements. Notice the set I(D) for the maximal chain D with chain id
5 − 4 − 3 − 1 covers D, and that the set of MSIs I(C) for any other maximal chain C in the
interval [b, bbabb] does not cover C.
Notice I(C) could contain intervals that overlap, that is, intervals with non-empty intersection. We will need to produce a set of disjoint intervals from I(C), which we will call J(C). We
construct J(C) = {J1 , J2 , . . .} as follows. Order the intervals of I(C) based on when they are
first encountered in C. Thus, I1 will contain the word vi of smallest index that appears in any
interval in I(C), I2 will contain the word vj of smallest index that appears in any interval in
I(C) not equal to I1 , etc. Let J1 = I1 . Then consider the intervals I2 = I2 − J1 , I3 = I3 − J1 ,
11

and so forth. Throw out any that are not containment minimal, and pick the first one that
remains to be J2 . Continue this process until no intervals remain to add to J(C).
For an example of the difference between I(C) and J(C), we need to consider a new interval.
In the interval [a, abbabb], whose maximal chains are found in Table 4, the chain C with chain
id 6 − 5 − 4 − 3 − 2 has a set of MSIs I(C) in which there is overlap. To construct J(C), we first
add the MSI I1 = C[abbab, abba] of I(C) to J(C). Then we truncate the remaining intervals in
I(C). In particular, I2 = C[abba, abb] becomes I2 = C[abb, abb], while the chain I3 = C[abb, ab]
does not overlap with I1 , giving I3 = I3 . Now we see that I2 ⊂ I3 . So we remove I3 from
the set of intervals under consideration, and add I2 to J(C). At this point, no intervals of the
original set I(C) remain to be considered, so J(C) = {I1 , I2 }.
The following theorem of Babson and Hersh gives the connection between J(C) and µ(u, w).
For a description, and example, of the Morse matching of simplices which leads to this Theorem,
please see Appendix A.
Theorem 3 ([1]). Let P be a poset and [u, w] be a finite interval in P . For any poset lexicographic
order on the maximal chains of [u, w], the above construction can be used to produce a Morse
matching which matches all the new simplices of a chain, except possibly one which is critical.
The set J(C) for each C has the following properties:
1. A maximal chain C is critical if and only if J(C) covers C.
2. If C is critical, then the dimension of its critical simplex is
d(C) = #J(C) − 1.
3. The M¨bius value from u to w is
o
(−1)d(C)

µ(u, w) =
C

where the sum is over all critical chains C in [u, w].
12

I(C) intervals for [a, abbabb]
Chain Id
1-2-3-6-5
1-2-6[-]3-5
1-2-6-5[-]3
1-6[-]2-3-5
1-6[-]2-5[-]3
1-6-5[-]2-3
6[-]1-2-3-5
6[-]1-2-5[-]3
6[-]1-5[-]2-3
6-5[-]1-2-3
6[-5[-]4[-]3-]2

v0
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb
abbabb

l1
1
1
1
1
1
1
6
6
6
6
6

v1
l2
0bbabb 2
0bbabb 2
0bbabb 2
0bbabb 6
0bbabb 6
0bbabb 6
[abbab0] 1
[abbab0] 1
[abbab0] 1
abbab0 5
[abbab0 5

v2
l3
00babb 3
00babb 6
00babb 6
[0bbab0] 2
[0bbab0] 2
0bbab0 5
0bbab0 2
0bbab0 2
0bbab0 5
[abba00] 1
[abba00] 4

v3
l4
000abb 6
[00bab0] 3
00bab0 5
00bab0 3
00bab0 5
[0bba00] 2
00bab0 3
00bab0 5
[0bba00] 2
0bba00 2
[abb000] 3

v4
l5
000ab0 5
000ab0 5
[00ba00] 3
000ab0 5
[00ba00] 3
00ba00 3
000ab0 5
[00ba00] 3
00ba00 3
00ba00 3
ab0000] 2

v5
000a00
000a00
000a00
000a00
000a00
000a00
000a00
000a00
000a00
000a00
a00000

J(C) intervals for [a, abbabb]
The set I(C) only changes for the last chain:
Chain Id
v0
6[-5-]4[-]3-2 abbabb

l1
6

v1
l2
[abbab0 5

v2
l3
abba00] 4

v3
l4
[abb000] 3

v4
l5
ab0000 2

v5
a00000

Table 4: Comparing I(C), J(C) for the maximal chains of [a, abbabb].

The rest of the paper is organized as follows. In Section 2, we use Theorem 3 to reprove
Bj¨rner’s formula in Theorem 1. We also give a simple proof of his characterization of the
o
topology of posets ordered by factor order using discrete Morse theory. In Section 3, we will
consider generalized factor order on the integers, meaning we will allow a partial ordering of the
letters to be taken into account. Section 4 considers generalized factor order on rooted forests,
allowing us to clearly show that the formula obtained in Section 3 for the M¨bius of function of
o
generalized factor on the integers is a generalization of Bj¨rner’s formula. This is not obvious
o
and in fact two independent proofs are needed to establish the connection. Section 5 discusses
open problems related to this work.

13

Chapter 2
Ordinary Factor Order
Let A be any set. Partially order A∗ using ordinary factor order. To get a sense of the
structure of the poset A∗ , we first consider the covering relations in this poset.
Lemma 4. A word w = w(1) . . . w(n) in A∗ can only cover the words w(2) . . . w(n) and
w(1) . . . w(n − 1). These two words are distinct unless w is flat, in which case they are equal
and flat.
Proof. Note w covers words of length |w| − 1. Since the letters of a factor of w must appear consecutively in w, the longest proper suffix w(2) . . . w(n) and the longest proper prefix
w(1) . . . w(n − 1) are the only two words w covers. Should these two words be equal, we have
w(1) = w(2), w(2) = w(3), . . ., and w(n − 1) = w(n) so that w(1) = w(2) = . . . = w(n). This
implies that w is flat when it covers a single word.
We will now formalize some of the concepts introduced informally in the introduction. Suppose there is an element 0 ∈ A. A word η ∈ (A ∪ 0)∗ is an expansion of u ∈ A∗ if η ∈ 0∗ u0∗ ,
/
where adjacency denotes concatenation of words and letters. An embedding of u into w is an
expansion η of u with length |w| such that for all i, either η(i) = w(i) or η(i) = 0. In the latter
case, we say w(i) is reduced to 0.
Note that the words appearing in Tables 2 through 4 are actually the embeddings of the
words vi . For example, we note that bb000 is the prefix embedding of bb into bbabb, while 000bb
is the suffix embedding.
14

ln−1
l1
l2
ln
Let [u, w] be an interval in A∗ . Let w = v0 → v1 → . . . → vn−1 → vn = u be a maximal
chain in [u, w], where the li are defined by the corresponding sequence of embeddings of vi into
w, ηvi , in the sense that
ηvi (li ) = 0 and ηvi (j) = ηvi−1 (j) when j = li .
In the case where vi−1 is flat, we require li to be the smaller of the two possible values. Note
that this gives each maximal chain its own unique sequence l1 . . . ln which we can use to identify
it. We call this sequence a maximal chain’s chain id. By lexicographically ordering these chain
ids, we produce a poset lexicographic order on the maximal chains of [u, w]. This is the order
we will use to find the MSIs of the maximal chains C, and ultimately the sets J(C) which will
allow us to apply Theorem 3. Examples of this ordering were given in Tables 2 through 4.
To facilitate the exposition, we make the following definitions. A descent in a maximal chain
is a word vi where li > li+1 . We say vi is a strong descent if li > li+1 + 1, and a weak descent
if li = li+1 + 1. An ascent in a maximal chain is a word vi where li < li+1 . In Table 2, the
chain 5 − 4 − 1 − 3 has v1 = bbab as a weak descent, v2 = bba as a strong descent, and v3 = ba
as an ascent.
ln−1
l2
l1
ln
Lemma 5. Let C : v0 → v1 → . . . → vn−1 → vn be a maximal chain in [u, w]. If vi is a
strong descent, then vi is an MSI in C.

Proof. Suppose vi+1 is not flat. Since li − li+1 > 1, we know that vi−1 = w(li+1 )vi+1 w(li )
and vi = w(li+1 )vi+1 . Therefore, if u = vi+1 w(li ), then
li−1
li+1 li
li+2
l1
l2
ln
C = v0 → . . . → vi−2 → vi−1 → u → vi+1 → . . . → vn
15

is a lexicographically earlier chain than C. Hence, vi is a skipped interval in C. Since vi is an
interval consisting of a single element, vi is an MSI.
If vi+1 is flat and vi is as well, the above argument still applies. If vi+1 is flat, but vi is
not, then u = vi+1 w(li ) must be a flat word. So li cannot be reduced in u. However, the chain
li−1
li+1 li+2
li+3
l1
l2
ln
l +1
D = v0 → . . . → vi−2 → vi−1 → u → vi+1 → . . . → vn−1 n
→ vn

is a lexicographically earlier chain than C because each vj for j > i is flat. Hence, vi is an MSI
in this case as well.
Comparing this result in Tables 3 and 4 shows that it accounts for a small proportion of the
MSIs in ordinary factor order. The next result, however, gives a great deal of information about
the critical chains of ordinary factor order.
ln−1
l1
l2
ln
Lemma 6. Let C : v0 → v1 → . . . → vn−1 → vn be a maximal chain in [u, w]. If vi is an
ascent, then it is not contained in any MSI.
Proof. We will prove this lemma by contradiction. Suppose C[vr , vs ] is an MSI that contains
vi . Notice that vi may only be preceded by ascents in this interval because if there are descents,
the last one that occurs before vi would be a strong descent. By Lemma 5, this would be an
MSI, contradicting the minimality of C[vr , vs ]. Thus, it suffices to derive a contradiction for
vi = vr , the first ascent in the interval C[vr , vs ].
Since C[vr , vs ] is an MSI of C[w, u] if and only if it is an MSI of C[vr−1 , vs+1 ], it suffices to
consider the case r = 1. However, if r = 1 then v1 being an ascent forces l1 = 1. This implies
v1 appears in all chains preceding C. Therefore, vr can be removed from any skipped interval
in which it appears and that interval will still be skipped, contradicting the fact that C[vr , vs ]
16

is minimal.
Notice that Lemma 6 implies that all MSIs of a chain C consist entirely of descents. Thus,
only the lexicographically last chain in an interval can possibly be critical. The next lemma
covers the two basic cases of MSIs in a chain C. We have already encountered the first case,
while the second case is new.
Lemma 7. Suppose w is not flat and |w| ≥ 2:
1. There are two maximal chains in the interval [i(w), w], and if C is the second chain, then
it has a unique MSI, C(w, i(w)).
2. If o(w) < i(w), there are two maximal chains in the interval [o(w), w], and if C is the
second chain, then it has a unique MSI, C(w, o(w)).
Proof. The first case follows from Lemma 5. For the second case, once we remove the first or
last element, there is only one copy of o(w) left in w. Therefore, there are two maximal chains
in the interval [o(w), w]: the first chain, which ends at the suffix embedding, and the last chain,
which ends at the prefix embedding. Since these two chains share only o(w) and w in common,
C(w, o(w)) is an MSI, completing the proof.
We can illustrate this lemma using the intervals [aa, baab] and [b, baab]. Note the inner word
of baab is aa, so that the maximal chains of [aa, baab] are baab − aab − aa and baab − baa − aa,
giving C(baab, aa) as an MSI in the second chain. The outer word of baab is b, so that the
maximal chains of [b, baab] are baab − aab − ab − b and baab − baa − ba − b, giving C(baab, b) as
an MSI in the second chain.
There is another way to think about these two types of MSIs that will prove useful moving
forward. In the first type, the embedding of i(w) in the critical chain and first chain are the same
17

when i(w) is not flat. In the second type, the embeddings of o(w) in the critical chain and the
first chain are different. Notice that if both i(w) and o(w) are flat, then w is flat, o(w) < i(w),
and there is a unique maximal chain in every non-empty interval [u, w]. Thus, there can be no
overlap between these two types of MSI. We will see this observation about same and different
embeddings provides a very useful way of determining how MSIs arise, even though it does not
apply to MSIs that end at flat words.
Proposition 8 generalizes Lemma 7(2), and the theorem that follows shows that we have
identified all cases of MSIs. It will be convenient to adopt the convention that a sequence
li+1 consisting of a single label is not decreasing, corresponding to the fact that the interval
C(vi , vi+1 ) is empty and so not an MSI.
ln−1
l1
l2
ln
Proposition 8. Let C : w = v0 → v1 → . . . → vn−1 → vn = u be a maximal chain in
the interval [u, w]. Suppose there are i and j such that vj = o(vi ) < i(vi ), and such that the
sequence li+1 , . . . , lj is decreasing. Then C(vi , vj ) is an MSI in C.
Proof. Since the sequence li+1 , . . . , lj is decreasing, vi can not be flat and j ≥ i + 2. So
Lemma 7(2) implies that C(vi , vj ) is an MSI in the subchain of C that is its intersection with
[vj , vi ]. So there is a lexicographically earlier maximal chain D in [vj , vi ]. Thus, the chain C
formed by replacing the subchain C[vi , vj ] in C with D yields C − C(vi , vj ) ⊂ C . Therefore,
C(vi , vj ) is a skipped interval of C.
To see that it must also be an MSI, note that o(vi ) < i(vi ) so that [vj , vi ] has only two
maximal chains and they intersect only at vi and vj . So the same must be true of any maximal
chain in [u, w] containing vi and vj . This forces minimality.
Theorem 9. The interval C(vi , vj ) is an MSI of a maximal chain C of [u, w] if and only if
C(vi , vj ) = vi+1 and vi+1 is a strong descent, or vj = o(vi ) < i(vi ), where the sequence
18

li+1 , . . . , lj is decreasing.

Proof. The reverse implication follows from Lemma 5 and Proposition 8.
Suppose C(vi , vj ) is an MSI in C. Note by Lemma 6 the sequence li+1 , . . . , lj is a decreasing
sequence. If vi+1 is a strong descent, then vi+1 is an MSI by Lemma 5. This implies C(vi , vj ) =
vi+1 . If vi+1 is not a strong descent then, by containment minimality, none of the descents are
strong descents. Also, our sequence is decreasing, so we conclude that vi = vj w(lj ) . . . w(li+1 ).
Thus, vj is the prefix of the word vi .
In order for C(vi , vj ) to be an MSI, there must be at least two embeddings of vj into vi ,
else no maximal chain can differ from C on the interval [vi , vj ]. Let k be the largest index
so that vk contains exactly two copies of vj . Then vk+1 contains only one embedding of vj ,
implying that vj is a suffix of vk . By the previous paragraph, vj is also a prefix of vk . Thus
o(vk ) = vj because if a word longer than vj was o(vk ), vk+1 would have more than one copy
of vj . Similarly, o(vk ) < i(vk ). So by Proposition 8, C(vk , vj ) is an MSI of C. Thus, by
containment minimality, it must be the case that k = i.

Theorem 9 completes the characterization of the MSIs in an interval [u, w] in factor order.
Notice the definitions of the inner and outer word, which Bj¨rner used to state his formula,
o
naturally arise when determining the MSIs. Also, the inequality u ≤ o(w) ≤ i(w) is forced upon
us by the poset lexicographic ordering of the maximal chains.
We are now ready to prove Bj¨rner’s formula using discrete Morse theory. We have broken
o
the proof up into several cases to make it easier to follow.
19

Theorem 1 ([4]). In ordinary factor order, if u ≤ w then

µ(u, w) =




µ(u, o(w))








1



(−1)|w|−|u|








0


if |w| − |u| > 2 and u ≤ o(w) ≤ i(w),
if |w| − |u| = 2, w is not flat, and u = o(w) or u = i(w),
if |w| − |u| < 2,
otherwise.

Proof. Let [u, w] be an interval in ordinary factor order. Suppose first that |w| − |u| < 2. Then
u = w or |u| = |w| − 1. By the definition of the M¨bius function, we have µ(u, w) = 1 in
o
the first case and µ(u, w) = −1 in the second case. Thus, the formula for µ(u, w) holds when
|w| − |u| < 2.
Now suppose |w| − |u| = 2. Then by the M¨bius recursion µ(u, w) = 0 if there is one element
o
in the interval (u, w) and µ(u, w) = 1 when there are 2 elements in the interval (u, w). Since
w covers at most two elements, these are the only possibilities. If w is flat, then µ(u, w) = 0
since (u, w) contains a single element. If w is not flat and u = i(w), then removing either the
first or last letter of w gives us an element in (u, w), implying µ(u, w) = 1. If w is not flat and
u = o(w), then removing either the first two letters or last two letters of w gives us u. Thus,
(u, w) has 2 elements implying µ(u, w) = 1. If the above cases do not hold, then u is either a
prefix or a suffix of w, but not both. In these cases, (u, w) has 1 element implying µ(u, w) = 0.
Thus, the formula for µ(u, w) holds when |w| − |u| = 2.
We now turn to the case |w| − |u| > 2. We will use Theorem 3 to calculate µ(u, w) from the
critical chains in [u, w]. By Lemma 6, the chain id of a critical chain must be decreasing. Since
a strong descent is followed by an ascent unless it is the last element in a chain, all the descents
20

must be weak descents except possibly the last one. Also, the only maximal chain in [u, w] that
could be critical is the one that is lexicographically last. Call this chain C.
Suppose first that u ≤ o(w)

i(w). We need to show that o(w) is an element in the chain

C. Let k = |w| − |o(w)|. Since vk = o(w) is not contained in i(w), the word o(w)w(k + 1) cannot
be flat even if o(w) is flat. This observation, along with the fact that u ≤ o(w), allows us to
conclude that |w|, |w| − 1, . . . , |w| − (k − 1) is a valid beginning for the chain id of a maximal
chain D. Notice that each of these entries is the largest possible entry that does not already
appear in the sequence. Thus, any chain whose chain id differs from the chain id of D in the
first k entries is lexicographically earlier than D. So in the chain C, l1 = |w|, l2 = |w| − 1,. . .,
lk = |w| − (k − 1), and vk = o(w).
If u = o(w)

i(w), the previous paragraph implies that the sequence l1 , . . . , lk is decreasing.

Thus, Theorem 9 implies C(w, o(w)) is the only interval in J(C). So by Theorem 3, µ(u, w) = 1.
Of course, in this case µ(u, o(w)) = µ(u, u) = 1 as well, so the formula holds.
Next we consider u < o(w)

i(w). Since lk was the largest possible entry remaining,

lk+1 < lk , implying that o(w) is a descent. Let C be the restriction of C to the interval
[u, o(w)]. We will show that #J(C) = 2 + #J(C ), allowing us to apply Theorem 3 to complete
the case u ≤ o(w)

i(w). Since the sequence l1 , . . . , lk is decreasing, Theorem 9 implies

C(w, o(w)) is the first interval in J(C). We claim o(w) is the second interval in J(C). If o(w) is a
strong descent, this follows immediately. If o(w) is a weak descent, vk+1 = w(1)w(2) . . . w(|w|−
k − 1) < o(w), implying there are at least two copies of vk+1 contained in w. Let j be the
the largest value such that vj contains two copies of vk+1 . Since in this case v1 , . . . , vj are
weak descents, vk+1

i(vj ) because the two copies of vk+1 in vj must be the prefix and

suffix embeddings. Furthermore, o(vj ) = vk+1 because the prefix with one additional letter,
21

o(w), appears only once in vj . Since the sequence lj+1 , . . . , lk+1 is decreasing, Theorem 9
implies C(vj , vk+1 ) is a skipped interval in C. By the process of constructing J(C) from I(C),
o(w) = C(vj , vk+1 ) − C(v0 , vk ) is the second MSI in J(C), proving the claim. Since o(w) is an
MSI consisting of one element, all the remaining intervals in J(C) are contained in the interval
(u, o(w)). Therefore, J(C) = J(C ) ∪ {C(w, o(w)), o(w)} and #J(C) = 2 + #J(C ). So by
Theorem 3, µ(u, w) = µ(u, o(w)), proving the formula for |w| − |u| > 2 and u ≤ o(w)
It remains to consider what happens when |w| − |u| > 2 and u ≤ o(w)

i(w).

i(w) does not hold.

To show µ(u, w) = 0, we proceed by contradiction. If µ(u, w) = 0 then, by Theorem 3, J(C)
must cover C. This implies that J1 = C(v0 , vj ) is an MSI for some vj . Recall that Theorem 9
gives two possibilities for MSIs. If J1 = v1 and v1 is a strong descent, then since |w| − |u| > 2,
v2 is an ascent. This contradicts the fact that C has a decreasing chain id. Alternatively, we
must have vj = o(w)

i(w). However, since vj ≥ u, u ≤ o(w)

i(w), contradicting our

assumption that this inequality does not hold. So µ(u, w) = 0, completing the proof.
By reproving Bj¨rner’s formula using this technique, it is easy to verify Bj¨rner’s description
o
o
of the homotopy type of a poset ordered by factor order.
Theorem 10. Let [u, w] be an interval in A∗ . Then ∆(u, w) is homotopic to a sphere or is
contractible
Proof. By Forman’s fundamental theorem of discrete Morse Theory [5], a simplicial complex
with a discrete Morse function is homotopy equivalent to a CW complex with exactly one cell of
dimension d for each critical simplex of dimension d (as well as a dimension 0 cell). By Babson
and Hersh’s theorem for poset lexicographic orders (Theorem 3 and [1]), ∆(u, w) has a discrete
Morse function in which a maximal chain is critical (contributes a critical simplex) if and only
if J(C) covers C.
22

Thus, if [u, w] has no critical chains, it is homotopy equivalent to a CW complex with only
the 0-cell. By Lemma 6, a critical chain must have a decreasing chain id, which means only
the lexicographically last chain can be critical. So there can be at most one critical chain. This
gives us a CW complex with a 0-cell and one other cell, which by Theorem 3 has dimension
#J(C) − 1. The unique way to attach this cell to the 0 cell is through a map which is constant
on the boundary, resulting in a sphere of dimension #J(C) − 1.
As a final note on the homotopy type, notice that a critical chain contains at most one MSI
caused by a strong descent in J(C). Thus, the dimension of the sphere grows larger as the
number of recursive calls to the formula (because of outerwords) increases. So if A = {a, b},
u = a, and w is an alternating word of a’s and b’s with |w| = n > 2, the sphere has dimension
n − 3.

23

Chapter 3
Generalized Factor Order on P
Let P be a partially ordered set. Partially order P ∗ using generalized factor order, which
is the partial order on P ∗ defined by letting u ≤ w if w contains a subsequence w(i + 1)w(i +
2) . . . w(i + n) such that u(j) ≤ w(i + j) in P for 1 ≤ j ≤ n = |u|. If u ≤ w, we will again say
that u is a factor of w. In this section, we will consider generalized factor order on the positive
integers P.
In Figure 3 is the Hasse diagram of the interval [121, 1221], ordered by generalized factor
order on P∗ . To see that 121 < 1221, let w = 1221 and note that 1 ≤ w(1), 2 ≤ w(2), and
1 ≤ w(3). In fact, 121 appears twice in 1221 because 1 ≤ w(2), 2 ≤ w(3), and 1 ≤ w(4). This
interval will useful in illustrating some of the ideas in this section. The M¨bius values are listed
o
for convenience - notice there is a M¨bius value outside of the set {−1, 0, 1}.
o
Although we now have two partial orders to work with, the use of inequalities will never be
ambiguous because the partial order induced by generalized factor order on words of one letter
is the same as the order in P . Notice that when P is an antichain, generalized factor order and
ordinary factor order are the same partial order.
Our definition of length for ordinary factor order on A∗ can be used in the context of
generalized factor order on P∗ . Similarly, the concept of an expansion of a word in (A ∪ 0)∗ can
be used for words in (P ∪ 0)∗ . An embedding of a word u into w is an expansion η of u satisfying
η ≤ w for generalized factor order on (P ∪ 0)∗ . Thus, 0121 and 1210 are embeddings of 121 into
1221.
24

1221
3
221
−1

1121
−1

1211
−1

122
−1

121
1
Figure 3: The interval [121, 1221]. The M¨bius value µ(121, v) is given below of each word v.
o

A word is flat in P∗ if it is a sequence of 1’s. This is a natural refinement of the definition from
the antichain case, as in that context every element is minimal, while in P only 1 is minimal. As
in the previous section, we consider the covering relations in P∗ to get a sense of the structure of
this poset. This proof of this lemma is similar to that of Lemma 4. Reducing a letter w(i) > 1
means we are replacing it with w(i) − 1. To be precise, reducing a letter w(i) = 1 means
removing it when considering words in P∗ , or replacing it with 0 when considering embeddings
in (P ∪ 0)∗ .
Lemma 11. A word w = w(1) . . . w(n) in P∗ can cover up to n words, each formed by reducing a
letter in w by 1. Reducing the letters w(1) and w(n) will always produce a factor, while reducing
w(i) for 1 < i < n can only produce a new factor if w(i) ≥ 2. These words are distinct unless
w is flat, in which case w only covers one word which is flat.
Since a larger example will also be useful in illustrating the ideas in this section, the interval
[2, 2212] is found in Figure 4.
It should be noted that whenever a word begins or ends with a sequence of 1’s, we could
produce the same factor by reducing any 1 from the sequence. However, since such a word is
always a prefix or suffix, to assure our embeddings respect generalized factor order on (P∪0)∗ , 1’s
can only be reduced if they are at the beginning or end of a word. If a word is flat, our convention
25

2212
−1
1212
−1

2112
1

212
1

1112
0

112
0

1211
0

2211
0
2111
0

221
−1

211
0

121
1

22
1

12
−1

21
−1
2
1

Figure 4: The interval [2, 2212]. The M¨bius value µ(2, v) is given below of each word v.
o

is that only the first 1 can be reduced. For ease, we will say the letter w(i) is reducible in the
word w if w(i) > 1 or w(i) = 1 and its position i is consistent with the preceding discussion.
Similarly, we say the letter η(i) in the embedding of a word v into w is reducible if η(i) > 1, if
η(i) = 1 is the first non-zero letter, or if v is not flat and η(i) = 1 is the last non-zero letter.
For example, the word 1211, found in the center of Figure 4, has three reducible positions:
1, 2 and 4. Notice reducing position 2 results in the word 1111, which is not in the interval
[2, 2212]. Also, in a flat word, such as 1111, only the first position is reducible. Similarly, if a
flat word is given as an embedding, such as 0110 in 2212, then only the first non-zero position,
in this case position 2, is reducible.
ln−1
l1
l2
ln
Let [u, w] be an interval in P∗ . Let C : w = v0 → v1 → . . . → vn−1 → vn = u be a
maximal chain in [u, w], where the li are defined by the corresponding sequence of embeddings
ηvi in the sense that
ηvi (li ) = ηvi−1 (li ) − 1 and ηvi (j) = ηvi−1 (j) when j = li .
26

This gives each maximal chain C a chain id l1 . . . ln . By lexicographically ordering these chain
ids, we produce a poset lexicographic order on the maximal chains of [u, w]. We will use this
order to find the MSIs of the maximal chains. Examples of a poset lexicographic order were
given in Section 1, Tables 1 and 4. Specific examples for this section will be given later in
Tables 5 and 6.
Suppose |u| = |w|. Let mi = w(i) − u(i). By Lemma 11, every permutation of the multiset
Muw = {1m1 , 2m2 , . . .} is the chain id for a maximal chain in [u, w]. Since there is a single
embedding of u into w, these permutations account for every maximal chain in [u, w]. This
implies the same-length case is really a direct product of chains. If [n] is the poset consisting of
the integers 1, . . . , n, partially ordered by size, a direct product of chains is the well-known poset
defined by P = [n1 ] × [n2 ] × . . . × [nm ], in which (i1 , i2 , . . . , im ) ≤ (j1 , j2 , . . . , jm ) if ik ≤ jk
for all 1 ≤ k ≤ m. We record some relevant results about this poset here for later use. Recall
that the rank function of any poset P in which every maximal chain has the same length is a
map ρ from the elements of P to the non-negative integers defined by ρ(x) = 0 if x is minimal,
and ρ(y) = ρ(x) + 1 if y covers x.
ln−1
l1
l2
ln
Proposition 12. If [u, w] ⊂ P∗ with |u| = |w| and C : w = v0 → v1 → . . . → vn−1 → vn =
u is a maximal chain in [u, w], then each descent vi is an MSI of C and this accounts for all
MSIs of C.

Corollary 13. Let [u, w] ⊂ P∗ with |u| = |w|. Then

µ(u, w) =




(−1)ρ(u,w)


if w(i) − u(i) ≤ 1 for all 1 ≤ i ≤ |w|,



0


otherwise,
27

where ρ denotes the rank function in P∗ and ρ(u, w) = ρ(w) − ρ(u).
ln−1
l1
l2
ln
Corollary 14. Let [u, w] ⊂ P∗ and C : w = v0 → v1 → . . . → vn−1 → vn = u be a maximal
chain in [u, w]. If |vi | = |vj | and vk is a descent with i < k < j, then vk is an MSI in C.
ln−1
l1
l2
ln
Let C : w = v0 → v1 → . . . → vn−1 → vn = u be a maximal chain in [u, w]. If a 1 is
reduced in a word vi , then ηvi (li+1 ) must be reducible, implying that li+1 corresponds to the
first or last non-zero letter in the embedding ηvi . The only other restrictions on reducibility
occur when a word is flat. Therefore, we can determine precisely which sequences correspond
to chain ids by considering what conditions imply the letters ηvi (li+1 ) are reducible.
Let η be an embedding of u into w. Let mi = w(i) − η(i). Let f denote the position of the
first non-zero letter in the embedding η, and

denote the position of the last non-zero letter in

the embedding η. We say a permutation of the multiset Mη = {1m1 , 2m2 , . . .} is admissible
if the last i appears before the last i + 1 for all 1 ≤ i ≤ f − 2 and the last j before the last
j − 1 for all + 2 ≤ j ≤ |w|. An admissible permutation is strongly admissible if the last + 1
appears before either one value from the set {f, f + 1, . . . , }, or 2 copies of a value from the set
{1, . . . , f − 1}.
For an example of an admissible permutation, we consider the embedding η = 0200 in
2212. Here, Mη = {12 , 31 , 42 }, and f =

= 2. So as long as the 3 appears after the last

4, as in the sequence 1 − 4 − 4 − 1 − 3, we get an admissible permutation. For an example
of a strongly admissible permutation, we consider the embedding η = 00110 in 22122. Here,
Mη = {12 , 22 , 41 , 52 }, f = 3, and = 4. So we need the last 2 to occur after the last 1, and the
last 5 to appear before either the last 4, two 1’s, or two 2’s. Examples include 2−4−5−5−1−1−2
and 1 − 1 − 2 − 2 − 5 − 5 − 4.
Proposition 15. Let η be an embedding of u in w, mi = w(i)−η(i), and Mη = {1m1 , 2m2 , . . .}.
28

If u is not flat, then a sequence of numbers is the chain id for a maximal chain in [u, w]
ending at η if and only if it is an admissible permutation of the multiset Mη .
If u is flat, then a sequence of numbers is the chain id for a maximal chain in [u, w] ending
at η if and only if it is a strongly admissible permutation of the multiset Mη .
Proof. For a maximal chain in the interval [u, w] to finish at the embedding η, its chain id must
be a permutation of Mη . The sequence l1 , . . . , ln is a chain id in [u, w] if and only if every word
in the corresponding sequence v1 , . . . vn is a factor of w that contains u as a factor.
If vi is not flat, 1’s can only be reduced at the beginning or end of the word. Thus, when
u is not flat, each vi will be a factor of w that contains u in the embedding corresponding to
η if and only if the positions in η smaller than f are reduced to 0 from left to right, and the
positions greater than are reduced to 0 from right to left. The permutations in Mη that satisfy
this requirement are the admissible permutations.
If vi is flat, only the first position of the word can be reduced. Thus, when u is flat, each
vi will be a factor of w that contains u in the embedding corresponding to η if and only if the
positions in η smaller than f are reduced to 0 from left to right, the positions greater than are
reduced to 0 from right to left, and all positions greater than are reduced to 0 before the last 2
in the word is reduced. The permutations in Mη that satisfy this requirement are the strongly
admissible permutations.
Now that we know which permutations of a chain id produce maximal chains, let’s take a
look at the maximal chains in [121, 1221] and [2, 2212].
In [121, 1221], whose maximal chains are given in Table 5, descents vi satisfying li+1 = li +1
are MSIs. Also, there is an MSI containing an ascent. So this example highlights some of the
differences between the case of P∗ and that of an antichain.
29

Chain Id
1-2
2[-]1
3[-]4
4[-]3
Table 5: The MSIs of

v0
l1
v1
l2
1221 1 0221 2
1221 2 [1121] 1
1221 3 [1211] 4
1221 4 [1220] 3
the maximal chains of

v2
0121
0121
1210
1210
[121, 1221] in P∗ .

In [2, 2212], whose maximal chains are given in Table 6, we see that every descent that does
not remove two 1’s from the back of a word consecutively is an MSI. Furthermore, for every
MSI C(vi , vj ) of length greater than 1, the embedding of vj into vi is not found in any previous
chain. So viewed from the right perspective, this example highlights some similarities between
the case of P∗ and that of an antichain.

As in Section 2, we begin our investigation of the MSIs by determining precisely when a
descent corresponds to an MSI. Suppose vi is a descent of a chain C. Notice that whenever
interchanging li+1 and li in the label sequence of C produces another maximal chain in [u, w],
the new chain is lexicographically earlier than C. This implies vi is an MSI of C. We will invoke
this line of reasoning by saying “li+1 and li can be interchanged.”

To maintain consistency with Section 2, we will say a descent vi is a strong descent if
vi−1 = vi+1 11 and we will say vi is a weak descent if vi−1 = vi+1 11.
30

I(C) for [2, 2212]
Chain Id
1-1-2-2-3
1-1-4[-4-]3
1-2[-]1-2-3
1-4[-]1-4-3
1-4-4[-]1-3
1-4[-4-]3[-]1
2[-]1-1-2-3
2[-4[-]4-3-]2
4[-]1-1-4-3
4[-]1-4[-]1-3
4[-]1-4-3[-]1
4[-]2[-]4-3-2
4-4[-]1-1-3
4-4[-]1-3[-]1
4-4[-]2[-]3-2
4-4-3[-]1-1
4-4-3[-]2[-]2

v0
l1
2212 1
2212 1
2212 1
2212 1
2212 1
2212 1
2212 2
2212 2
2212 4
2212 4
2212 4
2212 4
2212 4
2212 4
2212 4
2212 4
2212 4

v1
l2
1212 1
1212 1
1212 2
1212 4
1212 4
1212 4
[2112] 1
[2112 4
[2211] 1
[2211] 1
[2211] 1
[2211] 2
2211 4
2211 4
2211 4
2211 4
2211 4

v2
l3
0212 2
0212 4
[1112] 1
[1211] 1
1211 4
[1211 4
1112 1
[2111] 4
1211 1
1211 4
1211 4
[2111] 4
[2210] 1
[2210] 1
[2210] 2
2210 3
2210 3

v3
0112
[0211
0112
0211
[1210]
1210]
0112
2110
0211
[1210]
1210
2110
1210
1210
[2110]
[2200]
[2200]

l4
2
4
2
4
1
3
2
3
4
1
3
3
1
3
3
1
2

v4
0012
0210]
0012
0210
0210
[1200]
0012
2100]
0210
0210
[1200]
2100
0210
[1200]
2100
1200
[2100]

l5
3
3
3
3
3
1
3
2
3
3
1
2
3
1
2
1
2

v5
0002
0200
0002
0200
0200
0200
0002
2000
0200
0200
0200
2000
0200
0200
2000
0200
2000

J(C) intervals for [a, abbabb]
The set I(C) only changes for the chain 2 − 4 − 4 − 3 − 2:
Chain Id
2[-4-]4[-3-]2

v0
l1
2212 2

v1
l2
[2112 4

v2
2111]

l3
4

v3
[2110

l4
3

v4
2100]

l5
2

v5
2000

Table 6: The MSIs of the maximal chains of [2, 2212] in P∗ .

ln−1
l1
l2
ln
Proposition 16. Suppose [u, w] ⊂ P∗ and C : w = v0 → v1 → . . . → vn−1 → vn = u is a
maximal chain in [u, w]. Suppose vi is a descent. Then vi is a length 1 MSI if and only if vi is
strong.

Proof. We will prove this proposition by considering the difference in length between vi−1 and
vi+1 .
If |vi−1 | = |vi+1 |, vi is an MSI by Corollary 14.
Suppose |vi−1 | = |vi+1 | + 1. Then either ηvi−1 (li+1 ) = 1 and li+1 corresponds to the
31

first letter of vi−1 or ηvi−1 (li ) = 1 and li corresponds to the last letter of vi−1 . In the first
case, by Proposition 15, li+1 and li can be interchanged. In the second case, when vi+1 is not
flat, Proposition 15 implies li+1 and li can be interchanged. If vi+1 is flat, ηvi−1 (li+1 ) = 2
because otherwise vi−1 would be flat and li could not correspond to the last letter of vi−1 .
Therefore, if v is a flat sequence of 1’s with length |vi−1 |, then the chain
li−1
li+1 li+2
li+3
l1
ln
l +1
D : w = v0 → . . . → vi−1 → v → vi+1 → . . . → vn−1 n
→ vn = u

is a lexicographically earlier chain than C in [u, w]. Since C − vi ⊂ D, vi is a skipped interval
of C, implying it is an MSI of C.
Suppose |vi−1 | = |vi+1 |+2. Since vi is a descent, our restrictions on reducing 1’s imply vi+1
is not flat and either vi−1 = 1vi+1 1 or vi−1 = vi+1 11. In the first case, by Proposition 15,
li+1 and li can be interchanged. In the second case, vi cannot be a length 1 MSI because there
is a unique maximal chain in the interval [vi+1 , vi−1 ].

In the proof of the above result, we showed that unless the word vi+1 is flat, all descents vi
which are MSIs have vi+1 in the same embedding into vi−1 as a previous chain. So suppose
C(vi , vj ) is an MSI of the chain C, and D < C is a chain satisfying C −C(vi , vj ) = D−D(vi , vj ).
Then if there is a chain D < C satisfying C − C(vi , vj ) = D − D(vi , vj ) such that embedding
of vj into vi in D is the same as C, we should have an MSI which is a strong descent. If every
chain D < C satisfying C − C(vi , vj ) = D − D(vi , vj ) has an embedding of vj into vi different
than C, unless vj is flat, we should have a different type of MSI.
To describe the second type of MSI in generalized factor order on P∗ , we need to develop
the notion of a “principal factor.” If |u| ≤ |w| and u(i) ≤ w(i) for 1 ≤ i ≤ |u|, we call u a
32

prefix of w. A suffix of w is defined analogously. If |u| < |w|, a prefix or suffix is proper. If u
is both a proper prefix and a proper suffix of w, we say it is an outer factor of w. To simplify
the language, we will call an outer factor of w not contained in a longer outer factor a maximal
outer factor of w.
Using these definitions, we see that 21 is a prefix of 2212, 11 is a suffix of 2212, and that 211
and 111 are maximal outer factors of 2212.
From this point forward, if u is a prefix of w, we will often be dealing with the corresponding
embedding. If this is the case, will abuse notation and write u(i) = 0 in place of introducing
η and writing η(i) = 0. As an example, if u = 22 and w = 2212, we may write w(3) > u(3),
assuming the third position of u is 0.
Let p be a maximal outer factor of w. Suppose p is not flat. Then the principal index i of
p in w is the smallest index such that w(i) > p(i) and w(i) is reducible. We say p is a principal
factor of w if the word produced by reducing w(i) by 1 no longer contains p as a suffix.
Intuitively, the principal index i of an outer factor p is the first position of w that can be
reduced without removing the prefix embedding of p. The factor becomes a principal factor if
reducing i removes the suffix embedding of p from w. Notice the principal index of a principal
factor satisfies i > 1. Also, since p is not flat and a suffix, w(i) > 1 because the letters in the
suffix embedding of p greater than 1 necessarily occur later in w than the corresponding letters
in the prefix embedding of p.
For our first examples, we consider the principal factors in the intervals [121, 1221] and
[2, 2212] given in Tables 5 and 6. Note 121 is a prefix of 1221, and it’s principal index is 3. Our
results below will show the MSI in the chain 3 − 4 results from the fact that 121 is a principal
factor of 1221. For the second example, the only principal factor of 2212 is 211, as the flat
33

maximal outer factor 111 is excluded from the definition of a principal factor. As for the other
words in the interval [2, 2212], 1212 has 12 as a principal factor, 2112 has 2 as a principal factor,
2211 has 211 as a principal factor, 212 has 2 as a principal factor, and 221 has 21 as a principal
factor. We point out that when considering the entire set of maximal chains of [2, 2212], each
of these principal factors immediately follows exactly one MSI not caused by a strong descent.
Some additional examples may help to further clarify the definition. The principal factors
of 12222 are 1211, 1212, 1221, and 1222. The principal factors of 33133 are 3111, 3112, 3113
and 33. The words 3121 and 11211 have no principal factors.
It is important to note that a principal factor has exactly two embeddings in w. If there
were a third embedding of a principal factor p, we could extend it by a sequence of 1’s to create
a suffix of w. This new suffix would also be a prefix since 1 is the minimum of P, implying that
p would be contained in a longer outer factor.
Using principal factors, we can identify the second type of MSI in generalized factor order
on P.
i
Proposition 17. Suppose u is a principal factor of w with principal index i. Let C : w = v0 →
ln−1
l2
ln
v1 → . . . → vn−1 → vn = u be the lexicographically first chain in [u, w] with l1 = i. Then
C(u, w) is an MSI of C.
Proof. From the definition of principal factor, we conclude the word v1 contains only the prefix
embedding of u. By the definition of outer factor, w contains two embeddings of u, the prefix
embedding and the suffix embedding. So by Proposition 15, there is a maximal chain in [u, w]
with a chain id beginning with 1. Since the principal index i of u is greater than 1, there exist
chains that are lexicographically earlier than C.
Let C be an arbitrary maximal chain that is lexicographically earlier than C. Then l1 < i
34

because C is the lexicographically first chain in [u, w] with l1 = i. From the definition of principal
index, we conclude that the word v1 in the chain C does not contain the prefix embedding of u.
So v1 must contain the suffix embedding of u. Furthermore, since C is the lexicographically first
chain with the prefix embedding of u, we reduce the letters at the end last, implying vn−1 = u1.
Since v1 does not contain u1, the only words common to C and C are w and u. Since C was
an arbitrary maximal chain in [u, w] with l1 < i, and C is the first maximal chain in [u, w] with
l1 = i, we conclude C(u, w) is an MSI.

Note that this proposition shows that since 121 is a principal factor of 1221, the chain in the
interval [121, 1221] with chain id 3 − 4 has C(1221, 121) as an MSI (see Table 5). Also, since
211 is a principal factor of 2212, the chain in the interval [2, 2212] with chain id 2 − 4 − 4 − 3 − 2
has C(211, 2212) as an MSI (see Table 6). As a last example, since 21 is a principal factor of
221, the chain in the interval [2, 2212] with chain id 4 − 4 − 2 − 3 − 2 has C(21, 221) as an MSI.
To complete the characterization of the MSIs, we will need a precise description of the
lexicographically first chain in an interval [u, w] that contains an embedding η of u. The chain
id of this chain, Cη , is the lexicographically first permutation of Mη that is the chain id of a
maximal chain. Using Proposition 15, we will describe the structure of Cη when u is not flat.
First, it reduces all the letters before the support of the embedding to 0 in order from left to
right. Next, it reduces all the letters in the support of the embedding down to the corresponding
u-value in order from left to right. In the third step, Cη reduces all letters beyond the support
of the embedding to 1 from left to right. Finally, once we reach the end of w, all the 1’s beyond
the support of the embedding are reduced to 0 from right to left.
For example, the first admissible chain of [121, 1221] ending at the prefix embedding has
chain id 3 − 4. The first admissible chain of [2, 2212] ending at the prefix embedding has chain
35

id 2 − 4 − 4 − 3 − 2.
If u is not flat, call Cη the first admissible chain ending at η. Recall that a sequence is
unimodal if it consists of a weakly increasing sequence followed by a weakly decreasing sequence.
So a sequence l1 . . . ln is unimodal if l1 ≤ . . . ≤ li ≥ . . . ≥ ln for some index i. This discussion
implies the following lemma.
Lemma 18. Suppose [u, w] ⊂ P∗ and η is an embedding of u into w. Let

be the index of

the largest non-zero number in η. If u is not flat, Cη has as its chain id the unique unimodal
permutation of Mη with decreasing suffix |w|, |w| − 1, . . . , + 1.
To make better use of the Lemma, we introduce the notation 1m to represent a sequence of m
1’s. For example, if considering the prefix embedding of u into w, then u1m , where m = |w|−|u|,
is the word in Cu which precedes the decreasing suffix |w|, |w| − 1, . . . , + 1.
The following Theorem completes the characterization of the MSIs.
ln−1
l1
l2
ln
Theorem 19. Suppose [u, w] ⊂ P∗ and C : w = v0 → v1 → . . . → vn−1 → vn = u is
a maximal chain in [u, w]. Then C(vi , vj ) is an MSI of C if and only if C(vi , vj ) consists of
a single strong descent, or vj is a principal factor of vi , li+1 is the principal index of vj with
respect to the embedding ηvj of vj into w, and C[vi , vj ] is the first admissible chain in [vj , vi ]
ending at the prefix-embedding of vj .
Proof. The reverse implication follows from Propositions 16 and 17.
Suppose C(vi , vj ) is an MSI of C. By the definition of a poset lexicographic order, C(vi , vj )
is an MSI of C if and only if it is an MSI of C[vi , vj ] in the interval [vj , vi ]. Thus, it suffices
to consider the case w = vi and u = vj . Corollary 14 implies that when |u| = |w|, any MSI
consists of a single descent. Proposition 16 states that if C(w, u) is an MSI and it consists of a
single descent, then w = u11.
36

To finish the proof, it suffices to consider the case when |u| < |w| and C(w, u) is an MSI
of C that does not consist of a strong descent. Our first goals are to establish that w has a
prefix embedding of u and C[w, u] is the first admissible chain ending at the prefix embedding.
Let η be the embedding of u into w at the end of the chain C. Note that any descent vk
in C is a weak descent satisfying vk−1 = vk 1 = vk+1 11 since otherwise, by Proposition 16,
C(vk−1 , vk+1 ) would be an MSI, contradicting the minimality of C(w, u). If k + 1 = n, this
forces lk+2 < lk+1 = lk − 1, implying that vk+1 is also a weak descent. By continually
applying this idea, we find that any descents contained in C(w, u) occur in a single sequence
of weak descents at the end of this interval, and the corresponding labels form a decreasing
sequence of consecutive numbers. To see η is the prefix embedding of u into w, suppose for a
contradiction that the set Mη contains a 1. Since any descents occur in a sequence at the end
of the interval, it follows that l1 = 1 or ln = 1. If ln = 1, then vn−1 is descent satisfying
u11 = vn−2 , implying u is the empty word. However, this contradicts Proposition 15 because
vn−1 is obtained by trimming a 1 from the back of a flat word. Suppose l1 = 1. Then every
chain C lexicographically earlier than C has l1 = 1 and thus contains v1 , contradicting the fact
that C(w, u) is an MSI. Therefore, η is the prefix embedding of u into w, allowing us to write
η = u. Since |u| < |w|, we must reduce position |w| by the end of the chain. Note that the
label |w| can only be followed by another |w| or the sequence of labels |w| − 1, . . . , |u| + 1, which
leads to the sequence of weak descents. It follows that C must contain the word u1m , where
m = |w| − |u|. This implies u is not flat. So by Lemma 18, C is the first admissible permutation
of Mu . Thus, we have shown C is the first admissible chain ending at the prefix-embedding of
u.

Next, we will show u is an outer factor of w by showing it is a suffix of w. Recall that
37

C is not the lexicographically first chain in [u, w] because C(w, u) is an MSI. Let C be the
lexicographically first chain in the interval [u, w]. Lemma 18 implies C contains the word
vn−1 = u1 unless it ends at the suffix embedding of u into w. However, C cannot contain
vn−1 as otherwise C − C(w, vn−1 ) ⊂ C , contradicting the assumption that C(w, u) is an MSI.
Therefore, C must end at the suffix embedding of u into w. Thus, u is an outer factor of w
which is not flat.
To establish that u is a principal factor of w, it remains to show that u is not contained in a
longer outer factor, that l1 satisfies the definition of a principal index, and that reducing w(l1 )
removes the suffix embedding.
Suppose u were contained in a longer outer factor of w. Then u would be a prefix of this
larger factor, which is a suffix of w. Therefore, there exists an outer factor v of w such that
v = u1m , where m = |v| − |u|. By Lemma 18, C must contain this word. Since C is the first
admissible chain ending at the prefix-embedding of u, C[w, v] is the first admissible chain ending
at the prefix-embedding of v. Let D be the lexicographically first chain in the interval [v, w].
Since v contains u, it is not flat. So the structure of D is determined by Lemma 18, which
implies D ends at the embedding of v into w that is farthest to the right. So D ends at the
ˆ
ˆ
suffix embedding of v into w. Let C = D[w, v] ∪ C[v, u]. Then C is a maximal chain in [u, w]
ˆ
lexicographically earlier than C. But C − C(w, v) ⊂ C, contradicting the fact that C(w, u) is
an MSI. So u is not contained in a longer outer factor of w.
Lemma 18 implies that l1 is the first index such that w(l1 ) > u(l1 ) and w(l1 ) is reducible.
Suppose v1 , the word produced by reducing w(l1 ) by 1, contains the suffix embedding of u.
Then u is an outer factor of v1 and |v1 | = |w|. By Lemma 18, C[v1 , u] is the first admissible
chain ending at the prefix-embedding of u. Since v1 also contains the suffix embedding of u,
38

Lemma 18 implies that C[v1 , u] is not the lexicographically first chain in [u, v1 ]. Let D be
ˆ
ˆ
the lexicographically first chain in the interval [u, v1 ], and C = w ∪ D. Then C is a maximal
ˆ
chain in [u, w] lexicographically earlier than C. But C − C(v1 , u) ⊂ C, contradicting the fact
that C(w, u) is an MSI. Therefore, v1 does not contain the suffix embedding of u, and we have
established that u is a principal factor of w with principal index l1 , completing the proof.
Theorem 19 shows there are precisely two types of MSIs. We will refer to the first type
by saying “an MSI caused by a strong descent,” or just by referring to a word vi as a strong
descent. We will refer to the second type by saying “an MSI caused by the principal factor pvi .”
This language implies that pvi is a principal factor of the word vi , li+1 is its principal index
with respect to the embedding ηvi of vi into w, the interval C(vi , pvi ) is an MSI in the related
chain C, and C[vi , pvi ] is the first admissible chain in [pvi , vi ] ending at the prefix embedding
of pvi .
Our next goal is to determine precisely which maximal chains are critical chains in an interval
in P∗ . Our first objective is to consider those critical chains that consist entirely of strong
descents.
Proposition 20. Suppose [u, w] ⊂ P∗ , (u, w) is non-empty, and w is not flat. Suppose η is
an embedding of u into w. Then there is a critical chain C in [u, w] ending at η that consists
entirely of (strong) descents if and only if w(i) − η(i) ≤ 1 for all i, η(2) = 0, and η(|w| − 1) = 0.
Furthermore, these conditions imply |w| − |u| ≤ 2 and that [u, w] has at most two critical chains
consisting entirely of (strong) descents.
Proof. Suppose C is a critical chain in [u, w] that ends at η and consists entirely of descents.
Then l1 > l2 > . . . > ln−1 > ln . This implies w(i) − η(i) ≤ 1 for all i as each letter can be
reduced at most once. Since 1’s may only be reduced at the beginning or end of a word, the
39

decreasing label sequence also implies η(2) = 0 since it is not possible to reduce position 1 before
position 2. To finish this implication, suppose for a contradiction that η(|w| − 1) = 0. Since
each li is distinct and the sequence is decreasing, it follows that w = v2 11 as the last letter must
be reduced to zero before the second to last can be. So by Theorem 19, the MSI containing v1
is not caused by a descent and therefore must be caused by a principal factor p(w). Since the
chain id is decreasing, the corresponding principal index l1 must be |w|. By the definition of
principal index, w(|w|) > 1. This contradicts w = v2 11, implying η(|w| − 1) = 0.
Suppose w(i) − η(i) ≤ 1 for all i, η(2) = 0, and η(|w| − 1) = 0. The first assumption implies
each entry in Mη is distinct. If u is not flat, then the decreasing and η(2) = 0 conditions imply
the two conditions in the definition of admissibility. If u is flat, having w(i) − η(i) ≤ 1 implies w
consists only of 1’s and 2’s. So the decreasing permutation of Mη is strongly admissible because
once the last 2 has been reduced to a 1, at most an initial 1 remains to be reduced since η(2) = 0.
Therefore, Proposition 15 implies that the decreasing permutation of Mη is the chain id of a
maximal chain C in [u, w]. Since each entry in the chain id is distinct, C consists entirely of
descents. Furthermore, since η(|w| − 1) = 0, w = v2 11. So no descent has the property that
vi−1 = vi+1 11 as a decreasing chain id only permits the removal of consecutive 1’s from the
end of a word at the beginning of the chain. Therefore, by Theorem 19 each is a length 1 MSI in
C, implying that J(C) covers C(w, u). Thus, C is a critical chain consisting entirely of descents
and ending at η.
To see each interval [u, w] has at most two critical chains consisting entirely of descents, note
that |u| ≥ |w| − 2 because the first and last positions in an embedding satisfying the necessary
restrictions are the only ones which can be zero. Whenever |u| = |w|, there is also only one such
embedding. If |u| = |w| − 2 there can only be one such embedding as only the first and last
40

letters of w can be reduced, implying 0u0 is the only embedding of u into w. If |u| = |w|−1, then
it is possible the prefix embedding and the suffix embedding satisfy the necessary restrictions.
Thus, there are at most two embeddings of u that satisfy the restrictions for a critical chain
consisting entirely of descents. Since there is only one weakly decreasing permutation of any set
Mη , this completes the proof.
We note the example [121, 1221] from Table 5 provides a nice illustration of this proposition,
as the critical chains whose chain ids are 2 − 1 and 4 − 3 have MSIs caused by strong descents.
As stated in the theorem, we can have at most 2 critical chains consisting entirely of strong
descents.
The remaining critical chains must contain at least one MSI caused by a principal factor. So
these chains contain a principal factor of w or a principal factor of some vi with the property that
C(w, vi+1 ) consists entirely of descents vk such that vk−1 = vk+1 11. The second possibility
is easier to work with if we consider the relationship between the principal factor of vi and w.
This is the content of the next proposition.
Proposition 21. If a critical maximal chain C in [u, w] does not consist entirely of descents,
then it contains a vi ∈ (u, w] with a principal factor pvi ≥ u such that pvi 1m is a maximal
outer factor of w for some m ≥ 0.
Proof. By Theorem 19, C contains at least one MSI caused by a principal factor. Suppose
C(vi , pvi ) is the first such MSI. If pvi is a principal factor of w, there is nothing to show. If
not, then by Theorem 19, w = v2 11 and the chain id of C decreases through li+1 . This implies
only the last letter of w can be reduced to 0 in ηvi . So vi and thus pvi are prefixes of w.
To complete the proof, it suffices to show that pvi 1m is an outer factor for some m ≥ 0
because then the theorem holds for pvi 1 , where = |v| − |pvi | and v is a maximal outer factor
41

of w containing pvi . Recall that pvi is an outer factor of vi , which is a prefix of w such that
only the last letter of w can be reduced to 0 in ηvi . Therefore, pvi or pvi 1 is an outer factor of
w so that desired statement holds for m = 0 or m = 1.
In order to have a critical chain in [u, w] involving an MSI resulting from a principal factor
pvi , pvi needs to be contained in a different MSI or pvi must equal u. By Theorem 19, pvi could
be contained in one of three types of MSI: an MSI caused by a strong descent, an overlapping
MSI caused by a principal factor, or an adjacent MSI caused by a principal factor. We will show
the last possibility cannot occur.
Proposition 22. Suppose C(vi , pvi ) is an MSI of a critical chain C caused by the principal
factor pvi . Then pvi is contained in an MSI caused by a descent or an overlapping MSI caused
by a principal factor.
Proof. Let vj+1 = pvi . Suppose for a contradiction that C(vj , pvj ) is an MSI caused by
a principal factor. Since C(vi , vj+1 ) is an MSI caused by a principal factor, Theorem 19
implies C[vi , vj+1 ] is the first admissible chain ending at the corresponding embedding. So by
Lemma 18, vj = vj+1 1. However, this implies the value at the principal index lj+1 of pvj in
vj is vj (lj+1 ) = 1. This contradicts the fact that vj (lj+1 ) > 1, as pvj was assumed to be a
principal factor of vj . So C(vj , pvj ) is not an MSI caused by a principal factor, completing the
proof.
While refining the set of MSIs I(C) to create the set J(C), we reduce any intervals remaining
in I(C) that overlap with an earlier MSI and remove any that are no longer containment minimal
after this reduction. The next proposition states that overlapping MSIs in the set I(C) of a
critical chain must come in pairs.
42

Proposition 23. An MSI of a critical chain can overlap with at most one other MSI.

Proof. Let C be maximal chain of [u, w]. Suppose C(vi , vj ), C(vi , vj ), . . . , C(vi , vj ) is
1 1
2 2
k k
a maximal sequence of three or more overlapping MSIs satisfying i1 < i2 < . . . < ik . Since
MSIs caused by strong descents always have length one, they cannot be involved in overlapping
MSIs. So by Theorem 19, each vj is a principal factor of vi , li +1 is the principal index of
vj with respect to the embedding ηvi of vi into w, and C[vj , vj ] is the first admissible
chain in [vj , vj ] ending at the prefix embedding of vj . By Lemma 18, any two consecutive
MSIs must have unimodal label sequences that overlap. Note each ηvi (li +1 ) > 1 because
li +1 corresponds to a principal index. So each label sequence must contain at least one entry
before reaching its decreasing suffix. Therefore, the overlap between two intervals must start
on the weakly increasing portion of the label sequences. Since no letters are removed before
reaching the decreasing suffix, this implies |vi | = |vi | = . . . = |vi |. So each MSI C(vi , vj )
1
2
k
includes all of the decreasing suffix of C(vi , vj ), and each MSI except the first contains all of
1 1
the decreasing suffix of C(vi , vj ).
2 2
Consider the process of refining the set of intervals I(C) to J(C). The first interval in the
sequence of overlapping intervals, C(vi , vj ), is added to J(C). Any other interval in I(C) has
1 1
its overlap with this interval removed, and any interval that is no longer containment minimal
is discarded. However, each interval C(vi , vj ) left in I(C) contains the truncated portion of
C(vi , vj ). So C[vj , vj ) is added to J(C) and the rest of the intervals are discarded. Thus,
2 2
1 2
vj is not in an interval in J(C) and C is not a critical chain.
2
We now have enough information to give a nice description of the structure of a critical
chain.

43

ln−1
l1
l2
ln
Theorem 24. Let C : w = v0 → v1 → . . . → vn−1 → vn = u be a maximal chain of [u, w].
Then C is a critical chain if and only if C(w, u) can be written as a sequence of intervals

C[vi = v1 , vi ) ∪ C[vi , vi ) ∪ . . . ∪ C[vi
, v = u)
1
2
2 3
k−1 ik

where each interval C[vi , vi
) is one of the following three types:
j j+1
1. C[vi , vi
) is an MSI caused by the strong descent vi .
j j+1
j
2. C[vi , vi
) is an MSI caused by the principal factor vi
of the word vi −1 .
j j+1
j+1
j
3. The word vi
is a principal factor of a word in C[vi
, v ) and satisfies
j+1
j−1 ij
vi
1m = vi for m = |vi | − |vi
| > 0. The value m is unique in the sense that no
j+1
j
j
j+1
other word satisfies the description of vi
for another value m.
j+1
Furthermore, type (1) intervals are followed by intervals of type (1) or (2), type (2) intervals
are followed by intervals of type (1) or (3), and type (3) intervals are followed by intervals of
type (1). Finally, only intervals of type (1) or (2) can begin the decomposition.
Proof. For the forward implication, we need to show that in a critical chain, each interval in
the set J(C) is one of the three interval types listed and the order of the intervals respects
the ordering restrictions of the proposition. By Theorem 19, each MSI is caused by a strong
descent or a principal factor. So intervals of type (1) and type (2) can occur in J(C). Next,
since Proposition 23 states that overlapping intervals must occur in pairs, we need to show that
the second interval in an overlapping pair is an interval of type (3). Let C[vi , vi
) be the
j j+1
remainder of an interval from I(C) that was reduced in J(C). From the proof of Proposition 23,
C[vi , vi
) must be the remainder of the MSI C(v, vi
) caused by the principal factor
j j+1
j+1
44

vi
, where the preceding interval C[vi
, v ) is of type (2) and |v| = |vi
|. Since 1’s
j+1
j−1 ij
j−1
in these MSIs can only be trimmed from the back, vi = vi
1m for m = |vi | − |vi
|.
j
j+1
j
j+1
To assure this is the second interval in a pair of overlapping intervals in I(C), there cannot be
another word in C[vi , u] that is a principal factor of a word in C[vi
, v ). In particular,
j
j−1 ij
this means there can be no word in C[vi , u] satisfying the previous description of vi
for
j
j+1
another value m. Therefore, C[vi , vi
) is an interval of type (3) and all intervals reduced
j j+1
from overlapping MSIs in I(C) are of this type. Thus, there are no other types of intervals
that can occur in J(C). Finally, we need to verify the ordering restrictions. Type (1) intervals
cannot be followed by intervals of type (3) because the half-open interval under consideration is
empty. Intervals of type (2) cannot be followed by type (2) intervals by Proposition 22. Type
(3) intervals cannot be followed by type (2) intervals by Proposition 22, and cannot be followed
by type (3) intervals because the value m is unique. And type (3) intervals cannot begin the
decomposition because the half-open interval under consideration does not exist. This completes
the proof of this implication.

For the backwards implication, since the given set of intervals covers C, we need to show the
interval types are always reductions of MSIs in I(C). Type (1) and type (2) intervals are MSIs
by Theorem 19. Type (3) intervals must occur after a type (2) interval by definition. Suppose
C[vi , vi
) is a type (3) interval so that the word vi
is a principal factor of a word v
j j+1
j+1
in [vi
, v ). Lemma 18 implies that the label sequence of C[vi
, v ) is unimodal. So
j−1 ij
j−1 ij
Lemma 18 also implies that v, the word which has vi
as a principal factor, occurs before
j+1
the decreasing suffix of the label sequence of C[vi
, v ]. Thus, C[v, vi
] is the first
j−1 −1 ij
j+1
admissible chain in the corresponding interval [vi
, v] with vi
in the prefix embedding.
j+1
j+1
So by Theorem 19, C(v, vi

j+1

) is the MSI in I(C) that is reduced to the interval C[vi , vi
).
j j+1
45

Furthermore, this reduced interval appears in J(C) because vi
1m = vi for a unique value
j+1
j
of m. Indeed, if m were not unique, a different reduced interval would either be contained inside
this one or have this interval contained within it; both cases contradict the fact that J(C) covers
C. Since the ordering restrictions respect Propositions 22 and 23, this completes the proof of
this implication.

In the interval [121, 1221], the critical chain with chain id 2 − 1 consists of a single type (1)
interval, C[1121, 121) = C(1221, 121) (see Table 5). In the interval [2, 2212], the critical chain
with chain id 2 − 4 − 4 − 3 − 2 consists of the type (2) interval C[2112, 211) = C(2212, 211)
followed by the type (3) interval C[211, 2), which is truncated from the MSI C(2112, 2) (see
Table 6).
Using Theorem 24, we can separate the critical chains of [u, w] into three groups based on
what happens after the first type (2) interval in the chain: critical chains with no type (2)
intervals, critical chains whose first type (2) interval is the last interval or is followed by a type
(1) interval, and critical chains whose first type (2) interval is followed by a type (3) interval.
Notice the first group is investigated in Proposition 20. So if we can find the total contribution of
all critical chains whose first interval is a given type (2) interval, we will have enough information
to write down a recursive formula for the M¨bius value.
o
Let C be a critical chain. If J(C) contains any type (2) intervals, then by Theorem 24 the
first type (2) interval in the set must either be the first interval or occur after a sequence of
type (1) intervals. Furthermore, if the first type (2) interval is followed by a type (3) interval,
Theorem 24 implies the principal factor causing the type (3) interval must be a certain prefix
of the principal factor causing the type (2) interval. So to facilitate the exposition, we need to
make several new definitions.
46

Define w \ 1m to be the word that results when m 1’s are removed from the suffix of w, or
as undefined if w ends in less than m 1’s.
Define a word v to be a base of w if v(j) = w(j) or v(j) = w(j) − 1 for all j and |v| = |w|
or |w| − 1. Define the degree of a base to be the number of indices j for which v(j) = w(j) − 1.
This way, if a word vi in a chain C is a base of w, then it is a base of degree i. When i > 0, the
language “vi is based in C” will indicate the word vi of the chain C is a base of w and the labels
l1 , . . . , li of C form a decreasing sequence. In Proposition 20, we showed that this condition
forces each word v1 , . . . , vi−1 to be a strong descent.
Suppose vi is a base of w of degree i. Let l be the index of the smallest position satisfying
vi (l) = w(l) − 1, or |w| + 1 if i = 0. We define any word pvi that is a principal factor of vi and
whose principal index takes a value less than l to be a principal factor of w of degree i. This
definition is an extension of the definition of a principal factor because a principal factor of w
satisfies the new definition for i = 0. So to maintain consistency in the language, when a degree
is not noted in the language or the notation, the assumption will be that the principal factor
has degree 0.
In the example [2, 2212] found in Table 6, the bases of 2212 of degree 1 are 1212, 2112,
and 2211. The base 2211 of admits 211 as a principal factor of degree 1, but 2112 and 1212
have principal factors with principal indices greater than the smallest position satisfying vi (l) =
w(l) − 1. Returning to an example first given after the definition of a principal factor, the degree
2 base 12211 of the word 12222 has 1211 as a principal factor, making 1211 a principal factor of
degree 2. In fact, 1211 is a principal factor of 4 bases of 12222: 12211, 12212, 12221. and 12222
itself.
Let pvi be a principal factor of w of degree i. By Theorem 24, pvi could cause the first type
47

(2) interval C(vi , pvi ) in some critical chain C because when vi is based in C, the condition on
the principal index of pvi implies vi is a strong descent. Notice pvi must be an outer factor of
w or w \ 1. The latter is a possibility when w \ 1 is defined because, by the definition of a base,
vi (|w|) could be 0. Furthermore, the proof of Proposition 21 implies pvi 1m is a maximal outer
factor of w for some m ≥ 0. Finally, pvi could be a principal factor of other bases vj of w.
Suppose pvi is a principal factor of vi . Let vi be the word that results when the letter in vi
at the principal index of pvi is reduced by 1. That is, vi (j) = vi (j) − 1 when j is the principal
index of pvi and vi (j) = vi (j) for all other indices j. Define the primary prefix x(pvi ) of a
principal factor pvi to be the factor pvi \ 1m , where m is the smallest positive integer such that
pvi \ 1m is an outer factor of vi . So if no m > 0 satisfies the restriction, the primary prefix is
undefined.
Intuitively, the primary prefix of a principal factor pvi is the longest proper prefix of pvi
that has two embeddings in vi and only differs from pvi by some number of 1’s removed from
the back. Notice the primary prefix depends on the word vi , or perhaps more intuitively, the
word vi and the principal index of pvi in vi . In the example [2, 2212], 2 is the primary prefix of
the principal factor 211 of 2212. However, in the interval [2, 2222], which contains the previous
interval as a subinterval, 21 is the primary prefix of the principal factor 211 of 2222. And in the
interval [2, 2211], the principal factor 211 does not have a primary prefix.
The following proposition asserts that the primary prefix is the only word that can cause a
type (3) interval after the type (2) interval C(vi , pvi ).
Proposition 25. Let C be a maximal chain of [u, w] and suppose C(vi , pvi ) is a type (2) interval
in the set J(C). Then C(vi , pvi ) is followed by a type (3) interval C[pvi , x) in J(C) if and only
if x is the primary prefix of pvi and x appears in C.
48

Proof. First suppose x is the primary prefix of pvi and that it appears in C. By definition, x
is a maximal outer factor of vi . Thus, it is a maximal outer factor of any word in C(vi , pvi )
of which it is an outer factor. Let vm be the last word in the interval C(vi , pvi ) that contains
x as an outer factor. We will show x is a principal factor of vm with principal index lm+1 .
Since pvi is a prefix of vm+1 , x is as well. So vm+1 no longer contains the suffix embedding
of pvi . Furthermore, since C[vi , pvi ] is the first admissible chain in [pvi , vi ] ending at the prefix
embedding of pvi , for all li+1 < k < lm+1 , either we have vm (k) = pvi (k) or we have vm (k) = 1
and pvi (k) = 0. Therefore, for all li+1 < k < lm+1 , either we have vm (k) = x(k) or we have
vm (k) = 1 and x(k) = 0. This implies C[vm , x] is the first admissible chain in [x, vm ] ending
at the prefix embedding of x and vm (lm+1 ) is the first reducible letter in vm greater than the
corresponding position in the prefix embedding of x. Thus, lm+1 satisfies the definition of a
principal index, which implies x is a principal factor of vm and C(vm , x) is an MSI of C. Since
x is a maximal outer factor of vi , and C(vi , pvi ) is a type (2) interval, no word between pvi and
x can be a principal factor of a word vk in C. Therefore, C(vm , x) is reduced to the type (3)
interval C[pvi , x) in J(C), completing the reverse implication.

Now suppose that C(vi , pvi ) is followed by a type (3) interval C[pvi , x) in the set J(C).
Then by Theorem 24, x is a principal factor of a word v in C(vi , pvi ) and x = pvi \ 1m for some
m. From the proof of Theorem 24, we know |v| = |vi | and v ≤ vi , implying x is an outer factor
of vi . By Theorem 24 part (3), it suffices to show that x is a maximal outer factor of vi . For a
contradiction, suppose x is not a maximal outer factor of vi . Then a word of the form x1k would
be a maximal outer factor of vi and by the argument in the paragraph above, a principal factor
of some word in C(vi , pvi ). Thus, C(v, x1k ) would be an MSI in I(C). This would be reduced
to the interval C[pvi , x1k ), which is contained in C[pvi , x), implying that C[pvi , x) could not
49

be in J(C). This is a contradiction. Thus, x is a maximal outer factor of vi , implying it is the
primary prefix of the word pvi .
Let µ(u, v) be the normal M¨bius function if u and v are both elements of P∗ , or zero if
o
either is undefined. Define the function ν(u, v) to be

µ(u, v \ 1i ).

ν(u, v) =
i≥0

Notice all the terms in the summation will be zero beyond the largest value i = m for which
v \ 1m is defined, or the smallest value i = m for which v \ 1m ≤ u.
We are now ready to consider the contribution of critical chains whose first type (2) interval
is a specific interval. This proof is very technical, and we have broken it up into several cases
to make it easier to follow.
Proposition 26. Suppose C(vi , pvi ) is the first type (2) interval of some critical chain C of
[u, w]. Then pvi is a principal factor of w of degree i and vi is based in C. Furthermore, the
contribution to the M¨bius value µ(u, w) of all critical chains in [u, w] that have C(vi , pvi ) as
o
the first type (2) interval is

(−1)i ν(u, pvi ) − ν(u, x(pvi )) ,

where x(pvi ) is the primary prefix of pvi .
Proof. Since C(vi , pvi ) is a type (2) interval, Theorem 24 implies pvi must be a principal factor
of vi . If i = 0, pvi is a principal factor of w of degree 0. If i = 0, then since C is a critical chain
and C(vi , pvi ) is the first type (2) interval, Theorem 24 implies vi and the words v1 , . . . , vi−1
50

which precede it must each be contained in a type (1) interval. Since v2 11 = v0 , |vi | = |w| or
|w| − 1. Also, the i labels preceding vi are distinct and form a decreasing sequence. Therefore,
vi (j) = w(j) or vi (j) = w(j) − 1. This implies vi is a base of w, which allows us to conclude vi
is based in C. Since vi is in a type (1) interval, li+1 < li , implying pvi is a principal factor of
w of degree i.

To facilitate the discussion, we will first consider the case when pvi ends with a letter other
than 1. Then pvi \ 1 is undefined, so ν(u, pvi ) = µ(u, pvi ). Note that the set J(C) must cover
the entire chain C(w, u) for C to be critical, and we already know J(C) covers C(w, pvi ) when
C(vi , pvi ) is the first type (2) interval. Furthermore, pvi does not have a primary prefix, so by
Theorem 24, C(vi , pvi ) can only be followed by an interval of type (1) in J(C). Recall from
the proof of Theorem 19 that the last label in C(vi , pvi ), lk , is the last non-zero position in
pvi 1. So lk = |pvi 1| by Lemma 18. Thus, in any critical chain containing the type (2) interval
C(vi , pvi ), lk+1 < lk . We now consider two subcases depending on whether u = pvi .
First suppose u < pvi . Since pvi does not end in a 1, it must be a strong descent. So
in any maximal chain containing C[vi , pvi ], pvi is contained in a type (1) interval. It follows
that J(C[pvi , u]) must cover C(pvi , u), whose first label corresponds to lk+1 in C. Since any
choice of label lk+1 puts pvi in a type (1) interval, the set of critical chains in [u, w] that
contain C(vi , pvi ) are in a one-to-one correspondence with the critical chains of [u, pvi ]. The
corresponding map between the sets J(C) and J(C[pvi , u]) is given by the addition or subtraction
of the i + 2 intervals v1 , . . . , vi , C(vi , pvi ), and pvi . Therefore, the number of intervals in J(C)
is i + 2 + |J(C[pvi , u])|. So by Theorem 3, the total contribution of all these chains to µ(u, w) is
(−1)i+2 µ(u, pvi ) = (−1)i µ(u, pvi ).
51

Now suppose u = pvi . The above formula follows from Theorem 3 because µ(pvi , pvi ) = 1
and there are precisely i + 1 intervals in J(C) = J(C([w, pvi ])). So in this case, µ(u, w) = (−1)i .
Since pvi does not have a primary prefix and ν(u, pvi ) = µ(u, pvi ), this completes the proof for
this case.

Now we consider the case pvi ends with a 1. If u = pvi , the argument does not change from
the one above. If u < pvi , there are two significant differences from the previous discussion.
First, while pvi is still a descent vk in any maximal chain containing C(vi , pvi ), it is possible it
could be a weak descent. The second difference is pvi could have a primary prefix, implying that
C(vi , pvi ) could be followed by a type (3) interval in a critical chain. Fortunately, because of
the required conditions on the descent pvi , C(vi , pvi ) can only be followed by a type (1) interval
if lk+1 < |pvi |, and a type (3) interval if lk+1 = |pvi |. This allows us to consider these two
cases separately.

First, suppose pvi = vk ends with a 1 and a critical chain C containing the type (2) interval
C(vi , pvi ) has lk+1 < |pvi |. Then C can only be critical if C(vi , pvi ) is followed by a type (1)
interval and C(w, vi ] consists of i type (1) intervals. So as above, it follows that C is critical if
and only if J(C[pvi , u]) covers C(pvi , u), whose first label is lk+1 in C. Since lk+1 < |pvi |, we
have a one-to-one correspondence between the critical chains of [u, w] that contain C(vi , pvi )
and the critical chains of [u, pvi ] whose first label is not |pvi |. Notice that µ(u, pvi ) could
count critical chains of [u, pvi ] whose first label is |pvi | and first word is pvi \ 1. So we must
subtract out these critical chains when calculating the contribution to the M¨bius value. Since
o
the corresponding map between the sets of critical chains is given by the addition or subtraction
of the i + 2 intervals v1 , . . . , vi , C(vi , pvi ), and pvi , it follows from Theorem 3 that the total
52

contribution of all these critical chains to µ(u, w) is

(−1)i+2 µ(u, pvi ) − O(u, pvi ) = (−1)i (µ(u, pvi ) − O(u, pvi )),

where O(u, pvi ) is the total contribution to µ(u, pvi ) of the critical chains of [u, pvi ] for which
v1 = pvi \ 1. Since |pvi | does not satisfy the definition of a principal index, Theorem 24 implies
that pvi \ 1 can only be in a critical chain of [u, pvi ] if it is in a type (1) interval. If pvi \ 12
is undefined, we are looking for all critical chains of [u, pvi \ 1]. However, if pvi \ 12 is defined,
O(u, pvi ) is the contribution of all critical chains of [u, pvi \ 1] that do not start with the values
|pvi \ 1| and |pvi \ 12 |, as this would put pvi \ 1 in a non-MSI-causing descent in [u, pvi ].
Furthermore, these critical chains contain one less interval than those of [u, pvi ] because they
do not contain the interval pvi . So we need to account for this by taking the negative of the
values of the chains in [u, pvi \ 1]. Thus,

O(u, pvi ) = − µ(u, pvi \ 1) − O(u, pvi \ 1) ,

since O(u, pvi \ 1) is the total contribution to µ(u, pvi \ 1) of those critical chains of [u, pvi \ 1]
for which v1 = pvi \ 12 . This recursive definition for O(u, pvi ) terminates when we find an for
which pvi \ 1 is undefined or pvi \ 1 < u because both of these cases imply O(u, pvi \ 1 ) = 0.
Therefore,

O(u, pvi ) = − µ(u, pvi \ 1) + µ(u, pvi \ 12 ) + . . . + µ(u, pvi \ 1 −1 ) .

This implies that when pvi = vk ends in a 1, the total contribution of all critical chains containing

53

the type (2) interval C(vi , pvi ) and satisfying lk+1 < |pvi | is
(−1)i µ(u, pvi ) + ν(u, pvi \ 1) = (−1)i ν(u, pvi ).

Our last goal is to consider the case when pvi = vk ends with a 1 and a critical chain C
containing the type (2) interval C(vi , pvi ) has lk+1 = |pvi |. In this case, the set J(C) must
contain i type (1) intervals before C(vi , pvi ), and a type (3) interval immediately following
C(vi , pvi ). By Proposition 25, the type (3) interval must be caused by the primary prefix of
pvi , x(pvi ). So the type (3) interval is C[pvi , x(pvi )). Notice that Theorem 24 implies x(pvi )
must be contained in a type (1) interval. In the previous case, note that pvi is the first word
in the interval [u, w] which is not in the intervals of J(C) required for the type (2) interval
C(vi , pvi ), and pvi must be contained in a type (1) interval. In this case, x(pvi ) is the first
word in [u, w] that is not contained in the intervals of J(C) required for the type (3) interval
C[pvi , x(pvi )), and x(pvi ) must be contained in a type (1) interval for C to be critical. Therefore,
the argument is very similar, except x(pvi ) takes the place of pvi . If u < x(pvi ), the major
difference is C is now critical if and only if J(C[x(pvi ), u]) covers C(x(pvi ), u). So the i + 3
intervals v1 , . . . , vi , C(vi , pvi ), C[pvi , x(pvi )), and x(pvi ) precede the elements of J(C[x(pvi ), u])
in the set J(C). Beyond this detail, the argument leading to (−1)i ν(u, pvi ) is the same, with
x(pvi ) taking the place of pvi . Therefore, the contribution to µ(u, w) of the critical chains of
[u, w] that contain the type (3) interval C[pvi , x(pvi )) is
(−1)i+3 ν(u, x(vi )) = (−1)i+1 ν(u, x(pvi )).

Note this formula also holds if u = x(pvi ) because then ν(u, x(pvi )) = µ(u, u) = 1 and there are
54

i + 2 intervals in J(C).
Thus, if x(pvi ) is the primary prefix of pvi , the contribution to the M¨bius value of all critical
o
chains that contain the type (2) interval C(vi , pvi ) as their first type (2) interval is
(−1)i ν(u, pvi ) − ν(u, x(pvi ))

because if x(pvi ) is not defined, ν(u, x(pvi )) = 0. This completes the proof.
Using Propositions 20 and 26, we are able to write down a formula for µ(u, w). Recall that
ρ denotes the rank function in P∗ , and ρ(u, w) = ρ(w) − ρ(u). For simplicity, let 0 ≤ t ≤ 2 be
the number of critical chains in [u, w] that consist entirely of strong descents, and define

if ρ(u, w) > 1



(−1)ρ(u,w)


d(u, w) =




t(−1)ρ(u,w)


if ρ(u, w) ≤ 1.

Theorem 27. Suppose u ≤ w in the poset P∗ . Then

µ(u, w) = d(u, w) +

(−1)i ν(u, pvi ) − ν(u, x(pvi )) ,

where the sum is over all triples vi , pvi , x(pvi ) such that pvi is a principal factor of w of degree
i with base vi and primary prefix x(pvi ).
Proof. First suppose ρ(u, w) ≤ 1. Then [u, w] cannot have any maximal chains because the
open interval is empty or undefined. So both summations contribute 0 to the M¨bius value. By
o
definition of the M¨bius value, when ρ(u, w) = 1, µ(u, w) = −1 and when ρ(u, w) = 0, u = w
o
and µ(u, u) = 1. These are the values that are defined in the formula d(u, w).
55

Now suppose ρ(u, w) > 1. If C is a critical chain of [u, w] that consists entirely of strong
descents, then J(C) consists of ρ(u, w) − 1 intervals of length 1. Therefore, by Theorem 3, C
contributes
(−1)ρ(u,w)−2 = (−1)ρ(u,w)
to the M¨bius value µ(u, w). By Proposition 20, there are 0, 1, or 2 such chains in any interval
o
[u, w], making the total contribution of all such chains

t(−1)ρ(u,w) ,

where t is the total number of these chains. This is the value in the formula for d(u, w). Thus,
by adding the contribution of all critical chains that do not consist entirely of strong descents
to d(u, w), we will get a formula for the M¨bius value.
o
If a critical chain C in [u, w] does not consist entirely of strong descents, then by Theorem 19,
C must contain an interval caused by a principal factor. By Proposition 26, the first such interval
is caused by a principal factor of some degree i. Let C(vi , pvi ) be this interval, where i is the
degree of the principal factor pvi , and consider the set S of all critical chains that contain this
interval as the first type (2) interval. Then Proposition 26 implies the contribution of the chains
in S to the M¨bius value is
o

(−1)i ν(u, pvi ) − ν(u, x(pvi )) ,

where x(pvi ) is the primary prefix of pvi . This is precisely the term that appears in the given
formula for the triple vi , pvi , x(pvi ). By Theorem 24, summing over all such triples yields
a summation which gives the contribution of all critical chains containing at least one type
56

(2) interval. Thus, the M¨bius value can be found by adding d(u, w) to this last summation,
o
completing the proof.

We close this section with several example M¨bius function calculations using the above
o
formula.
µ(121, 1221) = d(121, 1221) + ν(121, 121)
=2+1
=3

µ(2, 2212) = d(2, 2212) + ν(2, 211) − ν(2, 2)
= 0 + µ(2, 211) + µ(2, 21) + µ(2, 2) − µ(2, 2)
=0+0−1+1−1
= −1
µ(2, 3121) = d(2, 3121) + 0
=0

For larger examples, it is helpful to collect like terms and eliminate coefficients. In the
example below, 3111 has 31 as its primary prefix for one degree 0 and one degree 1 base, while
it has 3 as its primary prefix for one degree 1 base.
57

µ(3, 33133) =0 + (1 − 2 + 1)ν(3, 3111) − (1 − 1)ν(3, 31) − (−1)ν(3, 3)
+ (1 − 2 + 1)ν(3, 3112) + ν(3, 3113) + ν(3, 33)
=µ(3, 3) + µ(3, 3113) + µ(3, 33)
=1 + µ(3, 3) + µ(3, 3)
=3

A quick investigation of the formula yields the coefficient for each term ν(u, v) is dependent
on how many times v occurs as a principal factor of odd versus even degree, or how many times
v occurs as the primary prefix of principal factors of odd versus even degree. It is not possible
for the primary prefix x = x(pvi ) to be a principal factor of any degree. Indeed, its principal
index is the same as the principal factor pvi = x1m of w so that there are at least 3 embeddings
of x in w. So we would need to remove the middle embedding from w via strong descents before
removing the suffix embedding. This is impossible because the suffix embedding starts at a later
index than any other embedding.

Remark. We have noticed that there is often a clear relationship between the odd and even
counts, such as a binomial sum, resulting in an unusually high number of terms ν(u, v) with
coefficient zero. However, a precise description of when the coefficients are zero has eluded us.
For more comments on this, see the last section on open problems.

58

Chapter 4
Generalized Factor Order on Trees and
Forests
A tree is a poset for which the undirected graph underlying its Hasse diagram has no cycles,
and a forest is a disjoint union of trees. A rooted tree T is a tree with a unique minimal element.
We will show in this section that our results generalize to the case of a rooted forest F , which
is a disjoint union of rooted trees.
Suppose T is a rooted tree, and let r be its root. Since T has no cycles and every element
s satisfies s ≥ r, it follows that every element except the root covers a unique element. This is
why we are considering generalized factor order on these posets. It can be shown the M¨bius
o
function of generalized factor order on T ∗ is similar to that of P∗ , and the proofs leading to the
result are nearly identical. For this reason, we have chosen not to consider this case separately
from the rooted forest case.
Suppose F is a rooted forest. Like the rooted tree case, in a rooted forest, every nonminimal
element covers a unique element. However, there are multiple minimal elements in this poset.
This leads us to suspect that we need to combine the results of Section 2 with Theorem 27.
While this is largely true, we will see that the definition of principal factor does not translate
quite as expected, and that having multiple minimal elements complicates several results from
Section 3.
To be consist with Section 2, we say a flat word in the Kleene closure F ∗ is a sequence of
59

m’s, where m is a minimal element. We say a word is rooted if it consists entirely of minimal
elements since each minimal element is the root of a tree. Note that a flat word is also rooted.
The following lemma states that the covering relations of F ∗ are analogous to those of P∗ . It’s
proof is similar to that of Lemmas 4 and 11.
Lemma 28. A word w = w(1) . . . w(n) in F ∗ can cover up to n words, each formed by reducing
a letter in w to the unique letter it covers, where reducing a minimal element means removing
it from the word. Reducing w(1) and w(n) will always produce a factor, while reducing w(i) for
1 < i < n can only produce a new factor if w(i) is nonminimal. These words are distinct unless
w is flat, in which case w only covers one word which is flat.

Note that a minimal element m cannot be reduced unless it is at the beginning or end of a
word. We maintain the convention that if a word is flat, only the first m can be reduced. This
allows us to maintain the notion of a reducible letter w(i).
ˆ
Suppose we have a distinguished symbol ˆ and ˆ ∈ F . Define F to be the poset F with ˆ
0
0 /
0
added as the unique minimal element. This allows us to maintain the definition of expansion
ˆ
from the previous sections, that is, a word η ∈ F is an expansion of u ∈ F if η ∈ ˆ∗ uˆ∗ .
0 0
ln−1
l1
l2
ln
Let [u, w] be an interval in F ∗ . Let C : w = v0 → v1 → . . . → vn−1 → vn = u be a
maximal chain in [u, w], where the li are defined by the corresponding sequence of embeddings
ηvi in the sense that
ηvi (li ) = s where ηvi−1 (li ) → s and ηvi (j) = ηvi−1 (j) when j = li .
This gives each maximal chain C a chain id l1 . . . ln . This chain id is unique because every
ˆ
element in F except ˆ covers a unique element. Notice this is the most general class of posets in
0
which every interval ordered by generalized factor order has maximal chains with unique chain
60

ids of this form. By lexicographically ordering the chain ids, we get a poset lexicographic order
on the maximal chains of [u, w] which we will use to find the MSIs in the rooted forest case.
Let η be an embedding of u into w. Let mi = ρ(η(i)) − ρ(w(i)), where ρ is the rank
ˆ
function in F . This allows us to maintain the idea of an admissible permutation of the multiset
Mη = {1m1 , 2m2 , . . .} from the previous section.
By Lemma 28, the characterization of chain ids ending at nonflat words does not change.
Unfortunately, since both rooted and unrooted words can cover flat words, it is not possibly to
write down a useful characterization of chain ids ending at flat words. However, since flat words
can only be reduced to flat words, we will be able to deal with this case separately.
Proposition 29. Suppose F is a rooted forest, and u and w are two elements in F ∗ satisfying
u ≤ w. Let η be an embedding of u into w, mi = ρ(w(i)) − ρ(η(i)), and Mη = {1m1 , 2m2 , . . .}.
If u is not flat, then a sequence of numbers is the chain id for a maximal chain in [u, w]
ending at η if and only if it is an admissible permutation of the multiset Mη .
Since there are multiple minimal elements, we need to reconcile our previous classifications of
MSIs in the positive integer and antichain cases. To begin considering MSIs in the new setting,
we need to once again identify all intervals [u, w] in which a chain C has C(w, u) as an MSI.
Recall from Section 2 that descents always caused MSIs in the antichain case when they
were strong descents, that is, li+1 < li − 1. In the context of P∗ , a strong descent satisfied
vn−1 = vn+1 11. These conditions are analogous. So we call any descent vn that does not
remove two minimal elements from the back of a word a strong descent, that is, vn−1 = vn+1 mn
for any minimal elements m and n. The next proposition states that a strong descent causes a
length 1 MSI. Since its proof is essentially the same as that of Proposition 16, we omit it.

61

ln−1
l1
l2
ln
Proposition 30. Suppose [u, w] ⊂ F ∗ and C : w = v0 → v1 → . . . → vn−1 → vn = u is a
maximal chain in [u, w]. If vi is a strong descent, then vi is a length 1 MSI.
Notice this statement is not an if and only if, as in the antichain case outer word MSIs
can reduce consecutive letters from the back. Indeed, if 1 and a are minimal elements in F ,
the interval [1a, 1a1a] contains a length 1 MSI. The presence of length 1 MSIs containing weak
descents is one of the key differences between the antichain and positive integer cases.
While the idea of a maximal outer factor still holds in the new context, simple examples
reveal that the previous definition of a principal factor will not be sufficient for the forest case.
For example, suppose F is disjoint union of two chains, b → a and 2 → 1. Then in the interval
[b, bb1], the chain C with chain id 232 has C(bb1, b) as an MSI, even though b is not a suffix of
bb1. A quick analysis reveals that b behaves like the principal factors from the previous section
because the MSI results from a unimodal chain id which is the lexicographically first id leading
to the prefix embedding of the word b.
Deeper analysis shows that words causing MSIs in this manner can have multiple embeddings
in w. The smallest example we could find of this is in the interval [21a22, 21a221a22a22]. In
spite of the fact 21a22 has three embeddings in the larger word, there is a maximal chain in
which C(21a221a22a22, 21a22) is an MSI. Fortunately, the definition of a principal factor can
still be generalized to fit the new context so that once again, we will have exactly two types of
MSIs in F ∗ .
Let p be a word in F ∗ and let w be a word in F ∗ that is not flat. Suppose that p is a prefix
of w with other embeddings in w, and no longer prefix containing p has multiple embeddings in
w. Then there is a smallest index i, called the principal index of p in w, such that w(i) > p(i)
and w(i) is reducible. We say p is a principal factor of w if the word produced by reducing w(i)
62

contains only the prefix embedding of p.
Notice this definition accounts for both of the examples given before it. As in the previous
cases, the principal index of a principal factor must take a value greater than 1. Before proceeding, it is important to understand why this definition includes both outer words and the Section
3 definition of a principal factor as special cases. In the antichain case, an outer word o(w) of
a nonflat word is a principal factor when its principal index is |w| because only 1 and |w| are
reducible in the case of an antichain. Since reducing |w| can only remove the suffix embedding
of a word, we must have o(w) ≤ i(w) in order for it to be a principal factor, where i(w) is the
inner word. This provides further insight into this condition of Bj¨rner’s formula.
o
To see that the definition of a principal factor from Section 3 is generalized by the new
one, first note that a principal factor of an unrooted word w cannot be rooted. Indeed, if w
contains a nonminimal element, then the principal index of any rooted prefix p will point to
the first nonminimal element. So reducing this element cannot possibly remove any embeddings
of p. Furthermore, the new definition guarantees p is a suffix in the case of P. If p has an
embedding in w which is neither prefix nor suffix, the word p1 would have a prefix embedding
and another embedding, contradicting the maximality of p. While it is more difficult to identify
principal factors when they do not have a suffix embedding, this generalization clearly shows
which properties of principal factors cause MSIs.
i
Proposition 31. Suppose u is a principal factor of w with principal index i. Let C : w = v0 →
ln−1
l2
ln
v1 → . . . → vn−1 → vn = u be the lexicographically first chain in [u, w] with l1 = i. Then
C(u, w) is an MSI of C.
Proof. Using the same argument from the beginning of the proof of Proposition 17, we conclude
there exist chains that are lexicographically earlier than C. Also from this proof, if C is an
63

arbitrary maximal chain that is lexicographically earlier than C, then l1 < i and v1 must contain
an embedding of u which is not prefix.
Furthermore, since C is the lexicographically first chain ending at the prefix embedding of u,
we reduce the minimal letters at the end last, implying vn−1 = um for some minimal element
m. If v1 contained um, u would be contained in a longer prefix with multiple embeddings in w,
contradicting the fact that u is a principal factor of w. Thus, the only words common to C and
C are w and u. Since C was an arbitrary maximal chain in [u, w] with l1 < i, and C is the
first maximal chain in [u, w] with l1 = i, we conclude C(u, w) is an MSI.
If u is not flat, the first admissible chain ending at η, Cη , is the maximal chain whose chain
id is the lexicographically first permutation of Mη that is the chain id of a maximal chain. This
chain has the same structure it did in the case of P.
Lemma 32. Suppose [u, w] ⊂ P∗ and η is an embedding of u into w. Let

be the index of

the largest non-zero number in η. If u is not flat, Cη has as its chain id the unique unimodal
permutation of Mη with decreasing suffix |w|, |w| − 1, . . . , + 1.
The following Theorem completes the characterization of the MSIs and states they are once
again caused by strong descents or principal factors.
ln−1
l1
l2
Theorem 33. Suppose [u, w] ⊂ F ∗ , u is not the empty word, and C : w = v0 → v1 → . . . →
ln
vn−1 → vn = u is a maximal chain in [u, w]. Then C(vi , vj ) is an MSI of C if and only if
C(vi , vj ) consists of a strong descent, meaning vi = vj mn for any minimal elements m and n,
or vj is a principal factor of vi , li+1 is the principal index of vj with respect to the embedding
ηvj , and C[vi , vj ] is the first admissible chain in [vj , vi ] ending at the prefix-embedding of vj .
Proof. The reverse implication follows from Propositions 30 and 31.
64

Suppose C(vi , vj ) is an MSI of C. By the definition of a poset lexicographic order, C(vi , vj )
is an MSI of C if and only if it is an MSI of C[vi , vj ] in the interval [vj , vi ]. Thus, it suffices to
consider the case w = vi and u = vj .
Since |u| = |w| implies [u, w] is direct product of chains, Corollary 14 can be translated to
the forest case. This implies strong descents are the only MSIs when |u| = |w|. However, strong
descents are always length 1 MSIs. Therefore, it suffices to consider the case when |u| < |w| and
C(w, u) is an MSI of C that does not consist of a strong descent. Our first goals are to establish
that w has a prefix embedding of u and C[w, u] is the first admissible chain ending at the prefix
embedding.
Let η be the embedding of u into w at the end of the chain C. Note that any descent vk
in C is a weak descent since otherwise, by Proposition 30, C(vk−1 , vk+1 ) would be an MSI,
contradicting the minimality of C(w, u). If k +1 = n, this forces lk+2 < lk+1 = lk −1, implying
that vk+1 is also a weak descent. By continually applying this idea, we find that any descents
contained in C(w, u) occur in a single sequence of weak descents at the end of this interval, and
the corresponding labels form a decreasing sequence of consecutive numbers.
To see η is the prefix embedding of u into w, suppose for a contradiction that the set Mη
contains a 1. Since any descents occur in a sequence at the end of the interval, it follows that
l1 = 1 or ln = 1. If ln = 1, then since vn−1 is a weak descent, u is the empty word. This
contradicts our assumptions. Suppose l1 = 1. Then any chain C lexicographically earlier than
C has l1 = 1 and thus contains v1 , contradicting the fact that C(w, u) is an MSI. Therefore, η
is the prefix embedding of u into w, allowing us to write η = u.
Since |u| < |w|, we must reduce position |w| by the end of the chain. Note that the label |w|
can only be followed by another |w| or the sequence of labels |w| − 1, . . . , |u| + 1, which leads
65

to a sequence of weak descents. It follows that C must contain the word um for some minimal
element m. Since ln = |u| + 1, C reduces the m at the end of vn−1 = um to get vn = u. This
implies um (and hence w) is not flat. So by Lemma 32, C[w, um] is the first admissible chain
ending at the prefix-embedding of um. Since minimal elements can only be removed from the
front or back of a word, C is the first admissible chain ending at the prefix-embedding of u.
Since C(w, u) is an MSI, C cannot be the lexicographically first chain in [u, w]. Therefore,
w must contain another embedding of u in addition to the prefix embedding. This implies that
u has a principal index in w.
Next, we will show l1 is the principal index of u in w. Since C is the first admissible
chain ending at the prefix embedding, w(l1 ) is the first letter that is reducible and satisfies
w(l1 ) > u(l1 ).
We also need to show that the word v1 contains only the prefix embedding of u. For a
contradiction, suppose v1 contains another embedding ρ of u besides the prefix embedding.
Then there is a chain C ending at ρ whose chain id begins l1 1 . . . and has v1 = v1 . This chain
is thus lexicographically earlier than C and satisfies C − C(v1 , u) ⊂ C , contradicting the fact
that C(w, u) is an MSI. So v1 contains only the prefix embedding.
It remains to show that there is not a longer prefix containing u with another embedding
in w. For a contradiction, suppose there is a longer prefix of w containing u that has multiple
embeddings in w. Then um is a prefix of w for some unique minimal element m and has another
embedding in w. Let C be the lexicographically first chain in the interval containing um.
Note C also contains um because as the first admissible chain ending at the prefix embedding,
ln = |u| + 1. Thus, C − C(w, um) ⊂ C , implying C(w, um) is a skipped interval. This
contradicts the fact that C(w, u) is an MSI.
66

We can now easily describe the critical chains that consist entirely of strong descents. Since
the proof is very similar to that of Proposition 20, we omit it.
Proposition 34. Suppose [u, w] ⊂ P∗ , (u, w) is non-empty, and w is not flat. Suppose η is
an embedding of u into w. Then there is a critical chain C in [u, w] ending at η that consists
entirely of strong descents if and only if w(i) = η(i) or w(i) → η(i) for all i, η(2) = ˆ and
0,
η(|w| − 1) = ˆ Furthermore, these conditions imply |w| − |u| ≤ 2 and that [u, w] has at most
0.
two critical chains consisting entirely of strong descents.
It should be noted that in the antichain case, the fact that µ(i(w), w) = 1 for the inner word
i(w) when w is not flat follows directly from this proposition.
As in the case of P, the remaining critical chains must contain at least one MSI caused by a
principal factor. So these chains contain a principal factor of w or a principal factor pvi of some
vi with the property that C(w, vi+1 ) consists entirely of strong descents.
In order to have a critical chain in [u, w] involving an MSI resulting from a principal factor
pvi , pvi needs to be contained in a different MSI or pvi must equal u. By Theorem 33, pvi could
be contained in one of three types of MSI: an MSI caused by a strong descent, an overlapping
MSI caused by a principal factor, or an adjacent MSI caused by a principal factor. This is
where the forest case becomes more complex than the case of P because the third possibility
can happen. However, it can only happen when vi is a rooted word.
Moving forward, we will have few results that apply to both rooted and unrooted words.
However, unrooted words still behave much like they did in the positive integer case, and our
proof of Bj¨rner’s formula will help us understand rooted words in the new context.
o
Proposition 35. Suppose C(vi , pvi ) is an MSI of a critical chain C caused by the principal
factor pvi . If vi is unrooted, then pvi is unrooted and is contained in an MSI caused by a strong
67

descent or an overlapping MSI caused by a principal factor.
Proof. If p is rooted prefix of an unrooted rooted vi , then the principal index of p in vi contains
a nonminimal element. So reducing the letter at the principal index cannot eliminate any
embedding of p. Thus, a rooted word cannot be a principal factor of an unrooted word.
Let vj+1 = pvi . Suppose for a contradiction that C(vj , pvj ) is an MSI caused by a principal
factor. Since C(vi , vj+1 ) is an MSI caused by a principal factor, Theorem 33 implies C[vi , vj+1 ]
is the first admissible chain ending at the corresponding embedding. So by Lemma 32, vj =
vj+1 m for some minimal element m. However, this implies the value at the principal index
lj+1 = |vj | of pvj in vj is m. But then vj and vj+1 = pvi are rooted words because the
principal index of an unrooted principal factor must contain a nonminimal letter. Since pvi is
not rooted, this is a contradiction.
As stated above, this result does not apply to rooted words. For example, in [1, 1a1a], the
rooted principal factor 1a is contained in the adjacent MSI caused by the rooted principal factor
1 of 1a1.
The previous result essentially separates the unrooted words from the rooted ones.
Corollary 36. If w is not a rooted word and C(w, u) is a critical maximal chain of [u, w], then
C(w, u) has no MSIs caused by rooted principal factors.
Proof. Suppose for a contradiction C(w, u) did contain an MSI caused by an rooted principal
factor. By Proposition 35, a principal factor of an unrooted word is also not rooted. Thus, the
last unrooted word in C(w, u) must be a strong descent vk . Since no rooted word is a principal
factor of vk , vk+1 must also be a strong descent for it to be contained in an MSI. This implies
lk+2 = 1, so that vk+2 cannot be a strong descent MSI. However, the principal index of a
68

principal factor cannot be 1. Thus, vk+2 cannot be in an MSI caused by a principal factor. So
by Theorem 33, if u = vk+2 , vk+2 is not in any MSI, contradicting the fact that C(w, u) is a
critical maximal chain. If u = vk+2 , then we have shown C(w, u) has no MSIs caused by rooted
principal factors.

This allows us to conclude that if w is not rooted, any overlapping MSIs in the set I(C) of
a critical chain must come in pairs.

Proposition 37. If w is not rooted, an MSI of a critical chain can overlap with at most one
other MSI.

Proof. This proof is entirely analogous to that of Proposition 23, with two notable exceptions.
First, we need to point out that by Corollary 36, all words involved in the overlapping intervals
C(vi , vj ), C(vi , vj ), . . . , C(vi , vj ) are not rooted. Second, this implies each ηvi (li +1 )
1 1
2 2
k k
is nonminimal because li +1 corresponds to a principal index of an unrooted word.
Notice again that this restriction on overlapping MSIs does not apply to rooted words. For
example, in the last maximal chain of [a, a11aa11a], the word a11aa is contained in three MSIs.
Nevertheless, this chain is critical.
At this point, it is clear that the J(C) structure of the critical chains is essentially the same
as in section 3 when a word is not rooted, while the forest case reduces to the ordinary factor
order case of section 2 when a word is rooted. To establish the formula, we will also need to
update the definitions of primary prefixes and the ν function, and use them to establish the
formula when w is not rooted. We have little choice but to establish the formula separately for
rooted words.

69

ln−1
l1
l2
ln
Theorem 38. Suppose w is not a rooted word. Let C : w = v0 → v1 → . . . → vn−1 →
vn = u be a maximal chain of [u, w]. Then C is a critical chain if and only if C(w, u) can be
written as a sequence of intervals

C[vi = v1 , vi ) ∪ C[vi , vi ) ∪ . . . ∪ C[vi
, v = u)
1
2
2 3
k−1 ik

where each interval C[vi , vi
) is one of the following three types:
j j+1
1. C[vi , vi
) is an MSI caused by the strong descent vi .
j j+1
j
2. C[vi , vi
) is an MSI caused by the principal factor vi
of the word vi −1 .
j j+1
j+1
j
3. The word vi
is a principal factor of a word in C[vi
, v ) and satisfies
j+1
j−1 ij
vi
m . . . mk = vi , where each mi is a minimal element and k = |vi | − |vi
| > 0.
j+1 1
j
j
j+1
The value k is unique in the sense that no other word satisfies the description of vi
j+1
for another value k.
Furthermore, type (1) intervals are followed by intervals of type (1) or (2), type (2) intervals
are followed by intervals of type (1) or (3), and type (3) intervals are followed by intervals of
type (1). Finally, only intervals of type (1) or (2) can begin the decomposition.
Proof. Since w is not rooted, by Corollary 36, no rooted word can be a principal factor which
causes an MSI.
Thus, both implications can be proved as they were in the proof of Theorem 24 by updating
the relationship between between vi and vi
. For example, in the forward implication, we
j
j+1
have vi = vi
m . . . mk = vi , where each mi is a minimal element and k = |vi |−|vi
|>
j
j+1 1
j
j
j+1
0, instead of vi = vi
1m for m = |vi | − |vi
|.
j
j+1
j
j+1
70

Since Theorem 38 gives essentially the same result as Theorem 24, when w is not rooted, we
need only update the appropriate definitions to get the desired formula. However, we will need
to handle the case when w is rooted separately before stating the formula.
Define a word v to be a base of w if v(j) = w(j) or w(j) → v(j) for all j and |v| = |w| or
|w| − 1. Define the degree of a base to be the number of indices j for which w(j) → v(j).
Suppose vi is a base of w of degree i. Let l be the index of the smallest position satisfying
w(l) → vi (l), or |w| + 1 if i = 0. We define any word pvi that is a principal factor of vi and
whose principal index takes a value less than l to be a principal factor of w of degree i. As in
the previous section, when a degree is not noted in the language or the notation, the assumption
will be that the principal factor has degree 0.
Define w \ k to be the word that results when k minimal elements are removed from the
suffix of w, or as undefined if w ends in less than k minimal elements. Note that unlike the
integer case when 1 was the only minimal element, there are multiple minimal elements which
could be reduced.
Suppose pvi is a principal factor of vi . Let vi be the word that results when the letter in
vi at the principal index of pvi is reduced by 1 rank. That is, vi (j) → vi (j) when j is the
principal index of pvi and vi (j) = vi (j) for all other indices j. Define the primary prefix x(pvi )
of a principal factor pvi to be the longest proper prefix that has at least 2 embeddings in vi and
satisfies x(pvi ) = pvi \ k for some k. So if no k > 0 satisfies the restriction, or no such word has
at least two embeddings in vi , the primary prefix is undefined
Notice the primary prefix definition still makes sense when pvi is rooted, in which case i = 0
and pv0 is an outer word not contained in the inner word. In this case, x(pv0 ) = pv0 \ 1. As was
seen in our proof of Bj¨rners result, this implies that whenever u ≤ x(pv0 ), pv0 is contained in
o
71

a length 1 MSI.
The following proposition asserts that the primary prefix is the only word that can cause a
type (3) interval after the type (2) interval C(vi , pvi ). While the spirit of the proof is similar to
that of Proposition 25, the definition of a primary prefix has changed enough to warrant stating
the entire proof.
Proposition 39. Suppose w is not rooted. Let C be a maximal chain of [u, w] and suppose
C(vi , pvi ) is a type (2) interval in the set J(C). Then C(vi , pvi ) is followed by a type (3)
interval C[pvi , x) in J(C) if and only if x is the primary prefix of pvi and x appears in C.
Proof. First suppose x is the primary prefix of pvi and that it appears in C. Let v be the last
word in the interval C(vi , pvi ) that contains at least two embeddings of x. We will show x is
a principal factor of v with principal index l +1 . Since pvi is a prefix of v +1 , x is as well.
So v +1 only contains the prefix embedding of pvi . Furthermore, since C[vi , pvi ] is the first
admissible chain in [pvi , vi ] ending at the prefix embedding of pvi , for all li+1 < k < l +1 ,
either we have v (k) = pvi (k) or we have v (k) minimal and pvi (k) = 0. Therefore, for all
li+1 < k < l +1 , either we have v (k) = x(k) or we have v (k) minimal and x(k) = ˆ This
0.
implies C[v , x] is the first admissible chain in [x, v ] ending at the prefix embedding of x and
v (l +1 ) is the first reducible letter in v greater than the corresponding position in the prefix
embedding of x. Thus, l +1 satisfies the definition of a principal index, and since v +1 only
contains the prefix embedding of pvi , x is a principal factor of v and C(v , x) is an MSI of C.
Since x is the longest proper prefix of pvi with two embeddings in vi that satisfies x = pvi \ k
for some k, and C(vi , pvi ) is a type (2) interval, no word between pvi and x can be a principal
factor of a word vk in C. Therefore, C(v , x) is reduced to the type (3) interval C[pvi , x) in
J(C), completing the reverse implication.
72

Now suppose that C(vi , pvi ) is followed by a type (3) interval C[pvi , x) in the set J(C).
Then by Theorem 38, x is a principal factor of a word v in C(vi , pvi ) and x = pvi \ k for some
k. From the proof of Theorem 38, we know |v| = |vi | and v has at least two embeddings in vi .
By Theorem 38 part (3), it suffices to show that no longer prefix of pvi containing x has two
embeddings in vi . For a contradiction, suppose y is such a prefix. Then y = xm1 . . . m has at
least two embeddings in vi , and by the argument in the paragraph above, is a principal factor
of some word in C(vi , pvi ). Thus, C(v, y) would be an MSI in I(C). This would be reduced to
the interval C[pvi , y), which is contained in C[pvi , x), implying that C[pvi , x) could not be in
J(C). This is a contradiction. Thus, x is the longest proper prefix of pvi with two embeddings
in vi , implying it is the primary prefix of the word pvi .
Let µ(u, v) be the normal M¨bius function if u and v are both elements of F ∗ , or zero if
o
either is undefined. Define the function ν(u, v) to be

µ(u, v \ i).

ν(u, v) =
i≥0

Notice all the terms in the summation will be zero beyond the largest value i = k for which v \ k
is defined, or the smallest value i = k for which v \ k ≤ u.
We are now ready to state the contribution of critical chains whose first type (2) interval is
a specific interval. By replacing the words pvi \ 1k in the proof of Proposition 26 by pvi \ k, it
is easy to adapt that proof to work for the next proposition.

Proposition 40. Suppose w is not rooted and C(vi , pvi ) is the first type (2) interval of some
critical chain C of [u, w]. Then pvi is a principal factor of w of degree i and vi is based in C.
Furthermore, the contribution to the M¨bius value µ(u, w) of all critical chains in [u, w] that
o
73

have C(vi , pvi ) as the first type (2) interval is
(−1)i ν(u, pvi ) − ν(u, x(pvi )) ,

where x(pvi ) is the primary prefix of pvi .
Our next goal is to consider the intervals [u, w] for w rooted. Note that when w is rooted,
the forest case reduces to the antichain case. Therefore, the formula for µ(u, w) is given by
Theorem 1, which the reader may wish to refresh at this time. Thus, we must show this
theorem is now a special case of our formula from Section 3. The key fact in the proof is that
the primary prefix of a rooted principal factor pvi is pvi \ 1, which was also the key in proving
Bj¨rner’s formula using discrete Morse theory.
o
Let ρ denote the rank function in F ∗ , and ρ(u, w) = ρ(w)−ρ(u). For simplicity, let 0 ≤ t ≤ 2
be the number of critical chains in [u, w] that consist entirely of strong descents, and define

if ρ(u, w) > 1



(−1)ρ(u,w)


d(u, w) =




t(−1)ρ(u,w)


if ρ(u, w) ≤ 1.

Proposition 41. Suppose u ≤ w in the poset F ∗ and w is a rooted word. Then

µ(u, w) = d(u, w) +

(−1)i ν(u, pvi ) − ν(u, x(pvi )) = d(u, w) + µ(u, o(w)),

where o(w) is the outer word as defined on page 1 and the sum is over all triples vi , pvi , x(pvi )
such that pvi is a principal factor of w of degree i with base vi and primary prefix x(pvi ).
Proof. First we show rooted words can only have principal factors of degree 0. Since any rooted
74

strong descent vi satisfies vi+1 = mvi−1 n for some minimal elements m and n, and every
principal factor of vi has principal index |vi | = 1, rooted words do not have bases of positive
degree. Thus, they cannot have principal factors of positive degree either.
We need to show the formula in Theorem 1 agrees with the one in the statement of this
proposition. Suppose |w| − |u| ≤ 2 and u = o(w). Then by Proposition 34 and Theorem 1,

µ(u, w) = d(u, w).

Furthermore, by the definition of principal factor, the only word that can be a principal factor
is the outer word o(w). Note |w| − |o(w)| > 1 when o(w) is not flat. So u ≤ o(w), implying the
summation is 0 because ν(u, o(w)) = 0 and µ(u, o(w)) = 0 by definition. This completes the
proof in this case.
Next, suppose |w| − |u| > 2, u ≤ o(w) \ 1, and o(w) ≤ i(w). Note o(w) is the unique principal
factor of w. From the discussion following the definition of the primary prefix, we know o(w) \ 1
is the primary prefix of o(w). Furthermore, by Proposition 34, d(u, w)=0 because |w| − |u| > 2.
Thus,

(−1)i ν(u, pvi ) − ν(u, x(pvi )) =ν(u, o(w)) − ν(u, x(o(w)))
=µ(u, o(w)) + ν(u, o(w) \ 1) − ν(u, o(w) \ 1)
=µ(u, o(w)),

completing the proof in this case.
Suppose |w| − |u| ≥ 2, u ≤ o(w), u ≤ o(w) \ 1 and o(w) ≤ i(w). Note o(w) is the unique
principal factor of w, but the primary prefix of o(w), o(w) \ 1, does not contain u. Furthermore,
75

by Proposition 34, d(u, w)=0 because |w| − |u| ≥ 2 and u = i(w). Thus,

(−1)i ν(u, pvi ) − ν(u, x(pvi )) =ν(u, o(w)) − 0
=µ(u, o(w)) + ν(u, o(w) \ 1)
=µ(u, o(w)),

completing the proof in this case.
Finally, in all other cases, |w| − |u| > 2 and o(w) ≤ i(w). Since |w| − |u| > 2, d(u, w) = 0.
Since o(w) ≤ i(w), o(w) is not a principal factor of w, meaning the summation is 0 as well. This
agrees with Theorem 1, which states µ(u, w) = 0 in all other cases, completing the proof.
Using Propositions 34, 40, and 41 we are able to write down a formula for µ(u, w) for u ≤ w
in F ∗ .
Theorem 42. Suppose u ≤ w in the poset F ∗ . Then

µ(u, w) = d(u, w) +

(−1)i ν(u, pvi ) − ν(u, x(pvi )) ,

where the sum is over all triples vi , pvi , x(pvi ) such that pvi is a principal factor of w of degree
i with base vi and primary prefix x(pvi ).
Proof. If w is rooted, the result follows from Proposition 41.
If w is unrooted, the proof of the desired result is an easy adaptation of the proof of Theorem 27.

76

Chapter 5
Future Research and Open Problems
5.1

Generalizing and Simplifying this Formula

As noted at the end of Section 3, many of the coefficients in our formula for generalized factor
order on the integers are zero. This phenomenon is even more pronounced in the rooted forest
case. Since our formula simplifies considerably in the case of rooted words, it is natural to
wonder whether the general formula can be simplified as well.
Should this formula be simplified, it will likely be done in one of two ways. It may be possible
to find a formula which applies to a more general class of posets ordered by generalized factor
order. Sagan and McNamara are attempting to prove a formula that works for any poset ordered
by generalized subword order which is simpler than the one given in [7]. Thus, it is possible a
similar situation could arise here.
To investigate generalized factor order on other posets P ∗ , one needs to consider words which
cover multiple elements, complicating the poset lexicographic order we used in this investigation.
One way to resolve these complications is to place an order on the children of each element of
P . This would generalize our current chain ids by including a subscript on the label indicating
which child each letter is reduced to. In the context of F ∗ , such subscripts would always be 1
because each element has a unique child, making this new type of chain id a clear generalization
of the current one. Initial data suggests it is worth pursuing this line of thought to see if a
formula can be found in more general cases.
77

It may also be possible to simplify the formula at the level of critical simplices. In particular,
it is often the case that critical simplices of dimension d and d + 1 are present when a coefficient
of ν(u, pvi ) is zero. This leads one to suspect it may be possible to use the discrete analogue of
“The First Cancellation Theorem” from smooth Morse Theory to cancel critical simplices.
However, it is not clear whether reducing the number of critical simplices in such a manner
would result in a simplified formula. For example, it is often the case that a principal factor p
will have have unique minimal degree base bi (of degree i) and maximal base degree base bj (of
degree j) such that if bk (of degree k) is another base, then i < k < j. When this happens, a
binomial sum zeros out the coefficient of ν(u, p). But this is not always the case - the smallest
counterexample we found was the word u = 2111222 in the interval [2111222, 2111222112221222],
in which u occurs as a principal factor of degree 1 twice, degree 2 once, but is not a principal
factor of degree 0 because 21112221111 is a longer outer factor. We were not able to reconcile
the previous observation with this exception to it in a desirable manner.

5.2

The Topology of P∗ and F ∗ Under Generalized Factor
Order.

Besides being useful results in proving the formula given for the M¨bius function of P∗ and F ∗ ,
o
Theorems 24 and 38 can be used to get a detailed description of the critical simplices of intervals
in P∗ and F ∗ . Thus, it is a first step into investigating the homotopy type of these posets. The
next step is again checking whether there are critical simplices of dimension d and d + 1 which
cancel each other out.
78

5.3

The Consecutive Pattern Poset and Ordinary Factor
Order

In a paper submitted to the arXiv in 2011, Bernini, Ferrari and Steingr´
ımsson calculate the
M¨bius function of the consecutive pattern poset [2]. Let Sd be the set of all permutations of
o
the first d positive integers. A consecutive pattern σ = a1 a2 . . . ak appears in a permutation
τ = b1 b2 . . . bn if the letters of some subsequence bi bi+1 . . . bi+k−1 of τ appear in the same
order of size as the letters in σ. The consecutive pattern poset is ∪d≥0 Sd ordered with respect
to consecutive pattern containment.

One of their results is a formula for M¨bius function of the consecutive pattern poset which
o
has many similarities to Bj¨rner’s formula for the M¨bius function of ordinary factor order. This
o
o
suggests there may be some common generalization of these posets. In particular, both posets
consist of words which only cover elements obtained by reducing the first or last letter, and all
M¨bius values are −1, 0, or 1. By investigating this poset with discrete Morse theory, it may
o
be possible to find a more general poset in which all critical chains have decreasing chain ids of
the form used in this paper, giving at most one critical chain in every interval. This may lead to
more results about the M¨bius function in the case of posets ordered by permutation patterns.
o
79

APPENDIX

80

Appendix A
The Matching of Babson and Hersh
In [1], Babson and Hersh give the acyclic matching of simplices in ∆(u, w) based on whether
the sets I(C) and J(C) cover C. Although knowledge of this matching is not required to apply
Theorem 3, we record the matching below for completeness.
The Matching:
• If I(C) does not cover C(w, u), let ρ0 be the lowest rank (that is, the last) vertex not
covered by I(C).
Match each new simplex h with h

{ρ0 }, where

is the symmetric difference operator

(that is, h \ {ρ0 } if ρ0 ∈ h and h ∪ {ρ0 } if ρ0 ∈ h.) This matching matches all new simplices of
C.
Note that h

{ρ0 } is always in C \ ( C <C C ) because the inclusion/exclusion of ρ0

does not affect whether the simplex hits every MSI. Also, this matching works for the very first
maximal chain since the empty set is consider a simplex in ∆(u, w).

• Otherwise, I(C) covers C and we base the matching on J(C) = {J1 , . . . , Jr }. Let ρi be
the lowest rank vertex of Ji ∈ J(C). Let Jr+1 = the set all vertices not in J(C), and let ρr+1
be the lowest rank vertex in Jr+1 . Define a map τ that associates an integer with each new
simplex h based on the first set Ji which h intersects in more than the lowest rank element.
81

That is,

τ :C \(

C ) → [r] ∪ {∞}

C <C
h → min {i|h ∩ Ji = {ρi }},
1≤i≤r
setting τ h = ∞ when h intersects each Ji in exactly the lowest rank element (that is, when the
set {i|1 ≤ i ≤ r, h ∩ Ji = {ρi }} is empty.)
First, if τ h = ∞, match the new simplex h with h

{ρτ h }. This matches all simplices for

which τ h = ∞.
If Jr+1 = ∅, then J(C) covers C and there is one simplex satisfying τ h = ∞. This simplex
contains each ρi . Thus, there is one simplex unmatched and it is a critical simplex of this
matching.
If Jr+1 = ∅, then J(C) does not cover C even though I(C) does. In this case, we match each
simplex h satisfying τ h = ∞ with h

{ρr+1 }. This matches all simplices for which τ h = ∞.

The matching is more complicated when I(C) covers C but J(C) does not because ρr+1 is
in I(C). Thus, removing it from a simplex does not guarantee every MSI is still hit, meaning
that h \ {ρr+1 } might not be in C \ (

C <C

C ). To guarantee h \ {ρr+1 } is a new simplex,

we need the lowest rank element of each Ji , ρi , in h. Indeed, any interval from I(C) reduced
and not included in J(C) intersects some interval Ji in at least the element ρi . This issue led
to a mistake in the published version of Babson and Hersh’s article, but this mistake is absent
from later versions.
Please refer to Tables 3 and 4 for the context of the below examples.
• I(C) does not cover C. Example: Chain 1 − 2 − 5 − 3 in the interval [b, bbabb]. Match
82

new simplices based on inclusion/exclusion of vertex abb. That is, match ab with abb − ab and
babb − ab with babb − abb − ab.
• J(C) covers C. Example: Chain 5 − 4 − 3 − 1 in [b, bbabb]. Match 2 of 3 new simplices,
based on inclusion/exclusion of vertex bba. That is, bba − bb is an unmatched, critical simplex,
while bbab − bb is matched with bbab − bba − bb.
• I(C) covers C, but J(C) does not. Example: Chain 6 − 5 − 4 − 3 − 2 in [a, abbabb]. We
match all new simplices based on the matching rules above. In particular, match abbab − abb
with abbab − abba − abb, abbab − abb − ab with abbab − abba − abb − ab, and abba − abb with
abba − abb − ab.

83

BIBLIOGRAPHY

84

BIBLIOGRAPHY

[1] Babson, E., and Hersh, P. Discrete Morse functions from lexicographic orders. Trans.
Amer. Math. Soc. 357, 2 (2005), 509–534 (electronic).
[2] Bernini, A., Ferrari, L., and Steingr´
ımson, E. The M¨bius function of the conseco
utive pattern poset. Preprint arXiv:1103.0173.
¨
[3] Bjorner, A. The M¨bius function of subword order. In Invariant theory and tableaux (Mino
neapolis, MN, 1988), vol. 19 of IMA Vol. Math. Appl. Springer, New York, 1990, pp. 118–124.
¨
[4] Bjorner, A. The M¨bius function of factor order. Theoret. Comput. Sci. 117, 1-2 (1993),
o
91–98. Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991).
[5] Forman, R. A discrete Morse theory for cell complexes. In Geometry, topology, & physics,
Conf. Proc. Lecture Notes Geom. Topology, IV. Int. Press, Cambridge, MA, 1995, pp. 112–
125.
[6] Forman, R. A user’s guide to discrete Morse theory. S´m. Lothar. Combin. 48 (2002),
e
Art. B48c, 35 pp. (electronic).
[7] Sagan, B. E., and Vatter, V. The M¨bius function of a composition poset. J. Algebraic
o
Combin. 24, 2 (2006), 117–136.
[8] Stanley, R. P. Enumerative combinatorics. Vol. 1, vol. 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1997. With a foreword by
Gian-Carlo Rota, Corrected reprint of the 1986 original.

85