-.‘,_-..

 

 

 

”-16le

{lllllllllllllllllllllJUlNlllllHlllllllllllllllllllllll

1293 00885 0160

This is to certify that the

dissertation entitled

Extremal Problems for the Mobius Function

presented by

Margaret A. Readdy

has been accepted towards fulfillment
of the requirements for

Ph.D. Mathematics

 

 

degree in

Major ess

Date Q/Qg/Clg

MS U i: an Aflirman’ve Action/Equal Opportunity Institution 0-12771

 

___.

r ‘\
LIBRARY

Michigan State
University J

 

 

L

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

______T=______

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MSU Is An Affirmative Action/Equal Opportunity Institution
omens-9.1

 

 

 

 

EXTREMflL PROBLEMS FOR THE
MOBIUS FUNCTION

By

Margaret A. Readdy
A DISSERTATION

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

DOCTOR OF PHILOSOPHY

Department of Mathematics

1993

ABSTRACT

EXTREMAL PROBLEMS FOR THE MOBIUS FUNCTION

By

Margaret A. Readdy

In the vein of recent work of Sagan, Yeh and Ziegler, we study extremal problems
connected with the Mobius function p of certain families of subsets from On, the
lattice of faces of the n-dimensional octahedron. In particular, we find that for lower
order ideals .‘F in On, |p(}")| attains a maximum by taking roughly the lower two-
thirds of the poset. For the case when .7: varies over all intervals of rank-selections, we
give a proof which finds the extremal configuration when n E 4(5). When n i 4(5),
our proof narrows down the extremal configuration to one of two possibilities. We
include data which supports our conjecture that the maximum occurs by taking the

ranks from approximately fin to En.

Purtill showed in a recent thesis that the coefficients of the cd-index <I> are non-
negative for certain posets, including the Boolean algebra B7, and the n—octahedron.
This work has been generalized by Stanley, who found the coefficients of (I) are non-
negative for face-lattices of convex polytopes. Stanley has observed that the non-
negativity of the coefficients of <I> immediately implies the arbitrary rank-selection
results for face lattices of convex polytopes. The Mobius function is maximized by
taking every other rank of the corresponding face lattice. For the record, we verify
the details of Stanley’s observation. In fact, Purtill’s recurrence for the cd-index of

Bn and 0,, allow us to conclude that the odd and even alternating ranks are the

only extremal configurations for these two posets. We include a conjecture of Stanley
which, if true, implies uniqueness of the extremal configuration for face lattices of

convex polytopes.

Sagan, Yeh, and Ziegler also studied Ln(q), the lattice of subspaces of an n-
dimensional vector space over GFq. For this poset they found all of Ln(q) is the
extremal configuration for the lower order ideal case. Using the inversion statistic,
we show the interval of ranks and arbitrary rank-selection cases also have the same

extremal configuration, i.e. the entire poset.

DEDICATION

To my parents Mary and Arthur,
and to the women in my family:
past, present and future.

iv

ACKNOWLEDGEMENTS

I would like to take this opportunity to thank my advisor Bruce Sagan for his
encouragement and enthusiasm. Perhaps the best way to express my thanks is to
paraphrase Roe Goodman, my Rutgers undergraduate mentor, who said the only
way we can begin to repay our professors for their time and spirit is, in turn, to treat

our own students with the same kindness and respect.

Special thanks to my doctoral committee, composed of Bruce Sagan, William
Brown, Edgar M. Palmer, Joel Shapiro, and William Sledd. Each represents a seg-
ment of the math community at Michigan State University with which I have been
fortunate to have had contact. In particular, a warm thank you to Christel Rotthaus

who acted as a “second advisor” for me when Bruce was visiting UCSD.

The faculty and staff of the Mathematics Department at Michigan State Univer-
sity, chaired by Richard Phillips, has generously supported me during my graduate
career. This includes providing transportation to special lectures in Ann Arbor for
the discrete graduate students, funding for conferences, and taking a continued in-
terest in my progress. Amongst the graduate students, we often say how spoiled we
are to have such a committed chair. Richard Phillips may perhaps be the very best

chairperson each of us will ever have.

During all four of my summers in East Lansing, David H. Y. Yen and Charles
Seebeck have always managed to arrange summer research support for me. I greatly
appreciate this vote of confidence and the extra time it gave me to concentrate on

my research.

The library staff, led by Dorothy Manderscheid and Chris DeFord (with help
from Sonya, Amy, Carrie, James, and Kim) has been especially helpful and friendly.

Thanks to Dorothy I now know who Bourbaki really is and where to find him.

Finally, my gratitude to all of my academic relatives, most especially my math
grandfather, Richard Stanley. On more than one occasion Richard Stanley has taken
time to ask me about my work and to offer his advice. He truly takes an interest in
whatever mathematics you happen to be working on, no matter how great or how

small.

vi

Contents

LIST OF TABLES

0.1 Basic Notation .............

0.2 Introduction ................................

1 Lower Order Ideals

1.1 Elementary Properties for 0,, ......................

1.2 Rank-Selected Lower Order Ideals ....................

1.3 Arbitrary Lower Order Ideals .....

2 Interval of Rank-Selections

2.1 Edge and Chain Labelings .......

2.2 Augmented Signed Permutations and Rank-selections .........

2.3 Proof of the Interval Case for 0,, . . .

3 Arbitrary Rank-selections

3.1 The ab—index and the cd-index .....

3.2 Arbitrary Rank-selections: Lp and 0,,

4 L,,(q); Related Extremal Questions

vii

00000000000000000

ix

16

2O

29

30

36

38

62

64

67

77

4.1 L,,(q): Interval of Ranks and Arbitrary Rank-selections ........ 77

4.2 Related Extremal Questions ....................... 84

BIBLIOGRAPHY 86

viii

List of Tables

1.1
1.2

2.1
2.2

3.1

4.1

Ip(0,,[lc])| for n = 2,3,4 ......................... 17
Lower Order Ideal Extremal Configuration for 0,,, n = 1, . . . , 25 . . . 28
Common Value of r for Row and Diagonal Results ........... 57
Extremal Configuration for Interval of Rank-selections from 0,, . . . 61
Arbitrary Rank-selection from 0,,: Maximum Mobius Value for n =

l, . . . , 10 .................................. 76
Comparison of the Predicted q with the Actual q, n = 1,. ..,10 . . . 84

ix

0.1 Basic Notation

We follow [17, chapter 3] for most of the terminology and notation we will use in
this dissertation. A partially ordered set (poset) P is a set P together with a binary
relation 3 (sometimes denoted by _<_p to indicate the poset P) which is reflexive,

antisymmetric and transitive, i.e.

(i) (reflexivity) For all a: E P, a: S 1:.
(ii) (antisymmetry) If :1: S y and y S at, then a: = y.

(iii) (transitivity) If :r S y and y S 2, then a: 5 2.

We use the notation .1: < y to indicate .1: S y and 3: 7E y. In a similar fashion,
the notation y > a: means a: < y. We say 2,3] 6 P are comparable if :c _<_ y or
y _<_ 9:; otherwise they are incomparable. The element y covers a: (notation: a: 4 y) if

a:<zSyimpliesz=y.

Two posets P and Q are isomorphic if there exists an order-preserving bijection
n : P —+ Q whose inverse is also order-preserving. The direct product or Cartesian

product of P and Q is the poset P x Q defined on the set

flamszRyeQ}

such that

(93,3!) SPxQ (5.31,) if 17 SP 17' and 31 So y'.

Given a finite poset P its Hasse diagram is a graph G = G(V, E) Its vertices V
consist of the elements of P. The edges E are determined by the cover relations of
P. In other words, we draw an edge between a: and y if x < y. To clearly show the

“hierarchy” of P, we draw y above 2:.

A chain c in P is a subset of P so that every two elements are comparable. Thus,

if the elements of c are {$041, . . . ,n}, with z, < 2:,- when i < j, we can write c as
c: $o<$1 <...<xk.
We say this chain c in P is unrefinable (or saturated) if we can write c as

c: zo-<:r1-<...-<:ck.

A maximal chain in a poset P is an unrefinable chain from a minimal element in P

to a maximal element in P.

Let P be a poset that has unique minimal element 0 and unique maximal element 1
(i.e., P is bounded). P is a graded poset of rank n if every maximal chain in P have the

same length n. All the posets we study in this dissertation will be finite and graded.

Thus, we have an associated rank function p defined by p : P —> {0, 1, . . . , n}, where
_ 0 if y = 0
p(y)_{p(x)+1 ifx-<y.

The n-dimensional octahedron 0,, is the convex hull of the 2n points
{$61, . . . , :lzen}

in n-dimensional Euclidean space, where

e,-=(0,...,0,1,0,...,0).

t-l n—i

For brevity, we will label these points by writing +i for +e,- and —i for —e,-. Using
this notation, we see that any proper face of 0,, can be labeled using a signed subset

of{1,. . . ,n}, i.e. a subset of the set {i1,. . .,:tn}, say

5 ={01,...,ak},

where S cannot contain both the elements +i and —i.

We can associate a poset 0,, with this geometrical object, called the lattice of faces
of the n-dimensional octahedron. We construct 0,, by taking all of the faces of 0,,
and ordering them by inclusion. With respect to the shorthand we have adopted, we
can represent 0,, as the poset of all signed subsets of {1, . . . , n} ordered by inclusion
with the element 1 adjoined. (Here we need to have an element which represents the
maximal face of 0,,, i.e., 0,, itself, since the notation does not lend itself naturally
to representing this element. Thus I is this maximal face.) The rank of any element
5' E 0,, \ I is given by IS I, where I - | denotes cardinality. Observe that I has rank

n + l in 0,,.
For a family .7" (_I P we define its completion by
f” = 7-“ u {6, i}
and its proper part by
7‘ = .7-'\ {0, i}.
An interval [.r, y] in P is defined by
[z,y]={zEP: xngy}, forxSy.

Notice that [23, 3:] consists of the element at. We do not allow the empty set to be an

interval. Given a poset P, the Mo'bius function ,u is defined recursively on intervals

[x,y] in P by

p(:r,a:) = 1 for all a: in P,

#(xay) = - 2 ”(3,2).

z$z<y

For brevity, we let u(P) denote the value of up(0,1). For a: an element of P we let

p(:r) denote up(0,.r). Additionally, for any family .7: of elements of P we let M?)

equal p;(0, 1).

Given a non-negative integers i and j, we let

[i]={1,2,...,i}

and
liajl = {i,i+1,-~,J'},
with the conventions that [0] = 0 and [i, j] = 0 for j < i. If rank(l) = r, then for a

family .7: Q P and S Q [r — 1], we define the rank-selected subposet
f(5) = {:r E f: rank(:c) E S}.
In particular the 2"” rank level of .7 is given by
17(2) = f({i}) = {2: E f: rank(a:) = i},

and the interval [i, j] of ranks of .7: (not to be confused with the closed interval [:r, y]

of elements of P) is
fizkj] = fawn = {. e f: mu.) 6 [2311}.
Also, we use the shorthand
1"[k] = .7([k]).

Finally, a lower order ideal A is a subset A of P such that if a: E .A and y S :1: then

yEA.

0.2 Introduction

The questions studied in this thesis belong to a branch of mathematics called ex-
tremal combinatorics. Extremal combinatorics is concerned with finding the “best”

configuration (according to some given criteria) among a set of possible arrangements.

As an example, in [17, Exercise 3.41a] Stanley posed the following extremal ques-
tion: given a bounded poset P with a fixed number of elements, what is the maximum
value of the Mobius function of P? Ziegler answered this question for both bounded
posets and graded posets. He also determined the extremal configuration in each

situation [21].

Recent work of Sagan, Yeh and Ziegler [15] approached extremal problems involv-
ing the Mobius function from a slightly different angle. They fixed the poset under
consideration (in their case, the Boolean algebra B,,) and studied the maximum value
attained by the Mobius function a over certain subsets of B,,. More specifically, if .77
is a family of subsets contained in the Boolean algebra B,,, then the max}- I ,u(f )I has

been found for three categories of families:
i. lower order ideals
ii. intervals of ranks
iii. arbitrary rank-selections.

The maxima are obtained by taking roughly the lower half, middle third, and every
other rank of B,,, respectively. The lower order ideal case was first solved by Eckhoff
[l2] and Scheid [l], and viewed in the context of the reduced Euler characteristic
by Bjorner and Kalai [8]. Niven [13] and de Bruijn [11] had previously solved the

arbitrary rank-selection case, while the interval of ranks case was a new result.

In this dissertation, we will address analogous extremal problems for 0,,, the
lattice of faces of the n-dimensional octahedron. More specifically, by extending the
techniques developed for B,, to 0,,, we find the extremal configuration for lower order
ideals is the lower two-thirds of the poset 0,,. In chapter 2, we state our conjecture for
the interval of ranks question. Our proof gives a complete answer when n 5 4(5) and

narrows down the answer to one of two possibilities for n aé 4(5). Also, we include

data supporting our conjecture. In chapter 3, we see that for arbitrary rank-selections
the extremal configuration is to take every other rank of 0,,. This is actually a simple
observation made by Stanley that the non-negativity of the coefficients of the cd-
index of 8,, and 0,, (proved by Purtill in his thesis) immediately imply the arbitrary
rank-selection result. In fact, Stanley’s observation applied to his new work on the
cd-index of face lattices of convex polytopes Lp also shows the Mobius function is
maximized for Lp by taking every other rank of the corresponding face lattice. In the
first half of chapter 4 we answer the interval of rank and arbitrary rank-selection cases
which were left undone in [15] for L,,(q), the lattice of subspaces of an n-dimensional
vector space over 0179. In both cases, the extremal configuration is to take the entire

poset. Finally, we complete chapter 4 by indicating our future research.

Chapter 1

Lower Order Ideals

In this chapter we will be concerned with maximizing |p(.77)l as f ranges over all

lower order ideals in 0,,. We first state the main result of this chapter:
Theorem 1.0.1 If}: is a lower order ideal in 0,,, then

[2.91 n
lu(f)| s I): (k)(—2)* I,

k=0

with equality occurring if and only if
P: = 0,,[k] with k = [233].

(Here [] denotes the greatest integer function.)

Before proving Theorem 1.0.1, we will first specialize f to be a rank-selected lower
order ideal, i.e., a lower order ideal of the form 0,,[lc] U {0}. We show in Lemma 1.2.1
that |u(0,,[lc])| is maximized if we take k to be [2%], i.e. the lower two-thirds of
0,,. Once we generalize .7: to be any lower order ideal in 0,,, we will see the ideal

0,,[[-25'1_]] U {0} is also the maximal configuration for Theorem 1.0.1.

7

8

1.1 Elementary Properties for 0,,

We begin by determining the Mobius value p of elements from 0,, and rank-selected
lower order ideals from 0,,. For the most part, these results follow from known
properties of the lattice 0,,, the definition of the Mébius function, and the product

theorem for the Mobius function.

The most important result we establish in this section is a recurrence for the
u(0,,[lc])’s (Corollary 1.1.5). We do this via a “reduced Euler characteristic” interpre-
tation of the Mobius function. This recurrence, in its absolute value form (Corollary
1.1.7), allows us to quickly narrow down the possibilities for the maximum of the
Mébius function for rank-selected lower order ideals. The summation formula for the

u(0,,[lc])’s allows us to sharpen and complete the argument for Theorem 1.0.1.

Let us first determine the M6bius value of elements from 0,,.
Proposition 1.1.1 Let a: be an element of 0,, \ I with rank 1:. Then ”(23) = (—1)".

Proof. First note that

r—u

0,,\ Squ-xli,

V
n

 

where V is the poset with Hasse diagram
+1 -1

V=V.

0

This holds because of the following order-preserving bijection. Define 1) : 0,, — 1 —»

yX...bey

v

n

 

xi——H'i=(vl,...,v,,)

where
+1, if i E a:
v; = -1, If —i E 12

0, if i,—i ¢ 2:.

9

Let a: = 2:1, . . . , at], be an element of rank k in 0,, — 1. Using the bijection 17 between

0,, — I and Y x - - - x I: and the product theorem for the Mobius function [17, Prop.

 

v

3.8.2], we obtain n

#o.-i(w) = qu-..xv(n(x))

= #V(0)”'*#V(i1)k,

where the elements 0, +1 and —1 correspond to the labeling of V. Noting [ti/(0) = +1

and uv(+l) = pv(—l) = —1 gives the result. D

We are able to express p(0,,[k]) in two ways: in terms of a summation formula

(Corollary 1.1.2) or a recurrence (Corollary 1.1.5).

Corollary 1.1.2 The following summation formula holds for p(0,,[k]):

I:

now) = —( )3 (’J?)(—2)J' ). o s k s n.

i=0

Proof. Use Proposition 1.1.1 and the fact there are (2)21. elements of rank j in 0,,.

D
Corollary 1.1.3 u(0,,) = (—1)"+‘, n 2 1.

Proof. It is enough to observe u(0,,) = p(0,,[n]) (recall 1 has rank n +1 in 0,,). The
result then immediately follows once we apply the binomial theorem to the summation

expression for p(0,,[n]) given in Corollary 1.1.2. B

Combining Proposition 1.1.1 and Corollary 1.1.3 yields the following:

Proposition 1.1.4 Let a: be an element of 0,, with rank 1:. Then [1(33) 2 (—1)’°.

10

Corollary 1.1.5 The u(0,,[k]) ’s satisfy the recurrence

#(Onlkl) = -2u(0n-1[l~‘ - 1]) + #(On—llkl),

where n 2 2, 0 < k < n, with boundary conditions

u(0,,[0]) = —l for n 2 0

and

u(0,,[n]) = (—1)"+1 for n 2 1.

We have two different proofs of this recurrence. The first applies the interpretation
of the Mobius function as counting certain chains in a poset. The second is a direct

application of the summation formula for p(0,,[lc]) and induction.

Before beginning our first proof, we briefly review the aforementioned interpreta—
tion of the the Mobius function. For P a bounded poset, we let c,- = c,-(P) denote
the number of chains of length i in P \ {0,1}. Here a chain of length i is a totally

ordered subset containing 2' + 1 elements.
A well-known result [17, Prop. 3.8.5] which relates chains with the Mobius func-
tion is

p(P)=—1+co—c1+c2—c3+... (1.1)

We are now ready to use this formulation of the Mébius function.

Proof 1. Let

a,- = # of chains of lengthj in 0,,_1[k — 1]
b, = # of chains of lengthj in 0,,_1[lc]
c,- = # of chains of length j in 0,,[lr].

11

We will refer to chains of “type c,” to mean those chains of length j in 0,,[k]. Similar
terminology will be used for a,- and bj. Using equation (1.1), we can translate the

recurrence in terms of chain notation, i.e.,
—1+Co—C1+Cg—... = —2(—1+ao—al+a2—...) + (—1+bo—bl+bg—...) (1.2)

Regrouping the terms on the right side of equation (1.2) above gives

—1+co—c1+c2—...=—1+(2(1)+bo)—(2ao+b1)+(2al+b2)—(2a2+b3)+... (1.3)

The chains of type c, : .131 < 32 < < $j+1 consist of those chains of length j in

0,,[lc]. They belong to one of the following four classes:

(i) neither {+n} nor {—n} E x,- for any i
(ii) 3:1 = {+n} (“the chain starts with {+n}”)
(iii) 2:] = {—n} (“the chain starts with {—n}”)

(iv) all other remaining chains not accounted for in (i), (ii) or (iii).

If we let d,- denote the cardinality of the last category (iv) of chains, then we claim

Ci = bi + a,-, + a,_, + d,
= bj+20j_1+dj, (1.4)
with the convention that a..1 = 1 counts the number of empty chains in 0,,_1[k — 1].
Clearly the chains of type b,- and category (i) have the same cardinality via the identity

map. The collection of chains starting with {+n} in 0,,[lc] has the same cardinality

as the type a j._1 chains by defining a natural bijection 11 between these two sets. Let

c: {+n}=:c1<:rg<...<.r,-+1

be such a category (ii) chain. We have n E x,- for all i, so we can map c to the chain

u(c): 2:2 \ {+n} < < 1:,“ \ {+n},

12

which is a type aJ-_1 chain. Conversely, if

E: y1<...<y,-

is a chain of type a,_1, map it to the chain
V'l(6): {+n} < y1 U {+n} < . . . < y,- U {+72}.

-1 1

Clearly, y 011 and you‘ are the identity maps on category (ii) and type a j-1 chains,
respectively, so these two collections have the same cardinality. We can similarly show
the cardinality of category (iii) chains equals aj_1 by uniformly replacing “+n” by

“—n” in this argument.

Substituting equation (1.4) for each of the c,- ’s appearing in the left side of equation
(1.3), we see that all the terms on the right side of equation (1.3) cancel out. The
remaining terms consist of an alternating sum of the dj’s. Hence the corollary will

follow once we have shown this alternating sum equals zero, i.e.

do—d, +d2—d3+...+(—1)""d,._1 =0. (1.5)

To complete this argument, we will construct a bijection A between certain chains
of type d,- and type dj-H, according to where {in} first occurs in each type of chain.
Here in stands for either +n or —n (but not both), depending upon which occurs in
the chain. An important observation to make is that if an < < 32,-“ is a chain of

length j in 0,,[k], then rank 2:,- 2 i.

Let {1,-,0 denote the cardinality of those type d,- chains :01 < < 23,-.” in 0,,[k]
with the property that if an, is the least element in the chain containing in then
2:}, = $5-1 U {in}. Let did be defined similarly, except that as), I) 35.1 U {in} (strict
containment). For h = 1, we let (to = 0. Note that d,- = dj’o + de for all j. From the

definitions of djp and de, we easily derive the following two properties:

13

(i) (10.0 = 0
(ii) (1,-” = 0.

Property (i) holds by virtue of the fact that type do chains do not include the chains

 

+71 or —n. Suppose property (ii) does not hold, i.e. dk_1,1 > 0. A typical type dk_1,1

chain looks like

yl <...<yh-1 <yhU{:l:n} <yh+1U{in} <...<ka{in}

with y}, at y),_1. But then

311 <---<yh-1<yh<yh+1<---<yk

is a chain of length It — 1 (all the y,’s are distinct). Thus rank y], 2 It implies rank
(31;, U {in}) _>_ k + 1, contradicting the fact that y], U {in} is an element from 0,,[k].

Hence property (ii) holds.

Next we show that the identity

din = dj+1.o (0 Si S k — 2) A (1-6)

holds. We define the map A : type d“ chains —* type dj+l,0 chains by

$1<...<$},_1 <xh<...<:r,-+1+-—+:r1 <...<:c;,_1<:c;,\{:t:n}<xh<...<xj+1

where h is the first position where in occurs in a type d,“ chain. We define the

inverse map A’1 : type dj+1,o chains ——t type d,“ chains by
y] < <y;,_1 <y;, <yh+1 < < yj+2i—iy1 < <yh_1 < yh+1 < <yj+2

where h + 1 is the first position where in occurs in a type d144,.) chain. It is easy to
check A"1 o A is the identity on type d“ chains and A o A’1 is the identity on type

dj+1’o chains, so A is a bijection.

14

Since d, = dip + dJ-J, the alternating sum of dj’s in equation ( 1.5) simplifies to
verifying

d0,0 + (—1)k-1dk-1,l = 0a

which is indeed true by properties (i) and (ii).

Finally, the first boundary condition holds since

”(040D = —(#o..(0))

= —l.

The second boundary condition holds by virtue of the fact u(0,,[n]) = u(0,,), which
equals (—1)"+l by Corollary 1.1.3. D

Proof 2. We first substitute the summation formula for u(0,,[lc]) given in Corollary
1.1.2 into the expression —2u(0,,-1[k — 1]) + u(0,,-1[k]). After shifting the index
of summation in the sum corresponding to —2u(0,,-1[k — 1]) and breaking off the

j = 0th term from the sum corresponding to p(0,,_1[lc]), we obtain

22(7) ,.>:,(";1)<-

—Z:2(’}:,1)(—2)’-§5(";1)(—2)j—1.

1:1 j=1
(1.7)

—2fl(0n_1[k — 1]) 'l’ P(0n-l lkl)

Using the facts (’i) = (2") + ("71) and (3)(—2)° = 1, we combine the three terms

J 1-1 J

on the right side of equation (1.7) to get

-2#(0n-1lk — 11) + ”(0mm = — {3((7 ' 1) + (” T 1))(_2),. — (3)(—2)°

15

which equals p(0,,[lc]) by Corollary 1.1.2. D

An easy result that we will need in order to complete the proof of Theorem 1.0.1

is the following corollary:

Corollary 1.1.6 I'Vhen k is odd u(0,,[k]) is positive and when k is even p(0,,[k]) is

negative (n 2 1, 0 S k S n).

Proof. The proof proceeds via induction on n and applying the recurrence for
p(0,,[lc]) described in Corollary 1.1.5. By the boundary conditions from Corollary
1.1.5, we have p(0,,[0]) = —1 and p(0,,[n]) = (-1)"‘“, the latter being positive for
n odd and negative for n even. In particular, the result holds for n = 1. Now assume
n > 1. We have handled the case for k = 0 or n, so now we will consider 1 S k S n— 1.
If It is odd, then by the induction hypothesis p(0,,-1[lc—1]) is negative and p(0,,-1[k])
is positive. Hence the recurrence given in Corollary 1.1.5 implies u(0,,[lc]) is positive.

A similar argument demonstrates u(0,,[lc]) is negative for it even. 0

Putting Corollaries 1.1.5 and 1.1.6 together, we see that the |p(0,,[k])|’s also

satisfy a recurrence.

Corollary 1.1.7 The |p(0,,[k])| satisfy the recurrence

lu(0n[kl)| = 2lll(0n—1lk -1])|+I#(0n-1[kl)l

with boundary conditions

l#(0n[01)| =1 for n 2 0

and

[p(0,,[n])| =1 for n 2 1.

16

1.2 Rank-Selected Lower Order Ideals

Before we determine the extremal configuration for |p(}')l, .7: an arbitrary lower
order ideal, it is natural for us to first study “simpler” ideals. In particular, we study

ideals .77 which are rank-selected lower order ideals, i.e. lower order ideals of the form

r = 0,,[lc] u 6.

In order to state a special case of the main theorem of this chapter, we make a
few more definitions. We say a sequence a0, a1, . . . , a,, of real numbers is unimodal if

for some It, 0 S k S n, we have

aoS...Sak>...>a,,.

Similarly, a sequence is strictly unimodal if we replace the inequalities by strict in-
equalities in the definition of unimodal. Finally, a sequence a,, . . . , a,, is almost strictly

unimodal if the sequence is strictly unimodal or is of the form

a, <02 < <ak=ak+1 >ak+2 > >a,,.
We are now ready to state a rank-selection lemma:

Lemma 1.2.1 For fixed n 2 2, |p(0,,[lc])| is strictly unimodal with unique maximum

occurring when lc = [27"].

Proof. The proof for rank-selected lower order ideals proceeds by induction on n.
By the recurrence for |u(0,,[lc])|, we quickly conclude the sequence {|u(0,,+1 [k])|}2:(1,
is almost unimodal and narrow down its maximum to one of two possibilities. We
will complete the argument by considering the equivalence class of n modulo 3 and

apply the summation formulas and recurrence relation for p(0,,[lc]) determined in the

previous section.

17

Table 1.1: [p(0,,[lc])| for n = 2,3,4

 

 

 

 

 

k=12 3 4
n=2 3100
3 5 710
4L71715‘1

 

For n = 2,3, and 4, the lemma is easily checked to be true. Refer to Table 1.1.
Fix n and let lc" be the index It for which |p(0,,[lc])| is a maximum. By Corollary

1.1.7 [p(0,,[lc])| satisfies the recurrence
|#(0nl’€l)| = 2|}!(0n-1llc —1l)|+ |/1(0n—1[kl)|- (1-8)

By the induction hypothesis the sequences {u(0,,[lc])}',§;, and {p(0,,[lc])}2=," are
strictly increasing and decreasing, respectively. Applying the recurrence to these

monotone sequences, we conclude the sequences
{ |u(0n+1[kl)| it; (1-9)

and

{ |It(0n+ilk])| Hit-+1 (1.10)

are strictly increasing and strictly decreasing, respectively. Thus, equations (1.9)
and (1.10) imply we have pinned down the index lc corresponding to the maximum
Iu(0,,+1[lc])| as one of two possibilities: k" or k“ + 1. A case-by-case argument using
the equivalence class modulo 3 of n and applying the summation formula for u(0,,[lc])

will give the result.

For ease in notation, let

at = |#(0n-1[kl)|

bk : l/‘(On lklll

18

CI: = lfl(0n+1lkl)l-

We first suppose n E 1(3). Since n + 1 5 2(3), we wish to show

Ck0+1 > Ck. .

Applying the recurrence (1.8), it suffices to show

2bk° + bk°+1 > 2bk°-1 + bk‘a

i.e.

51,0 > 2bk0_1 — 01,-1.1.

The summation formulas given in Corollary 1.1.2 and the fact n :— 1(3) enable us to

rewrite this as

bk' > bk‘-l + (bk-1 — bin-1)

PM it .
= bk°-1 + Z (.)(—2)Ja

j=k° 3

since lc“ is even. By the induction hypothesis we have bk. > bk-_1. If we can show

:1} (;)(—2)j is negative, then we will be finished. Write n as 3m + 1. Then

lc" = [339-] = 2m. Thus
k.“ n J- _ 3m+1 2m 3m+1 2m 1
Z (1')”) " ( l”) + (2m + 1)(_2) +

j=k. 2m

(3m+1)!( 2m[ —1 [
(2m)!m! _) (m+l)(2m+1) ’

 

which is negative, as desired.

Next we consider n E 2(3). Since n + 1 E 0(3), we wish to show

cko+1> Cko. (1.11)

19

Using the same method as in the case for n E 1(3) (and noting lc‘ is now odd), we

can rewrite equation (1.11) as

k'+1 n _
bk' > bk°—l - 2 (j)(-2)J-

j=k°

By the induction hypothesis we have bk. > b1..-“ so it remains to show 2:3} (3‘) (—2)j

is non-negative. If we write n as 3m + 2, then lc“ = [27"] = 2m + 1. Thus

k.

j=k. j (2m+1)!ml m+1 2m+2
= O.

 

 

Note the above calculation implies
019-1 = bk0+1 for n 5 2(3). (1.12)
We will need this result for the next case.
For n E 0(3) and n + 1 E 1(3), we wish to show

Ck°+1 < Ck' ,

01‘

bk. < 2bk0-1 - bko+1. (1.13)
Rewriting equation (1.13) in terms of elements from the n — lst row, we have

2ak°-l + ak' < 2 (2611..-: + ak°-1)"‘(20k° + “Iv-H),

i.e.

01:04.] < 4(1ko_2 — 30kt. (1.14)

Observe n — l E 2(3), so by equation (1.12) we conclude a,,--2 = a». (Recall here

that the index k“ is the index of the maximum in the nth, not the n — lst, row. The

20

index corresponding to the maximum in the n — lst row is k“ — 1.) Hence equation

(1.14) becomes

ak‘+t < a»,

which holds by the induction hypothesis on the n —. lst row. [3

1.3 Arbitrary Lower Order Ideals

In this section we give the proof of Theorem 1.0.1. To do so, we develop the notions
of the shadow A(S') and the dual shadow V(S') of elements 5' of a fixed rank from 0,,.
Using bipartite graph arguments, we obtain estimates for A(S) and V(S) reminiscent

of Bollobas’ work on shadows for hypergraphs [10].

For the proof of Theorem 1.0.1 we suppose we have a lower order ideal .7: Q 0,,
which maximizes |p(.7-')|. By the shadow lemmas we find bounds for the “shape” of
.7. Next we find rank-selected lower order ideals contained in .7: and containing .7". A
lemma due to Baclawski [2, Lemma 4.6] and independently to Steékin [20] enable us
to “peel off” elements from these ideals. Hence, we are able'to compare the Mobius

values of these configurations with .7: and complete the proof.

Suppose we are given elements 5' all of the same rank in a poset. Since we are
working with lower order ideals, we would naturally like to be able to estimate the
number of elements in the poset covered by S. More formally, we define the shadow

of a subset S of rank r in 0,, by

A(S) = {B E 0,,(r — 1) : B Q Afor some/1 E S}.
We then have an inequality involving [13(5)] and [5].

Lemma 1.3.1 (Shadow Lemmafor 0,,) US Q 0,,(r), where r 2 313113, then |A(S)I 2

[S] with equality only when n E 2(3) and S = 0,,(315'3).

21

Proof. For the inequality we utilize an edge-counting argument. Consider the bipar-
tite graph G formed in the Hasse diagram of 0,, by S and A(S). Each vertex A E S
has degree r, so the graph G has exactly rISI edges. Also, every vertex B E A(S') has
degree at most 2(n — r+1), so the number of edges in G is at most 2(n — r +1)|A(S)|.
Thus ’

7‘ISI S 2(n - r +1)|A(5)|,

i.e.
n-r+ 1)

 

ISI 5 2‘ |A(S)I.

Thus when r > 2—"53, the first part of the lemma follows.

If n E 2(3) and r = 3131—2, then the above argument works as long as some vertex
in A(S') does not have degree 31:3. If every vertex B 6 A(S') has this degree, then
in 0,, the vertices of A(.S') are only adjacent to vertices of S (and vice-versa). Hence
if S' C 0,,(r) (strict containment), this would contradict shellability of the chain
complex of 0,, ([5], [7]). (See Section 2.1 for information about shellability and the

chain complex.) B

In an analogous manner, we define the dual shadow of S, where S is a subset of

rank r in 0,,, by

V(S')= {BE 0,,(r+1): B2 Afor some/16 S}.

We also have a dual shadow lemma for 0,,. Since its proof is virtually identical to

that of Lemma 1.3.1, we shall simply state the result.

 

Lemma 1.3.2 (Dual Shadow Lemma for 0,,) US 9 0,,(r) where r S “34, then
IV(S)I Z [S] with equality only when n E 2(3) and S = 0,,(3”3—"1-). Cl

Now we are ready to give a proof of Theorem 1.0.1. Let .7: g 0,, be a lower order

ideal with maximum |p(f')| and let it be the maximum rank of an element in T. We

22

will first derive some expressions that will enable us to compare u(.77) with p(.’F[lc— 1])
and u(.7"[k — 2]), yielding an upper bound for k. The Shadow Lemma for 0,, and the
following proposition enable us to do this. Here max P denotes the set of maximal

elements of the poset P. Recall that for P a bounded poset, P = P \ {0,1}.

Proposition 1.3.3 [2, Lemma 4.6] [20] Let P be a bounded poset. IfT Q max P then
up) = MP \ T) — 2: #(0. x). (1.15)
267'

This result follows by counting the chains in P not containing elements of T and the
chains in P containing elements of T. Proposition 1.3.3 is useful in the sense that it
enables us to see how the Mébius function of a poset changes if we “peel off” some

(or all) of its top elements.

Applying equation (1.15) to P = .7, T = .77(lc), and recalling p(0,:r) = (—1)k for

a: E 0,, of rank It gives

#(f) = #(flk -1])-(-1)"lf'(k)l,

01‘

#(flk-1])= #(f')+(-1)"lf(k)l- (1-16)

Similarly applying equation (1.15) to P = .7:[k — 1], T = .7:(lc — 1), substituting for
,u(f[lc — 1]) in equation (1.16), and solving for u(.7-'[k — 2]) gives

#(f'lk - 2]) = #(f) - (-1)"(|}'(’c -1)l - l-7"(k)|)- (1.17)

Since .7 is a lower order ideal, we have Af'Uc) Q .77(lc — 1), so

|f(k —1)|-IA.7-‘(Ic)| 2 o.

23

Suppose k > [354]. By the Shadow Lemma 1.3.1 we know

lAf(k)| > WHI-

Hence

If'(lc—1)|—|f(k)| > 0.

After considering all the possibilities for the sign of p(.7") and the parity of k, we see
one of equations (1.16), (1.17) implies Iu(}')| is not a maximum, contradicting the

fact that .7 Q 0,, is an idea] with maximum |p(f)|. Hence I: S [23”].

We will now work with the Dual Shadow Lemma to extract further information

about the structure of .7". Let

f°={B: Beon\f}

and define

I = min{rank(B): B E fc}.

Form g = .7: U f°(t’) and ’H = Q U ff“ + 1). As before, we apply equation (1.15)
first to P = g, T = f°(€) and then to P = 'H, T = .776“ + 1) to obtain equations

resembling equations (1.16) and (1.17):
#(9) =It(-7") -(-1)‘|F(€)| (1-18)
#(H) = #(f)+(-1)'(|-7°(€+1)|-|~7"c(")|)- (1.19)

Now Vfcu) <_: .7-‘°(t +1), implying [me +1)| — IVfc(t)| 2 0. Suppose e < 2'1—3-1.

We apply the Dual Shadow Lemma 1.3.2 to conclude

If‘(€ +1)| — |f°(€)| > 0.

24

Once we consider all the possibilities for the sign of p(}') and the parity of t, we see
that one of equations (1.18), (1.19) implies |u(f')| is not a maximum. Hence we must

have t 2 2—"§—‘.

To finish this argument, we reason in the following manner: for each equivalence
class of n modulo 3, the bounds for lc and I will enable us to find rank-selected lower
order ideal configurations containing .7: and contained in .77, respectively. As before,
we will apply equation ( 1.15) to obtain expressions for the Mébius function of these
two lower order ideal configurations, apply a parity and sign argument, and then the

rank-selection Lemma 1.2.1 to derive the required result.

By definition of k and t’, we have k 2 t’ — 1. We first consider the case n E 0(3).

We have

kze—1z%—1,

and from before

implying

For convenience, let r = 33“. Then we have

0,,([r —1])g 7? g 0..([r]),

where the first containment follows from the definition of t and its bounds, while the
second from the definition of k and its bounds. Note that r is even in this case, so by

equation ( 1.16) we have

#(Onlr -1]) = #(7’) + |~7"(r)|- (1-20)

25

By the same token, equation (1.18) becomes
#(Onlt‘l) =14?) - |0n(r)\}'(7‘)|- (121)

If u(.7-') > 0, then equation (1.20) and the maximality of |u(.7-')| imply .77(r) = 0.
Hence ? = 0,, [r — 1] = 0n[[%"] - 1], contradicting the rank-selection Lemma 1.2.1.
Otherwise u(f') < 0, so equation (1.21) plus the maximality of |,u(.7:)| imply 0,,(r) =
.T(r). Thus If = 0,,[r] = 0,,[[2—;—]], as desired.

Suppose n E 1(3). Again, by the inequalities derived for lc and f and their

definitions, we obtain

 

 

 

 

1
leaf—122,1;- —1andlc_<_2n;1,
implying
2. 1 2 1
k: n;- or n; —1.

Letting r = Eff—l, we have

0n([" - 1]) Q 77' E 0n(l7‘l)-

Notice r is odd in this case, so again equations (1.16) and (1.18) reduce to

#(Onlr -11) = #(f') - |f(r)| (1-22)

and

#(Onlrl) = #(f') + l0n(r)\.7"(r)l- (1-23)

If p(}') > 0, then equation (1.23) and the maximality of |u(f')| imply 0,,(r) = .7:(r),
so P = 0,,[[%”] +1], contradicting Lemma 1.2.1. If u(.7:) < 0, then equation (1.22)
and the maximality of Iu(.7:)l imply 7(r) = 0. Thus k = r — 1 and IP = 0,,[[2—;4]], as

desired.

 

26

Finally, suppose n E 2(3). We have the bounds

 

 

 

 

 

 

2 —l 2 2
k2 " —1andkS "3+, (1.24)
implying
2n —1 2n —1 2n —1
lc = — .
3 l, 3 or 3 +1
Letting r = “3‘1 we have

0n([r —1])§ .7- <_: 0n([r +1]).

Suppose I: = r + 1. We will see that this will lead to a contradiction. The choices for
lc will then reduce to r - 1 or r, and the remainder of the argument will proceed as

in the n E 0(3) and n E 1(3) cases.

Since r is odd in this case, equations (1.16) and (1.17) become

#(firi) = M) + |f(r +1)| (1.25)

and

”(our - 11) =14?) + lflr +1)| — Iflrn. (1.26)

If u(.7-') > 0 then equation (1.25) and the maximality of |p(.7")| imply .77(r + 1) = 0,
contrary to our assumption on k. Thus ”(f) < 0. However, recall that the Shadow

Lemma applied to S = f (r + 1) has

lflr +1)| S IAN" +1)| S lf(r)l,

implying the difference If (r + 1)] - |f(r)| S 0. If the difference is negative, this
contradicts the maximality of Ip(.77)]. If the difference is zero, then (by the Shadow

Lemma again) f'(r + 1) = 0,,(2—'§fl). So P = 0,,[2—"3fl], contradicting Lemma 1.2.1.

27

The present situation is k is r — 1 or r, so we have

0n(lr — 1]) S; 7- Q 0n(lrl)

Since r is odd, the same reasoning as in the n E 1(3) case shows that equations (1.22)
and (1.23) continue to hold. Now if #07) < 0, equation (1.22) and the maximality of
Ip(.7)| imply .7(r) = 0. Thus T = 0,,[r — 1] = 0n[['2;_;lJ - 1], contradicting the rank-
selection Lemma 1.2.1. Therefore, [1(f' ) > 0, so the maximality of |u(.7-')[ implies
0.0") \ fl") = 0. i-e. 7 = 0an] = 0,.[L'%‘J].

We thus conclude the extremal configuration occurring in Lemma 1.2.1 coincides

with the extremal configuration for Theorem 1. B

Table 1.2 displays the extremal configuration and the Mébius values of the lower

order ideal case for 0,,, n = 1,... ,25.

Table 1.2: Lower Order Ideal Extremal Configuration for 0,,, n = 1,. . .,25

 

 

 

 

 

 

 

Extremal
n Configuration .7" |p(0,, (.77))I
1 041] 1
2 02m 3
3 0312] 7
4 0.42] 17
5 05[3] 49
6 0.,[4] 129
7 07 [4] 351
8 0.,[5] 1023
9 09[6] 2815
10 0,0[6] 7937
11 0n[7] 23297
12 0,2[8] 65537
13 0,3[8] 187903
14 0149] 553983
15 0.5[10] 1579007
16 0,6[10] 4571137
17 0,7[11] 13516801
18 0,8[12] 38862849
19 019[12] 113213439
20 0,0[13] 335478783
21 021[14] 970522623
22 022[14] 2839740417
23 023[15] 8428126209
24 02.1[16] 24494735361
25 025[16] 71904919551

 

 

Chapter 2

Interval of Rank-Selections

In this chapter we are interested in maximizing |u(0,,[i,j])| where [i, j] Q [n] is
an interval of ranks from 0,,. To do this, we will translate this problem to one of
enumerating a certain class of permutations. A special edge-labeling of the poset 0,,,

called an R—labeling, enables us to perform this conversion.

The main result we will prove in this chapter is the following:

Theorem 2.0.4 For intervals of rank-selections [i,j] Q [n] of 0,,, where n > 0 is

fired and n 74 2, [p(0,,(S))[ achieves a maximum at one (or‘possibly both) of

 

 

 

2—”, 4” {,5} [2—"51—5, 4—”] when n: — 0(5)
:irglfl,215;4:,[_n_5-L3, -451 when n= _ 1(5)
5: 2—"51—1, ‘—”5"3 [2—"5*§,fl‘i2: whennE2(5 )
3311,5—"5'2 2%, 44%;; when n E 3(5)
:3—5'153, inf—1 when n E 4(5).

 

For n = 2, the maxima occur when

5: [1,1].» [2,2].

We conjecture that the following result is true.

29

30

Conjecture 2.0.5 For intervals of rank-selections [i,j] Q [n] of 0,,, where n > 0 is

fixed and n 94 2, |p(0,,(S'))| achieves a unique maximum when

s 5131—5114—9111.

For n = 2, the maxima occur when

S = [1,1] or [2,2].

In section 3 we provide numerical evidence to support this conjecture.

We will return to the concept of edge-labelings, specifically EL- and CL-labelings,

in the next chapter.

2.1 Edge and Chain Labelings

In order to motivate the importance of edge and chain labelings, we first briefly
develop the notion of shellability of complexes. This topological condition implies
a certain result about simplicial homology. We will see that CL-shellings and EL-
shellings of order complexes are each combinatorial conditions which imply shellability

of the order complex.

We follow [6] for all notation and terminology related to shellability and homology.
A simplicial complex A is a collection of subsets of a finite set V (called the vertex

set) such that

(i) ifFEAandGQFthenGEA
(ii) ifvEVthen {v}€A.

All the complexes we will work with will be nonvoid, so 0 E A. The members of

A are called simplices or faces, while the maximal faces of A are called facets. The

31

dimension of a face F E A is [F | — 1, while the dimension of a complex is

dimA=max {dimF: FE A}.

A complex is pure is all of its facets are equicardinal.

Let A be a pure simplicial complex. A shelling of A is a linear order F1, F2, . . . , F,

of the facets of A satisfying the following condition:

Given facets F,- and F ,- with i < j, there exists a facet F], with k < j such

that Fgfl F,- Q FknFj, where [PkflFjI = dim A— 1.

We call a complex shellable if it admits a shelling. If F“. . . ,F, is a listing of the

facets of A in a shelling order, let

A,-={GEA: GQkaorsomekSi}

and let

R(E)={I€F.': Fi\-’BEAi—l}

be the restriction of F}.

We next review simplicial homology and homology of a shellable complex. Let
A be a simplicial complex of dimension d on the vertex set V. Assume that V has
been given some linear order. Hence, if F = {vo,v1, . . . ,vk} is a nonempty face of
dimension It in A, we will write it as [v0, v1, . . . ,vk] if v0 < v, < . .. < v), with respect
to the linear ordering of V. Let Ck(A) denote the free abelian group generated by
the set of k-dimensional faces of A written in canonical form. Notice that 0-1 E Z

and Co(A) E 2'”, where Z denotes the integers. Define the boundary operator

0),: Ck(A) -t Ck_1(A)

32

by
l:
8k[vo, v1, . . . , v1]: z(—1)“[vo, v1, . . . , 13,-, . . . , vk].
i=0

(Here :13; means delete the element x,.) One can verify that 8;, 0 3H1 for all k E Z.

The kernel of the boundary operator 8;, forms a group Zk(A) called the group of
k-cycles, i.e.,

Z401) = (P 6 04(13): (91:00) = 0 )-
Let B,,(A) be the group generated by the image of 614,1,
EMA) = (0 E 0,,(A): 0 = 5m“), T E 0,,,,(A) ),

called the group of k-dimensional boundaries. Notice that B,,(A) Q Zk(A) for k E Z.

The reduced homology groups are the quotient groups defined by

HklA) = Zk(A)/Bk(A)-

We call a complex A acyclic over Z if BAA) = 0 for all k E Z.

An important result about the reduced homology of a shellable complex is the

following:

Theorem 2.1.1 [6, Theorem 7.7.2] Let A be a shellable d-dimensional complex with

facets .7". Furthermore, suppose
{FEfz 72(17): F} = {F1,...,F,},

where ’R(F) is the restriction operator induced by some shelling. Then

Mali :3.

Also, there are cycles 1),, . . . ,p1 E BAA) uniquely determined by
1 j = I:

0 otherwise.

Pk(Fj) = {

Finally, {p1, . . . ,p,} is a basis of the free group BAA).

33

For P a poset, we can define a simplicial complex A(P) called the order complex.
We take the vertices of A(P) to be the elements of P and the faces of A(P) to be

the chains of P. Notice that the facets of A( P) are simply the maximal chains of P.

If P is a finite graded poset, we say it is shellable if its order complex A(P) is
shellable. It would be useful to have a combinatorial criterion to show that the order
complex of a poset is shellable. The concepts of EL-labelings and CL-labelings each

imply shellability of the order complex.

Let P be a finite graded poset. An edge-labeling of P is a map A : {(x, y) E P x P :
x -< y} —> A, where A is some poset (usually the integers). We say an unrefinable
chain

xo-<x1-<...-<xk

in a poset with edge-labeling A is rising if

A(30,$1)S A(11,$2)S . . . S A(Zk-1,$k).

An edge labeling A of a poset P is called an R-labeling if for every interval [x, y]
in P there is a unique rising maximal chain c in [x, y]. Furthermore, we call an R-
labeling A an EL-labeling (edge lexicographical labeling) if this unique rising maximal
chain c is lexicographically least among all other maximal chains in [x, y]. A graded
poset that admits an EL-labeling is said to be EL-shellable (edge lexicographically
shellable).

Using the labeling of the elements of 0,, in section 0.1, we see that 0,, has a very

natural R—labeling:

Proposition 2.1.2 Let 0,, be the lattice of signed subsets of the elements [n] ordered

by inclusion with 1 adjoined. If we label each edge (x,y) E 0,, by

17.,y>={g,\2 33:;

34

, then A is an R-labeling of 0,,. In fact, this A is also an EL-labeling of 0,,, so 0,, is
EL-shellable.

Proof. We first observe the edge-labeling A of 0,, is well—defined, for if x «< y with
y 791, then Ix] + 1 = lyl. Hence y \ x is a single integer. For x -< y =1 in 0,, (i.e. x

is a coatom of 0,,), the edge (x, y) is labeled by the integer 0.

Notice that any maximal chain in the interval [x, y], y ;£ 1, is labeled by a sequence
of integers in the set {y\x}. Hence, the unique rising maximal chain c in [x, y] consists
of the elements of y\x ordered with respect to the natural order of the integers. (Here
we are interchangeably thinking of a maximal chain in [x, y] as a set of labeled edges

from x to y.)

For y = l and x = {1:1, . . . ,xk} of rank 10 S n, any maximal chain in [x,y] = [x, 1]

is labeled by some signing of the n — k + 1 elements
{0} U [n] \ {|x1|, . . . , kal} = {0} U {21, . . . ,z,,_k}
with 21 > 22 > . .. > z,,_;,. Hence, the unique rising chain c is
c: x < xU{—zl} < xU {—zl,—22} < < xU{—zl,...,—z,,_1,} < 0.
By construction, this chain is lexicographically least among all other maximal chains
in the interval [x, 1], so A is in fact an EL-labeling of 0,,. D
The Boolean algebra has a well-known R-labeling.

Proposition 2.1.3 Let B,, be the lattice of subsets of the elements [n] ordered by

inclusion. If we label each edge (x,y) 6 B,, by

A(3:11,) : y\x,

then A is an R-labeling of B,,. In fact, this A is also an EL-labeling of B,,, so 8,, is
EL-shellable.

35

Let P be a graded poset of rank n. Let

£‘(P) = {(c,x,y): c is a maximal chain of P, x,y E c and x 4 y}.

A chain-edge labeling of P is a map A : £‘(P) -+ A, where A is some poset (usually

the integers), satisfying the following condition: if c and c’ are two maximal chains

inP
c 0=xo4x14...4x,,=1
c’ 0=x64x',4 4x],=1

whose first d edges coincide, then the corresponding labels must also coincide along

these d edges, i.e.

A(c,x,_1,x,-) = A(c’,x:-_,,x') for i = 1,. . . ,d.

Suppose we have assigned a chain-edge labeling A to P. Let [x,y] be an interval
in P with I: = p(x,y) and r : 0 = r0 4 r1 4 - - - 4 rp(,) = x be a saturated chain from
0 to x. We call the pair ([x,y],r) a rooted interval with root r, denoted by [x, y],. If
e : x = x0 4 x1 4 . . . 4 x1, = y is a maximal chain in [x, y],, then it has a well-defined

induced labeling given by
A(C, xi-li (17,) = A(ma $p(x)+i-—1a xp(x)+i)a Z: 1, - - ° 1 k)

where m is any maximal chain in P containing r and c. We say the maximal chain c

in a rooted interval [x, y], is increasing if

A(c,xo,x1) < A(c,x1,x2) < < A(c,xk_1,x;,).

A chain-edge labeling A is a CL-labeling (chain lexicographical labeling) if for

every rooted interval [x,y], in P: (i) there is a unique increasing maximal chain c

36

in [x,y],, and (ii) for any other maximal chain c’ in [x,y],, c is lexicographically
least. Any graded poset which admits a CL-labeling is called CL-shellable (chain

lexicographically shellable).

From the definitions it is easy to see that if P is EL-shellable then it is CL-
shellable. A theorem of Bj6rner links the ideas of EL-shellability, CL-shellability and

shellability.

Proposition 2.1.4 [5, Theorem 2.3 ] For P a graded poset we have the following
implications: P is EL-shellable => P is CL-shellable => P is shellable.

Using recursive atom orderings (a concept equivalent to CL-shellability), Bjérner and

Wachs proved the following theorem:

Theorem 2.1.5 [9, Theorem 4.5] Let P be a convex polytope and Lp be its lattice of
faces. Then Lp is CL-shellable.

We will need this result for the proof of Theorem 3.0.8.

2.2 Augmented Signed Permutations and Rank-
selections

Given the R—labeling of 0,, described in section 1, we can use this to convert the
statement of Conjecture 2.0.5 to one of enumerating augmented signed permutations
of the integers [n]. Before doing this, we first recall some known results about R-

labelings and the Mébius function of rank-selections.

Let ap(S) = 0(5) be the number of maximal chains in P(S) U {0,1}. We define

the beta invariant by

3(5) = Z(-1)'S\T'0(T)o

rgs

37

By the Principle of Inclusion and Exclusion, we have

07(3) = Z 3(T).

Tgs

We have the following proposition, due to Stanley.
Proposition 2.2.1 [16, Proposition 14.1] u(P(S)) = (—1)'S'+IB(S).

Let it be a permutation of the n letters {a1 , . . . , a,,}. We will write all permutations

using one-line notation:

1r = «(a1)7r(ag)~-7r(a,,)

= W1W2'H1rn.
We define the descent set of 7r = «1772 - - - 1r,, by

D(1r) = [i] 7r, > “In-+1}.

As an example, if 11' = 43152, then D(7r) = {1,2,4}. We let the set of all augmented

signed permutations of [n] be the following:

5,? = {0:31...s,,s,,+1: {sl,...,s,,} C {1,2,...,n}U{1,2,...,n},

|s,-| 3£ |st for i 96 j, and s,,+1 = 0}.
(Here we are using the bar notation a to denote —a.) For example,

5; = {120, 120,120,i20,210,210,210,210}.

Note that the maximal chains in 0,, with respect to the labeling A described in
Proposition 2.1.2 correspond with the augmented signed permutations 5:. As an

example, there are seven maximal chains in 03 with descent set {1, 2}:

{3210, 3120, 3120, 2130, 2130, 1230, 1230}

38

Observe that |u(03[2])| = 7. The fact that these two numbers coincide is explained

by Corollary 2.2.3.

Theorem 2.2.2 Let P be a poset of rank n + 1 and S Q [n]. If P admits an R-
labeling, then

6(5) = the number of maximal chains in P with descent set S
(with respect to the given R-labeling A).

By Proposition 2.2.1, we have an important corollary.

Corollary 2.2.3 Under the same hypotheses as Theorem 2.2.2 we have

Iu(P(S))| = the number of maximal chains in P with descent set S
(with respect to the given R-labeling A ).

As a remark, Theorem 2.2.2 and Corollary 2.2.3 still hold if “R-labeling A” is replaced
by “EL-labeling A” or “CL-labeling A”.

2.3 Proof of the Interval Case for 0,,

We have established that 0,, has an R—labeling in PropoSition 2.1.2. In light of

Corollary 2.2.3 we will now use the notation
371(5) = “4071(5)“,

where S Q [n]. We will also use the notation

871(5) = {7r 6 Sf: D(7r) = S}.

(Thus 6.45) = an(S)l')

The problem of maximizing |u(0,,(S))|, where S runs over all interval rank-
selections [i, j] Q [n], is equivalent to maximizing the number of permutations in

B,,( S), where S runs over all intervals of descents [i , j] Q [n]. To tackle this problem,

39

we fix n > 0 and form a triangular array of the 6,,[i, j]’s. The jth row consists of the

values

fl.[1,n—j+1],s..[2,n-j+2], ...,fl,,[j,n] (j=1,...,n).

For example,

012 1
022 1
3 3
03! 1
7 5
5 11 7

To prove Theorem 2.0.4, we look at various configurations in the triangles. In other
words, we try to determine the maximum value in a given row, a given diagonal, or a
given antidiagonal. Using bipartite graph arguments we have been able to determine
the maximum value of the diagonal case completely. (Here a diagonal means the
sequence of B,,[i, j]’s with j fixed, 1 S i S j, and an antidiagonal means the sequence
of ,6,,[i,j]’s with i fixed, i S j S n.) Applying the same techniques to the row and
antidiagonal cases narrows down the maximum to one or two possibilities. Once we
have found the maximum behavior in the row, diagonal and antidiagonal sequences,

we will intersect this information to yield Theorem 2.0.4.

To get the reader accustomed to working with these augmented permutations,
we now give a “faster” proof of Corollary 1.1.7. In fact, Proposition 2.3.1 gives a

recurrence for any ,Bn[i, j], not just the B,,[1, j]’s.

40

Proposition 2.3.1 For the triangular array of 6,,[i, j] ’s, with n > 1, the following

recurrences hold:

(a) 6.[i.j]=2fl.-.[i—1.j-1]+29.-.[z',j—11+fl.—.Izuj]. 15451414
(a) 19,,[i,n]=2fl,,_,[i-1,n—1]+B.,_1[i,n—1], 19's..

with boundary conditions

5111,11 = 1 and 5,40) =1 (n 21).

Proof. Let

8.03:] = {r e 8:: D(w)=[i,1'1}
B:[i,j] = {7r 6 B,,[i,j] : 17 contains the element n}

B;[i,j] = {1r 6 B,,[i,j]: 77 contains the element a}.

For shorthand we will sometimes use 3, 8+ and 8‘, when context makes the value

of the other parameters clear.

Each of the recurrences stated in this proposition follows easily after observing
what happens if we remove the element n or n from a permutation in Sf. For (i),
let 1r = al---a,,a,,+1 = a1---a,,0 E B,,[i,j]. If 7r 6 3+, then a,- = n. Deleting the

element n from 1r gives the bijection

B:[z',j] «—» B,,-,[i— 1,j — 1] UB,,_1[i,j — 1] (2.1)

where the first term on the right side of equation (2.1) corresponds to a,-_1 > a,-+1 and
the second term to a,--1 < a,-+1. If 1r 6 B" then either a, = n or a,“ = n. Deleting

the element a from 11' gives the bijection

B;[i,j] +—i B,,-,[i — l,j — 1] U B,,-1[i,j] U Bn_1[i,j— 1]. (2.2)

41

(Again, the right side of equation (2.2) corresponds to the three cases a, = n, a,“ = n
with a,- > “1+2, and a,“ = n with a,- < din). After taking cardinalities, the

correspondences in (2.1) and (2.2) imply recurrence (i).
Part (ii) follows from the bijections

B:[i,n] +——+ B,,-;[i — 1,n — 1] U B,,_1[i,n — 1] (2.3)

and
B;[i,n] 4—-—-+ B,,-,[i — 1,n — 1]. (2.4)

The boundary conditions follow from the facts

Bl[1, 1] = (1,0)

and

B,,(0)=(i1.,n—1,...,1,0) Cl

 

We will need some notation before starting the various proofs to find the max-
imum value in a given row, diagonal or antidiagonal from the triangular array of
,B,,[i, j]’s. Let 77 = 0102 - - - a,, be any strictly increasing (respectively, strictly decreas-
ing) sequence of integers. For a ¢ 77 an integer, we let 1'7 denote the sequence obtained
by inserting [a] in the sequence 77 so that it remains strictly increasing (respectively,
strictly decreasing). Similarly, we let 71' denote the sequence obtained by inserting
—|a] in the sequence 77, and 77’ denote the sequence obtained by inserting a into the
sequence 77. In each case, we add the element -—|a| or a into the sequence 77 so that
the resulting sequence remains strictly increasing (respectively, strictly decreasing).
For a E 77 let 7'7 denote the sequence obtained by removing the element a from 77.

(Note that since 77 was monotone, the sequence 77 will still be monotone.)

42

Recall that a strictly unimodal sequence is a sequence a], . . . , a,, of the form

a1<a2<~~<ak>ak+1>-°->a,,.

and a sequence a,, . . . ,a,, is almost strictly unimodal if the sequence is strictly uni-

modal or is of the form

a1<ag <<ak=ak+1>ak+2 > > a,,.
We are now ready to begin the proofs.

Proposition 2.3.2 (How Sequences) For r 2 0 the sequence

,3,,[1,1+ r],fl,,[2,2 + r], . . . ,flnIn — r, n]

is almost strictly unimodal with maximum occurring at one (or both) of

Bully-3’25], 131%211 + 7]. flnllglifll. [ES—”l + 7‘1-

For r = 0 and n E 2(3), the sequence

B,,[1,1],B,,[2, 2],. . . , B,,In, n]

is almost strictly unimodal with maximum occurring at

 

flnllz'TJa [Sill] = Alibi-‘1. [3311]-

Proof. We first show 6,,[i—1,i+ r — 1] < 6,,[i,i + r] for i S [313$]. To do this
we construct a bipartite graph G with vertex bipartition V1 = B,,[i — 1, i + r — 1] and
V,» = B,,[i,i + r] and show that [VII < IV2I.

Given 77 = a1 - - - a,,0 E V], we can write 77 = 7717727730 with
771 = 01°”ai—1
172 = armam-

773 = ai+r+l°"an-

43
Note that

77 =01 < < a,-_1 > a, > >a,-+,. <a,~+,.+1< <a,, <0,
so 771, 772 and 773 are monotone increasing, decreasing and increasing, respectively.

Bali—1.i+r—1] B,,[i,i+r]

07-1 0 be
A, A A. A”

01 /
b1

Let 77 6 V1. For each a E 773 form the permutations
U = 7T17l'271'30,

i.e., remove the element a from 773 and adjoin [a] to 771 with respect to the usual
ordering, and

0’ = 2171'271'30,

i.e., remove the element a from 773 and adjoin -IaI to 771 with respect to the usual

ordering. Notice that 0’ and 6 are elements of 8,, Ii, i + 7']. Now given 77 6 V1, draw an

edge of G to every 6 and 6 that can be obtained from 77 in the manner just described.

In the bipartite graph constructed, every vertex in V1 has degree equal to 2I773| =

2(n — i — r). Conversely, each vertex in V: has degree at most I771] = |th = i since the

element a 6 n3 is negative. Notice there are some vertices r = b, - - - b,,0 6 V2 with

degree < i. For instance, if b, = n then 6 cannot be obtained from a 77 with n E 773

since we always have min 773 > min 772. Hence

2(n - i - r)IV1I < z°|V2l,

44

01'

i

 

(n-i-r)

Therefore, for i _<_ 113$ we have [VII < IV2I.

We next show fln[i,i+r] > fln[i+1,i+r+1] for [Ln-331] S i S n—r—l. In asimilar
fashion, we construct a bipartite graph with vertex bipartition V1 = B,,[i + 1, i + 7' +1]
and V; = Bn[i,i + r].

Bn[i+1,i+r+1] B,,[z',i+r]

aH-l 0 be A"
flu

A o

ai+r+2 / bi+r+l

Given 77 = 7717737730 6 V1, where

771 = 01 < < a,,
772 = a,“ > . .. > ag+r+1,
”3 = ag+r+2 < o o o < an,

remove any a 6 771 and draw an edge to every permutation in V3 of the form

6' = 617737730.

Here we have added —|a| < 0 to 773 with respect to the usual ordering because all
the elements of 7‘73 must be negative. Observe 6 E B,,[i,i + r] and every vertex in

V; has degree I771] = i. Every vertex in V; has degree at most 2(n — i — r) because

45

|7i'3| :2 n — i — r and there are two choices for the signing of an element a E 773 when
it is put back into 771. The degree of a vertex could be less than 2(n — i — r). If
7' = b1 ~ - - bnO E Bn[i, i + r] with b;+,.+1 = ii, then moving the element n into b1 - - . 65-1

would give a permutation with i a member of its descent set. So we have

i|V1|< 2(n - i - 7‘)|V2|-

Thus, we obtain |V1|< |V2| for i Z gig-24.

The previous argument shows 3,,[72 - r — 1,n — 1] > B,,[n — r, n] for r S n — 3.
If r = n — 1 there is no argument since fln[0,n — 1](= fln(0)) is not an element of
the row sequence. For r = n — 2 the result follows by using the actual summation

formulas for [3,41, j]. We wish to show

B,,[Ln—l] > fln[2,n]

= fln[1, 1] (2.5)

To obtain the equality in equation (2.5), we need a lemma.

Lemma 2.3.3 For 5' Q [n] the following equality holds

fln(5) = {inflnl \ 5)- '3

This lemma is proved by noting that there is a bijection B,,(S') H Bn([n] \ S) via the

bar operator which sends 77 = a1 - - - a,,O E B,,(S) to 7'7 = 61- - - 6,.0 E Bn([n] \ S).

Now substitute the summation formula from Corollary 1.1.2 in equation (2.5). We
see it is enough to show

I- )3 (:)(-2)"| > I- i (:)(—2)J'I. (2.6)

i=0 i=0

46

Applying the the binomial theorem the left side of equation (2.6) and simplifying the

right side of equation (2.6) we obtain

|—(—1)"+(—2)"|=2"-—1>|—1+2n|=2n—1.

Here we are using the fact 72 Z 3 to simplify the quantities appearing in the absolute
value signs. (Recall r = n — 2 > 0.) But 2" > 212 when n 2 3, so equation (2.6) holds

for n 2 3.

It remains to show

Bull—232.], [273]] = flnllzé‘l, [ZS—"ll
for n 5 2(3). (This is the r = 0 case.) Write n = 3m + 2. Then

l'zbfll : l6m3 4] = 2m+1

and
[23"] = 2m + 2
Note that
[Mid] = lu(0n[i, 2W
= (number of elements in 0,, of rank 2) — 1.
Thus,

2m+1

= 22m+lmlffifiéfiflm + 2 — 2(m +1)]

all-”£1, L231] - 7347's], rs“ = (3m + 2),...H _ (g: 1322,...

=O,Cl

We conjecture that the row sequences obtain their maxima as follows.

47

Conjecture 2.3.4 For fixed 0 S r S n — 1 the sequence

,Bn[1,1+ r], fln[2,2 + r], . . . ,fin[n — r, n]
is almost strictly unimodal. Its maxima only occur at

:Bn[l.2n——§hfl.l’ [24334]] forn i 2(3) or r 9e 0

,Bnhz'fifll, [3153” = flnuygflj, (2%” ‘forn 5 2(3) andr = 0.

We next fix j and consider the diagonal of elements fln[i, j], i = 1,. . . , j. This

time we are able to determine the complete maximum behavior of this sequence.

Proposition 2.3.5 (Diagonal Sequences) The sequence

Balm}. [Bul29jlv - - ”filial

is strictly unimodal. It attains its unique maximum at

a [Ft-21,7] forj aé n
flu [Vlgfljm] forj = n.

Proof. We first show fln[i—1,j] < flulfij] fori 3 L423 (j 7‘- n). As in Proposition 2.3.2,

we form a bipartite graph with vertex bipartition V1 = B,,[i — 1, j] and V3 = B,,[i, j].
Bali-1,i] Bulidl

07—1 be 0
.A. W A. ../‘“

V / b-

+1
01 aj+1 b J
1

48

Given 77 = a1 - - - a,,O = 771a,-17727730 E V1, where

771 = a1<...<a,-_3
772 = a;>...>aj
773 = a,“ <... <a,,»

and a E 773, form the permutation

I I e
a = 771a,-_17737730.

Since a E 773, we know a < 05-1, so 0’ E Bn[i,j]. For every 77 6 V1, draw an edge to
every 6 that is constructed in the manner described. The degree of every vertex in
V1 is I773] = j — i + 1, while the degree of every vertex in V3 is at most |77§| = i — 1.

We obtain the edge count inequality
(j-i+1)|V1| < (i-1)|V2|

This inequality is strict. For instance, if 7' = b, - - - bnO E B,,[i, j] with bl = 7'2, then we
cannot put 7': into big ' - - (7,. If we did, then we would violate the property that for

permutations 77 E B,,[i—1,j] we have min 772 > min 773. So |V1| < |V3| for i 5 Liz.

We next show fln[i,j] > fln[i + 1,j] for i 2 1-12'3- (j 9f n). Construct a bipartite

graph with vertex bipartition V1 = B,,[i + 1,j] and V; = B,,[i,j].

Buli+1,j] Balm}
ai+1 0 bi
/\ ./ /\ /,, °

/ b. v

49

Given 77 = a1 - - ~a,,0 = 771ag+17727730 6 V1, where

771 = al<...<a,-,
772 = 05+2 > ... >aj+1,
“'3 = aj+3<...<a,,,'

and a 6 771, draw an edge to the permutation

O” = irlag+17ré7730.
Since a E n], we know a < a,+1, so 6’ E Bn[i, j]. The degree of every vertex in V1 is
[771] = i, while the degree of each vertex in V3 is at most |77§| = (j - i + 1). We obtain

the edge count inequality

i|V1| < (j-i+1)lV2|-

This inequality is strict. For instance, if 7' = b1 .. ~bn0 E B,,[i,j] with b,- > bi“,
then if we were to move the element bj+1 into the sequence by - - b,-_1, the resulting
permutation would have the descent set [i + 1, j + 1] rather than [i + 1, j]. Therefore

|V1l<lV2l Melt—R

We now know {fln[i,j]}, 1 S i S [2.15.2 j, is a strictly increasing sequence and
{fln[i,j]}, [1%] S i S j, is a strictly decreasing sequence. Observe that [32:2] =
[1321]. Therefore, we may conclude the diagonal sequence {fln[i, j]}, 1 S i S j, j 75 n,

is strictly unimodal with unique maximum flnll'%2.la j].

We have characterized the monotonic behavior of all the diagonal sequences except
the one with j = n. We now consider that sequence. To show 6,, [i — 1,n] < ,Bnli, n]
for i S £33, we consider a bipartite graph with vertex bipartition V1 2 B,,[i — 1, n]

and V3 = B,,[i,n].

50
Bah—1,n] B,,[i,n]

(15-1 bi
/ o. ... .°.
01 / b"

Given 77 = a1 - - ~a,,0 = 771a,_17720 6 V1, where

“I = G] < O O O < a.._2

7T2 = a,->...>a,,

and a 6 773, draw an edge to each of the permutations

0‘ = 310.;17120

and

6 = 3'1 a,_1 3'20.

Since D(77) = [i — 1, n], we see that the elements a,_1, a,, . . . a,, are positive. So a,_.1 Z
a > 0 implies ag_1 > —a. Each vertex in VI has degree equal to 2|772| = 2(n — i + 1),
while each vertex in V3 has degree at most [7'71| = |th = (i — 1). For instance, if
T = b1 - - - bnO E Bn[i,n] with bl = 7‘2, then we cannot put n into b,-+1 ~ - - (1,. since then
b,- < max «3 = n and the result would not be a permutation in B,,[i — 1, n]. We thus

have the edge count inequality

2(n -i+1)|V1| < (i-1)|V2l.

so “’1' < IV3| for i S 31313-31.

To show fln[i,n] > B,,[i + 1,n] for i Z 2—"3fl, we construct a bipartite graph with

vertex bipartition V1 = B,,[i + 1,n], V3 = Bn[i,n].

51
B,,[i + 1,n] B,,[i,n]

“5+1 bi

/\,° /\

\.0 / .. ‘ V2)
/ b1

01

Given 77 = a1“ -a,,0 = 7717730 6 V1, with

771 = al<...<a,-

772 = a.-+1>...>an

and a E 771, draw an edge to the permutation

0’ = 7717720.

All the elements in 772 are positive, so we must place |a| in 773 so that the resulting
permutation a E Bn[i, n]. Every vertex in V1 has degree I771| = i, while each vertex in
V3 has degree at most 2|7'72| = 2(n — i + 1). For example, if 7' = b1 - - -b,,0 E Bn[i,n]
with b,- = n, then we cannot put 71 back into 7‘71 = b1---b,-_1. If we did, this would
violate the pr0perty that max 771 < max 772 for any permutation 77 E B,,[i + 1, n]. We

have the edge count inequality

i|V1|< 2(n—i+1)IV2I,

so IVII < |V2| for i _>_ gig—2a
We have shown the sequence {fln[i,n]}, 1 S i S [Egg], is strictly increasing and
the sequence {,Bn[i,n]}, [2—"51‘31 S i S n, is strictly decreasing. Hence, for n 32 1(3)

the sequence {fln[i,n]}, 1 S i S n, is strictly unimodal with unique maximum of

allk‘a‘éJml-

52

For n 5 1(3) we apply Lemma 2.3.3 to the sequence sequence of ,Bn[i,n]’s. We
obtain {,Bn[l,i]}, 0 S i S [333], is strictly increasing and {fln[1,i]}, [£3115] S i S
n — 1 is strictly decreasing. The permutations represented by these two sequences
correspond to rank selections of the form [1, i] from 0,,, i.e., rank-selected lower order

ideals. By Theorem 1.0.1 B,,[L L?” > ,Bn[l, [2"‘1]]. Hence, the sequence {fln[17i]}7

3

 

0 S i S n — 1 is strictly unimodal with maximum 341, [27%]. Applying Lemma 2.3.3

again gives the result we claimed. C]

The last sequence we consider is the one consisting of antidiagonal elements fln[i, j],

J=z,IIO,nO

Proposition 2.3.6 (Antidiagonal Sequences) The sequence
flnlidlfinlid + 11,- - ..flnlim]

is almost strictly unimodal with maximum occurring at one (or both) of
flnlia lfiiflfl, flnli, [ESL-ill-

W'hen i = 1 the antidiagonal sequence
Buliiilaflnliii'l‘1l7°"7IBn[i7n]

is strictly unimodal with unique maximum of

anli.12—"*;;‘Jl.

Proof. We begin by forming a bipartite graph with vertex bipartition V1 = Bn[i, j — 1]
and v2 = 84:37] (3' ¢ n).

53
Bn[i7j — 1] Bfllzaj]

a1 ()1 bj+l

Given 77 = 771773aJ-7730 6 V1, where

771 = a1<...<a,-_1
71'2 = a.->...>aj_1
773 = aj+1<...<a,,

and a E 773, form the permutations

0 = 7717'73aj7‘730

and

6 = 7717'72aj7i'30.

Since a,- < a < 0 for all a E 773, In] > a,-. Hence 6,6 6 V3. From the vertex 77,
draw an edge to each of the I773] = 2(n — j) permutations in V2 constructed in the
manner described. The degree of each vertex in V3 is at most |7'72| = I713] = j — i + 1.
If 7' = b1 . . .bnO 6 V3 with b,- = n, then we cannot place 7‘2 into bj+2 - - - bu to form a
permutation in V1 because the permutation b1 . - - b,-_1b,-+1 - - - bj+1fibj+2 - - - bn0 has its
jth element b,“ > n, violating a,- < min 773 for permutations 77 = a1 - --a,,0 6 V1.

We have the edge count inequality

2(n -J')|V1| < (j-i+1)|V2|.

54
so IV1| < IV2I forj 5 2—3—2‘

Next we form a bipartite graph with vertex bipartition V1 = B,,[i, j + 1] and
v2 = 8.737] (7+1 aé n).

Bnli.j+11 ' Balm}

Given 77 = 7717727730 E V1 and a E 772 with

771 = a1<...<a,-
772 2 05+] >... >aj+1
773 = aj+2 < <a,,,

form the permutation

6 = 771 71'277'30.

Observe that 6 6 V3 since all the elements of i73 must be negative. For each a E 773,
draw an edge from 77 to every 6 formed in this manner. We obtain the edge count
inequality

(j-i+1)|V1| < 2(n -J')|V2|-

The degree of every vertex in V1 is I772] = j — i + l and each vertex in V2 has degree

at most 2I7i3| = 2(n —j). If 7' = b1...b,,0 6 V3 with bj+1 = n, we cannot move 77 into

55

b,-+1 - - - bj. If we did, then we would violate the property min 772 > min 773 for any

77 6 V1. Thus forj _>_ 2413'; we have |V1| < IVgl.

Finally, we consider the terms of the form fln[i, n] and fln[i, n— 1]. Let V1 = B,,[i, n]

and V: = B,,[i,n — 1] be a vertex partition. (Note 2' S n — 1).

B,,[i,n] Bn[i,n — 1]

0
a1 Yr: b1 v
0 bn
For 77 = 7717730 6 V1, with
771 = a1<...<a,-
773 = a,+1 > >71”
and a E 773, form the permutation
6' = 7716260
Draw an edge from r to each of the [77;] = n — i permutations in V3 formed in

the described manner. Each vertex in V; has degree at most one. For instance, if
7' = (71 - - - bnO 6 V2 and any one of the elements 17,-, . . . , bn_1 is negative, replacing 67,
by |an in b,- - - - b" will not give us back a permutation in V1. We obtain the edge count
inequality

(n-illel < |V2l,

so |V1|<IV2|wheniSn-1.

56

All parts of the proposition have now been proved except the case i = 1 which

follows by appealing to the lower order ideal Theorem 1.0.1. D

Now we are ready to give the proof of Theorem 2.0.4. The theorem easily holds
for n = 1 and n = 2. (Refer back to the pictures of the triangular arrays for 01 and
03 that were previously given.) Now fix n 2 3. We first look at the candidates for the
overall maximum for ,Bn[i, j] that the row and diagonal propositions give us. From

Proposition 2.3.5 the candidates for the maxima are those fln[i, j] with i = [1129-] , i.e.

,Bn[r+1,2r+1] forr=0,...,2r+1Sn—1 (2.7)

fl..[r+2,2r+2] forr=0,...,2r+2Sn—1. (2.8)

Note that we do not need to consider the nth diagonal {fln[i,n]}, 1 S i S n, since
by Lemma 2.3.3 this sequence coincides with the sequence {fln[1,j]}, 1 S j S n (and

the common entry fln[1,n] = 1, which is not a maximum).

The Row Sequence Proposition 2.3.2 predicts the maximum occurs at
fl.[in§-2—'J. [24:11] orfl.[lz—"§311.P-’%51]-

Restated, these maximum candidates are

 

 

 

,Bn [2%, @531] when 2n — 2r 5 0(3) (2.9)
,6“ [2n—gr—1 , 2n-t3r—1]’ fin [2n—3rf2, 2n-gr-1-2] when 2n _ 21‘ E 1(3) (2.10)
fin [2n—gr—2, 2n3t3r—2], ’8" [2n—gri-1 , 2n-fz-3ri-1: when 2" _ 27‘ E 2(3) (211)

 

 

Next we determine which row and diagonal candidates coincide. In other words,
we look for those integer values of r in which a maximum candidate from the diagonal
argument (equations (2.7) and (2.8)) is also a maximum candidate from the row
argument (equations (2.9), (2.10) and (2.11)). Note that in both cases 7' = j — i for

the entry ,Bn[i, j], so we are using the same parameter in the rows and diagonals. For

57

Table 2.1: Common Value of r for Row and Diagonal Results

 

 

 

 

 

 

 

 

 

 

 

Diagonal Row Common value
equation equation of r Forcing
2n - 2r E 1(3) (2.7) (2.10) Ls"! n 5 2(5)
(2.8) (2.10) ' “5’7 E 1(5)
(2.7) (2.10) “—5'1 n E 3(5)
(2.8) (2.10) ’"g‘ n 5 2(5)
2n - 2r 5 2(3) (2.7) (2.11) Z—"fl n E 0(5)
(2.8) (2.11) 2";‘3 n 5 4(5)
(2.7) (2.11) @514 n 5 1(5)
(2.8) (2.11) I] 39-515- n 5 0(5)

 

 

2n—3

2n—2r
3 5

. Since r is

 

example, when 2n — 2r 5 0(3), = r + 1 if and only if r =

2n-2r

 

2n-6
5 a

       

an integer, we must have n 5 4(5). Similarly, - —r + 2 when r =

n 5 3(5).

The remaining cases when 2n — 2r E 1(3) and Zn — 2r E 2(3) follow in a similar

manner. Table 2.1 displays the information needed to complete these cases.

We now rearrange our results according to the equivalence class of n modulo 5. In
each case we decide if we can employ the antidiagonal sequence result to narrow down
the two max candidates to one overall maximum. We will see that the antidiagonal

Proposition 2.3.6 is only helpful when n E 4(5).

First an ose n E 0 5 . Substitutin r = 2—"53 into the row maximum candidates
PP g 5

for 2n — 2r 5 2(3), we obtain the candidates

3 [2..- -2(32=-)— 2 2n+(3"—;3)- -__2] flu] 2.. _4_5_n—5]
fl 3 , 3

 

 

2-2’—"=é+12+"""’+1 ":5
fiL;[ n (35 l , fl ( g l ] ==£L125 ,%?].

58

These two possibilities lie in the same row, so we cannot apply the antidiagonal result.

For n E 1(5) the row and diagonal arguments give

 

fl [2n-2(2‘f—')-1 2n+(’";’)-1] = fl [ma ...—4]
n 3 9 3 n 5 ’ 5

(here 2n — 2r E 1(3) and r = 2"“7), and

5

 

 

[B [2n-2th—2'H'1 2n+(2n;2)+1] _IB [2ni3 4nil]
" 3 ’ 3 "' n 5 ’ 5

(here 2n — 2r E 2(3) and r = P‘s—'2). Both of these elements lie in the same antidiag-

onal. Recall that the antidiagonal proposition asserts

54:37 — 1] < [Maui] forj s 11%;;‘1
5.12371 > mm + 1] forj 2 read].

For n E 1(5) this says

a. [245% - 1] < 3.. [3232.7] forj s 11%!-

IBn [zit—Sigijj > fin [21:97]. + 1] forj Z 12531.

Hence, Proposition 2.3.6 gives no additional information about the two candidates

for the maximum.

For n E 2(5) the two candidates for the maximum are
271i] 477—3 2ni6 4711-2
fin] 5 a 5 J and fi%[ 5 , 5 ].

(Here 2n — 2r 5 1(3) with r = 3"?“1.) As when n E 0(5), these two possibilities lie in

different antidiagonals, so the antidiagonal result cannot give any new information.

When n 5 3(5) the candidates are

2 i4 4 -2 2 i i3
flu]: , n5 ] and fin] 7154,4775 ].

59

 

(Here 2n -— 2r E 0(3) with r = E? and 2n — 27' E 1(3) with r = 2:1, respectively.)
These two values lie in the same antidiagonal. However, for n E 3(5) Proposition

2.3.6 says
a. [Lgfis — 1] < a. [Hg—4,7] forj s 125:3

a. [Lafiflj] > a. [21.53,]... 1] forj 2 —;&

which yields no new information about the two candidates for the maximum.

The last case is when n E 4(5). We obtain the candidate maxima

2 i2 — 2 i2 —6
flu] n5 ,4n51] and fin] 715 ,4715 ]

which lie in the same antidiagonal. (Here 2n — 2r E 0(3) with r = 33-5—3 and 2n — 2r E

 

2(3) with r = ”5’8, respectively.) By Proposition 2.3.6 we have

 

fl. [ls—”.7 — 1] < [341132.71 forj s

3.. [243—27] > 3.. [3%34' + 1] forj _>_ 4—"-—‘.

Hence we can conclude in this case that the overall maximum is fln[2—"5‘L2, %]. C1

The result of Theorem 2.0.4 is unsatisfactory in the sense that, unlike the Boolean
algebra, it does not determine the overall maximum for the interval rank-selection
case (except when n _=-: 4(5)). Instead, for n 1 4(5) it narrows down the extremal
configuration to one of two possibilities. Part of the difficulty with the n-octahedron is
that its triangle of ,Bn[i, j]’s is not symmetric along its rows like the Boolean algebra’s
triangle. More specifically, each row of the Boolean algebra’s triangle is symmetric

about its middle-most element (or elements, if the length of its row sequence is even.)

We have tried various methods to “sharpen” the bipartite arguments for 0,, by
redistributing the edges created between the different permutation types. Unfortu-

nately, none were successful. However, the data for the interval of ranks case behaves

60

quite beautifully, as you can see in Table 2.2. The data strongly suggests that the

maximum occurs by taking the ranks [Egg] through [951,3].

Table 2.2: Extremal Configuration for Interval of Rank-selections from 0,.

61

 

 

 

 

 

 

 

 

 

 

Extremal
n Configuration .7 Ip(0n(f'))l
1 01[1,1] 1
2 02[1,1] = 0,.[2,2] 3
3 03[2, 2] 11
4 0,[2, 3] 41
5 05[3, 4] 161
6 06[3, 5] 591
7 07[3, 5] 2631
8 08[4, 6] 11871
9 09[4, 7] 52513
10 010[5, 8] 231937
11 0,,[5,9] 993343
12 012 [5, 9] 4699903
13 013[6,10] 22111231
14 014[6, 11] 102406721
15 0147, 12] 471223169
16 01.47, 13] 2126966271
17 017V, 13] 10262581759
18 013[8, 14] 49138667007
19 019[8, 15] 232427864577
20 02.49, 16] 1091852042241
21 021 [9, 17] 5058126423039
22 0,2[9 17] 24635153735679
23 02.410, 18] 119106560870399
24 02410, 19] 570189596794881
25 02411.20] 2712059387740161

 

 

Chapter 3

Arbitrary Rank-selections

Given a permutation a1 - - - a,,, we say it is alternating if either

a1<a2>a3<a4>... (3.1)

01‘

a1>ag<a3>a4<.... (3.2)

In the first case (equation (3.1)) we call the permutation an alternating permutation
with initial ascent and in the second case (equation (3.2)) we call the permutation
an alternating permutation with initial descent. We say a permutation a1 - - - a,, has a

double ascent if there exists an index It so that a], < a,,“ < a,,”.

Let P be a poset of rank n, S g [n — 1], and /\ an R-labeling of P. Recall that
|p(P(S))| equals the number of maximal chains in P with descent set S with respect
to an R-labeling A. Proposition 2.1.3 gives an R-labeling /\ of the Boolean algebra B,,.
Note that the maximal chains in B" with respect to this A are simply permutations

in the symmetric group 5,, on 72 letters.

By Corollary 2.2.3, the question of maximizing the Miibius function over arbitrary
rank-selections from the Boolean algebra is equivalent to finding an S Q [n — 1] which

maximizes the number of permutations of descent set S in the symmetric group Sn.

62

63

Sagan, Yeh and Ziegler [15, Theorem 1.2, part 2] used this interpretation of the
arbitrary rank—selection problem to solve the 13,. case. They constructed injective but
not surjective maps from permutations in Sn with a double ascent to permutations

in 5,, with one less double ascent. They obtained the following result.

Theorem 3.0.7 For arbitrary rank-selections S Q [n — 1] of En, |p(B,,(S))| attains

a unique maximum when we take S to be
S: {1,3,5,...}n[n— 1] orS= {2,4,6,...}fl[n— 1].

In this case |u(B,,(S)I = En, the nth Euler number.

In other words, for arbitrary rank-selections S Q [n — 1] the M6bius function is
maximized by taking every other rank from B,,. In terms of permutations from the
symmetric group, this result says the alternating permutations with initial ascent
(or the alternating permutations with initial descent) are the largest class with given

descent set.

The arbitrary rank-selection question, viewed in the context of permutations in
the symmetric group, was studied by Niven and de Bruijn. In [13] Niven also used
an injection-but-not-surjection argument, whereas in [11] de Bruijn developed an

algorithmic technique.

In this chapter we are interested in addressing the arbitrary rank-selection case
for the n-octahedron. Rather than studying this question in terms of augmented
signed permutations of [n] which arise from the R-labeling of 0,, in Proposition 2.1.2,
we present an approach based upon a non-commutative polynomial (I) called the cd-
index. In a recent thesis, Purtill [14] showed that for certain lattices L, <I>(L) has
non-negative coefficients. (See Theorem 3.1.2.) Stanley [18] generalized this to face

lattices of convex polytopes, which permitted him to conclude

64

Theorem 3.0.8 (Stanley) Let Lp be lattice of faces of a convex polytope P, where
the rank of Lp is n + 1. For arbitrary rank-selections S Q [n] of Lp, |u(Lp(S))|

attains a maximum when we take S to be

3: {1,3,5,...} n[n] orS= {2,4,6,...}fl[n].

In this chapter we reconstruct Stanley’s proof in the case of the n-octahedron and

show that these are the only S which maximize p for 0,,.

Theorem 3.0.9 For arbitrary rank-selections S Q [n] of 0,,, |/4(0n(S))| attains a

unique maximum when we take S to be
S = {1,3,5,...] 0 [n] or S = {2,4,6,...} 0 [n].

In this case |p(0n(S)I = Eff, the nth signed Euler number.

3.1 The ab-index and the cd-index

This section serves as a brief introduction to the ab—index and the cd-index. We
will follow [18] for all notation and terminology related to the cd-index. For those

interested in studying the cd-index’s origins, we refer to Bayer and Klapper’s paper
[4].

We will begin by describing Bayer and Billera’s work on flag h-vectors of Eulerian
posets. A key observation due to Fine links the ab—index with the cd-index. Once we
review some algebraic properties of the cd-index, we summarize Purtill’s dissertation
work. For us, his most important results are the non-negativity of the coefficients of

the cd-index of Ba and 0,,, and a recurrence for each of their cd-indexes.

Let P be a finite, graded poset of rank n + 1 that is bounded. Recall in chapter

2 that for S _C_ [n] we defined 0(5) = ap(S), the number of maximal chains of

65

P(S) U {0,1}, and 6(5) = 5;:(5), the beta invariant. This defines a : 2" —-> Z, the
flag f-vector of P, by
S H 0(5),

and fl : 2" —* Z, the flag h-vector of P, by

s ... 3(5)-

We will now encode the flag h-vector (equivalently, the flag f-vector) of the poset

P. First, define a monomial in the noncommutative variables a and b by

uszulooeun,

where
__ a, ifiQ'S
...- b, 3763.

(For our purposes, it will be helpful to think of a as “ascent” and b as “descent”.) As
an example, if n = 5 and S = {1, 4, 5}, then us = baabb. We form a non-commutative
polynomial, called the ab-index, by
\I'p(a,b) = Z ,Bp(S)u5.
591"]
We define the degree of both a and b be 1 so that \Ilp(a, b) is homogeneous of degree

n.

When P is an Eulerian poset (refer to [17, Chapter 3] for terminology), Bayer
and Billera [3] showed the flag h-vector ,3}? satisfies certain linear relations called the
generalized Dehn-Sommerville equations. In the literature these equations are also
referred to as the Bayer-Billera relations. Fine observed that having flp satisfy the
Bayer-Billera relations is equivalent to having the ab—index contained in the algebra

generated by the two elements c = a + b and d = ab + ba.

66

Proposition 3.1.1 [4, Theorem 4] (Fine) Let P be a finite graded poset that is also
bounded. Then the flag h-vector Hp satisfies the Bayer-Billera relations if and only
if \Ilp(a,b) can be written as a polynomial (bp(c,d) in the noncommutative variables

c=a+bandd=ab+ba.

We call the polynomial <I>p(c, d) the cd-index of P.

As noted in [18] the cd-index has some very nice algebraic properties. If <I>p(c, (1)
exists (which it does for Eulerian posets such as Bn and 0,,), then it is unique.
(As noncommutative polynomials over any field K, c = a + b and d = ab + ba are
algebraically independent.) If we define the degree of c to be 1 and the degree of d to
be 2, then (Dp(c, d) is homogeneous of degree n with integer coefficients. By the very
nature of the variables c = a + b and d = ab+ ba, if <I>p(c, (1) exists then its associated

ab-index \Ilp(a, b) is symmetric in a and b.

In his dissertation, Purtill proved the following result about the cd-index. For

shorthand we will write (P(P) for <f>p(c, d).

Theorem 3.1.2 [14, Theorem 6.1] For 8,, and 0,,, its cd-index <I>(B,,), respectively

(P(On), has non-negative coefficients.
He also established recurrences for <I>(B,,) and <I>(0,,).

Proposition 3.1.3 [14, Corollary 5.8] The following recurrence holds for the cd-

index of the Boolean algebra:

(P(Bn+2) = C(P(Bn+1) + En: (n) (P(Bj)dQ(Bn+1_j), n 2 0,

i=1 7

67
Proposition 3.1.4 [1.], Corollary 5.12] The following recurrence holds for the cd-

index of the n + l-octahedron:

<I>(0,,+1)= c<I>(O,,) + i24(’;)<1>(3,)d¢(0,_,), n 2 0,

i=1

with T(Oo) = 1.

Some values for <I>(B,,) and <I>(O,,) are given below:

0(32) = C
Q(Bs) = 62 + (1

(11(34): 03 + Zed + 2dc
<I>(B5) = c4 + 3c2d + 5cdc + 3dc2 + 4d2

<I>(Oo) = 1

Q(01) = C

¢(02) = 62 '1' 2d

0(03) = c3 + 6cd + 4dc

0(04) = c4 + 14C2d + l6cdc + 6dc2 + 20d2

<I>(05) = c5 + 30cdc2 + 485de + 3034 + 100w!2 + 64.1% + 80dcd + 8dc3

3.2 Arbitrary Rank-selections: Lp and On

In this section we will prove the arbitrary rank-selection result for face lattices of
convex polytopes Lp. The results we will have to appeal to are very strong. Two
such examples are Stanley’s non-negativity of the coefficients of the cd-index for L p

and Bjérner’s and Wachs’ result that these face lattices are CL-shellable.

Before proving Theorem 3.0.8, we first verify some properties of ab-expansions
of monomials in the variables c and d. When we formally substitute c = a + b
and d = ab + ba into <I>(Lp) to recapture \II(Lp), we will see the ab-words which

receive the highest contribution from the coefficients of (P(Lp) are the alternating

68

ones: the alternating initial ascent word of length n, ababab. . . and the alternating
W
initial descent word of length n, bababa . . .. This conclusion requires Stanley’s result
W

about the non-negativity of the coefficients of <I>(Lp).

Since Lp is CL-shellable (Theorem 2.1.5), the coefficient 35 of a given word us in

\IILP(a, b) equals |p(Lp(S))]. Hence, we will have shown the rank-selections

S = {1,3,5,...} 0 [n] and S: {2,4,6,...}fl [n]

maximize |p(Lp)|.

We are able to conclude that the odd and even alternating rank-selections from
Lp each maximize the Mébius function for the arbitrary rank-selection question.
What we are not able to conclude at this time is a uniqueness result, i.e., that the
alternating rank-selections are the only extremal configuration. We can, however,
show uniqueness when Lp = 0,, via the recurrence for (P(On) in Proposition 3.1.4.
We also include a conjecture of Stanley which, if true, implies the uniqueness of the

extremal configuration in Theorem 3.0.8 for any Lp.

We begin by defining a convex polytope P (or polytope) to be the convex hull of
a non-empty finite set of points in Euclidean space. For instance, the n-dimensional

octahedron is a convex polytope since it is the convex hull of the Zn points
{21261, . . . , :ften}

in n-dimensional Euclidean space, where

e,- = (0,...,0,1,0,...,0).

i—l 16-:

A polyhedral complex A (not to be confused with the shadow A(S) defined in chapter

1) is finite set of polytopes {P1, . . . ,’P,-} in Euclidean space such that

(i) any face belonging to some 7’,- is a member of A

69

(ii) the intersection of any two members of A is again a member of A.

The maximal faces of a polyhedral complex are called facets. We say A is an n-
complex if the dimension of all the facets of A is 77. Finally, for an n-complex A
we form its face lattice LA by ordering the faces of A by inclusion and adjoining a

maximal element 1. For example, the dimension of all the facets of the n-dimensional

octahedron 0,, is n - 1. Thus, L0,, = 0,,, the n-octahedron.

We next make some simple observations about monomials in the variables c and
d. If w = w; - - - 10,, is an ab—word of degree n, then we say w has a double ascent at

position i if w,- = w,-+1 = a and has a double descent at position i if w,- = w.-+1 = b.

Lemma 3.2.1 Given any monomial w of degree n in the noncommutative variables

c = a + b and d 2 ob + ba, its ab-expansion satisfies

(i) the alternating initial ascent word of length n occurs exactly once
(ii) the alternating initial descent word of length 71 occurs exactly once
(iii) any given ab—word of length n occurs at most once.

(iv) If w = w’dw” with deg w’ = i — 1 then its ab-expansion contains no

ab-word with a double ascent or double descent at position i.

Proof. For properties (i) through (iii) we proceed by induction on the degree n of a

monomial in c and d. By convention for n = 0 the only monomial in c and d is 1.

Now let w be a monomial in the variables c and d of degree n 2 1. We have
two cases to consider, depending upon the first element of w. If w begins with c,
then remove this initial c. This leaves a monomial w’ in the variables c and d of
degree n - 1. By the induction hypothesis the ab-expansion of w’ yields exactly one
alternating initial ascent word of length n —1 and one alternating initial descent word

of length n — 1. All the other possible ab-words of length n — 1 occur at most once.

70

Premultiply all of these monomials by c = a+b. This yields exactly one alternating
initial ascent word of length n and one alternating initial descent word of length n.
All the other possible length n monomials in a and b occur at most once. If not, then
deleting the initial a or b from two duplicate monomials in a and b of length 71. would
give two duplicate length n — 1 monomials in a and lb arising from the same cd-word

of degree n — 1. This would contradict the induction hypothesis.

In a similar fashion, we show the same result for w a monomial in the variables c
and d of degree n > 1 whose first element is d. The difference here is we will have to

apply the induction hypothesis for words in the variables c and d of degree n — 2.

Remove the initial d from w. This leaves a monomial w’ in the variables c and d
of degree n — 2. By the induction hypothesis for n -— 2 the ab-expansion of w’ yields
exactly one alternating initial ascent word of length n — 2 and one alternating initial
descent word of length n — 2. All other possible ab—words of length n — 2 occur at

most once.

Now, premultiply all of these monomials by d = ab + ba. This gives exactly one
alternating initial ascent word of length n and one alternating initial descent word of
length n. All other possible length n ab-monomials occur at most once. If not, then
delete the initial ab or ba from two of the duplicate ab—monomials of length n. This
gives two duplicate length n — 2 monomials in a and b arising from some word in c

and d of degree n — 2, contradicting the induction hypothesis.

For (iv), suppose w = w’dw” with deg w’ = i — 1. Since the degree of w’ is i — 1,
the d (of degree 2) which follows w’ will contribute to the ith and i + lst positions of
the ab-words formed from the ab—expansion of w. This element d can only contribute
ab or ba. Hence, the ab-expansion of w contains no ab-word with a double ascent or

double descent at the ith position. Cl

71

The uniqueness result in Theorem 3.0.9 requires two key observations about

(P(On).
Lemma 3.2.2 The following two properties hold for (P(On):

(i) all possible monomials of degree n in the variables c and d occur at least
once in (P(On)

(ii) for n 2 0 ifm is some monomial of length n in the variables a and b
that is not alternating, then there exists a monomial w in <I>(0,,) whose

ab-expansion makes no contribution to m.

Proof. We first show (i) holds by induction on n. Property (i) is vacuously true for

n = 0 since 0(00) = 1.

Now assume n 2 1. By the recurrence of Proposition 3.1.4
n-l . _ 1
<I>(0,,) = c<I>(0,,_1) + Z 21(n j )<I>(B,~)d<I>(0,,_,-_1), n 2 1, (3.3)
i=1
with <I>(Oo) = 1. Suppose w is a monomial of degree n in the variables c and d. If w
begins with the variable c, remove it to form the monomial w’ of degree n - 1. By the
induction hypothesis, w’ appears at least once in Q(0,,_1). Hence the term c<I>(0,,_1)
appearing in equation (3.3) contains the monomial w = cw’. We do not have to worry

about any possible cancellation since the coefficients of <I>(O,.) are clearly non-negative

from equation (3.3).

Next, let w be a monomial in c and d of degree 72 beginning with the letter d. We
similarly use the first term of the second summand appearing in equation (3.3) to
verify property (i) for w. Remove d from w to form w’, a monomial of degree n — 2.
By the induction hypothesis w’ appears at least once in (P(On-z). Also (P(Bl) = 1.

Hence the term in the summand corresponding to j = 1 in equation (3.3) creates a

w = ldw’ for 0(0n).

72

Property (ii) is vacuously true when n = 0 since there are no non-alternating
words of length l in the variables a and b. For n 2 1, (ii) will follow immediately
from part (i) of this lemma and from (iv) of Lemma 3.2.1. Let m be a monomial of
length n in the variables a and b that is not alternating. Then m has a double ascent
or double descent. Without loss of generality we may assume m has a double ascent
aa at the ith position. (The same argument works when m has a double descent bb
at the ith position.) By property (i) we know every monomial of degree n in the
variables c and (1 occurs at least once in (P(On). In particular, monomials of the form
w = w’dw” with deg w’ = i— 1 occur at least once. By Lemma 3.2.1 the ab—expansion

of any such w makes no contribution to m. D

We have an analogous version of Lemma 3.2.2 for B,,. Its proof is omitted since

it is virtually identical to that of Lemma 3.2.2.

Lemma 3.2.3 The following two properties hold for <I>(B,,):

(i) all possible monomials of degree n — 1 in the variables c and d occur at least
once in <I>(B,,)

(ii) for n 2 1 if m is some monomial of length n — l in the variables a and b
that is not alternating, then there exists a monomial w in (P(Bn) whose

ab-expansion makes no contribution to m. D

It is well-known that the nth Euler number En counts the total number of alter-

nating permutations in the symmetric group with odd (or even) descent set, i.e.

E, = |{77ES,,: D(77)={1,3,5,...}fl[n—1]}| (3.4)

= [[77 6 Sn: D(77) = {2,4,6,...} 71 [n —1]}|. (3.5)

73

A recurrence for the nth Euler numbers is
n

n
Err-+2 = Z (j)EjEn-j+li n 2 1:

i=0

with E0 = E1 = 1. In a similar manner, Purtill defines the nth signed Euler num-
ber E: which counts the total number of augmented signed permutations that are

alternating with odd (or even) descent set:

E: = [[776sz D(77)={1,3,5,...}n[n]}| (3.6)

= |{77€sz D(77)={2,4,6,...}n[n]}|. (3.7)

A recurrence for the nth signed Euler numbers is
Eff“ = 221' (35,131,, 77 21,
i=0

with E3“ = Ejt = 1. (See [14, section 6].)

From Lemmas 3.2.1 and 3.2.2, we can now very easily give the proofs of the
arbitrary rank—selection theorems for Lp and 0,,. We first consider the arbitrary
rank-selection question for Lp, and then prove the uniqueness result for 0,,. It is a
well-known fact that Lp is Eulerian. Thus, <1>( Lp) exists by Bayer and Billera’s work
in [3] and Fine’s equivalence in Proposition 3.1.1. By Stanley [18, Theorem 3.1.2],

the coefficients of <I>(Lp) are non-negative.

Consider the ab-expansion of <I>(Lp) into \II(Lp). By Lemma 3.2.1 each monomial
in 0(Lp) contributes exactly one term to the alternating initial ascent word of length
n, exactly one term to the alternating initial descent word of length n, and at most
one term to all other words of length n in the variables a and b. Thus, the coefficient
of the alternating permutations of length n with initial ascent (equivalently, with

initial descent) equals the number of monomials appearing in 0(Lp). In turn, this

74

. number is just the sum of all the coefficients of <I>(Lp), i.e., (I’LP(1,1). (Here we are

formally substituting c = 1 and d = l in (PL,,(c,d).)

For an ab—word us, S Q [n], we define

D(US) = 5.

(Recall that when we introduced us, we said it would be helpful to think of the a’s
as ascents and the b’s as descents.) Since Lp is C L—shellable (Theorem 2.1.5), the

coefficient of any ab-word us in \It(Lp) is |p(Lp(S))|.

We have shown the alternating ab—words of length 77 receive the greatest contri-
bution from the coefficients of <I>(Lp). In fact, they receive the maximum possible
contribution, since the expansion of each monomial in (P(Lp) contributes at most one
to each ab-word. Thus, the extremal configuration for rank-selections S Q [n] from
Lp is

S = {l,3,5,...}fl[n] orS = {2,4,6,...}fl[n].

This is Theorem 3.0.8.

We next show that for 0,, the odd and even alternating rank—selections are the
only extremal configuration. Suppose m is not an alternating word in the variables
a and b. By property (ii) of Lemma 3.2.2 there exists a monomial w in 0(0n) whose
ab-expansion does not make any contribution to m. Thus the coefficient of m in
\It(0,,) is less than that of the alternating initial ascent (or descent) ab—word of length

n.Cl

As a comment, we could use Lemma 3.2.3, the 8,, counterpart of Lemma 3.2.2,
in the argument just given to reprove Theorem 3.0.7. Also, for the proof of Theorem
3.0.9 we did not have to appeal to Stanley’s non-negativity of the coefficients of <I>(Lp)

and the CL-shellability of LP. Instead, we could have used Purtill’s non-negativity of

75

the coefficients of 0(0n) and the fact 0,, has an R-labeling.

In a personal communication with Stanley we brought to his attention that we
cannot conclude uniqueness of the extremal configuration for Lp other than the cases

when Lp is 8,, or 0,,. Consequently, Stanley has made the following conjecture:

Conjecture 3.2.4 [19] Among all n-polytopes (or more generally Gorenstein* lat-
tices of rank n + 1), the simplex (i.e., the Boolean algebra) has the least cd-index

coeflicient-wise.

If Stanley’s conjecture is true, it would immediately imply the uniqueness result for
Theorem 3.0.8: we would know that every cd-word occurs at least once in <I>(Lp),
since every cd-word occurs at least once in (P(Bn) with positive coefficients. This
would give an Lp counterpart of part (i) of Lemma 3.2.2. Moreover, since part (ii) of
Lemma 3.2.2 follows from part (i) of the same lemma and from Lemma 3.2.1, Lemma

3.2.2 would hold for any Lp, not just 0,, and B,,.

In the table that follows, we include the Mébius values of the extremal configura-

tion for Theorem 3.0.9.

Table 3.1: Arbitrary Rank-selection from 0,,: Maximum M6bius Value for n

1,...,10

76

 

3

E:!:

 

 

CDWKIQO‘vBODMi—s

i—o
O

 

 

1

3

1 1

57

361

2763
24611
250737
2873041
36581523

 

 

Chapter 4

Ln(q); Related Extremal Questions

In the first section of this chapter we address extremal problems for L,,(q), the lattice
of subspaces of an n-dimensional vector space over the finite field GFq. For the lower
order ideal case, Sagan, Yeh and Ziegler found the entire poset L,,(q) is the extremal
configuration. Their argument uses techniques analogous to the ones they developed
for B,,. We determine that all of the ranks of the poset L,,(q) is also the extremal
configuration for its the interval of ranks and arbitrary rank-selection cases. As usual

in such cases, we use the inversion statistic.

The second section of this chapter describes work-in-progress related to questions

addressed in this dissertation.

4.1 L,,(q): Interval of Ranks and Arbitrary Rank-
selections

For S Q [n — l], we use the notation

(L,,(q),S) = {W E L,,(q): dim W E S}

to indicate the S rank-selection from L,,(q). For 77 = 771773 - - - 77,, 6 Sn, define

inV77=|{(i,j): 77,->77,andi<j} I
77

78

For example, if 77 = 31524 E 35, then inv 77 = 5.

In chapter 2 we saw that we could translate questions involving the M6bius func-
tion of rank-selections S from 8,, and 0,, into questions of studying certain permuta-
tions with descent set S. For S rank-selections from L,,(q) there is a way to compute

Ip(L,,(q), S )I in terms of the inversion statistic.

Proposition 4.1.1 [17, Theorem 3.12.3] Let L,,(q) be the lattice of subspaces of an

n-dimensional vector space over GE, and let S Q [n — 1]. Then

|#(Ln(q).5)| = Z q‘"""-

«es...D(«)=s

We will use this interpretation of S rank-selections from L,,(q) to establish its interval

of rank and arbitrary rank-selection results.

Theorem 4.1.2 For sufi’iciently large q and arbitrary rank-selections S Q [n — 1]
from L,,(q), Ip(L,,(q),S)I attains a maximum when we take S = [n — 1]. In other

words, for large enough values of q,

Iu(L..(q),S)| g .16“)

with equality holding if and only ifS = [n — 1].

Since the extremal configuration in Theorem 4.1.2 is an instance of an interval rank-

selection, we have the immediate corollary:

Corollary 4.1.3 For interval of rank-selections S Q [n— 1] from L,,(q), the extremal

configuration coincides with the one in Theorem 4.1.2.

The proof of Theorem 4.1.2 will follow once we establish a simple result about

inversions of permutations in Sn.

79

Proposition 4.1.4 For 77 6 Sn, we have the following bound

n
. < .
inv77_ (2)

Furthermore, 77 = n n — 1- - - 2 l is the unique permutation in S,, with inv 77 = (’2‘).

Proof. For any 6 = 0102 - - - 6,, E S", we have the following bound on the maximum

number of inversions that the ith element 6,- E 6 can contribute to inv 6:

I{j: 6,>6,-andi<j}ISn—i. (4.1)

Hence, the greatest number of possible inversions any 77 = 771772 - - . 77,, 6 Sn could have

n n i— (n)
i=1 2

), where 77 = mag-”77,, E S... Thus for 1 S i S n, 77,- must

is

71

Suppose inv 77 = (2

attain the maximum possible number of inversions described in equation (4.1). When
i = 1 equation (4.1) forces 771 = n. The letters [71 — 1] are now left, so when i = 2

equation (4.1) forces 77; = n — 1. Continuing in this fashion, we see that

77,-=n—i+1,1SiSn. Cl

Theorem 4.1.2 now follows immediately from Proposition 4.1.4. Ip(L,,(q), S)I is a
polynomial in q with degree at most (3) . The degree equals ('2‘) only when S = [n — 1].

There is only one such permutation 77 E Sn with D(77) = (’2‘), so we are done.

A more precise statement of what is meant by the phrase “large-enough q” in

Theorem 4.1.2 is given in the next proposition.

Proposition 4.1.5 The maximum in Theorem 4.1.2 is guaranteed to hold ifq 2 En,

where E, is the nth Euler number.

80

Proof. We have for S 2f [n — 1]
('2')-1 ,
|u(Ln(q).S)| = Z 69'. (4-2)

i=0

where

c,-=|{77€S,,: D(77)=S,inV77=i}I.

Taking the most naive upper bound for each qi appearing in equation (4.2) gives

61-1 ..
ll‘(Ln(Q).S)l S 2; C.-q(1’)‘1
. (2)4

: q(2)-1 ; Ci

= q(';)-1| {77 e 5,: 1)(«) = S} |

(1(3)-1 En (4.3)

|/\

l/\

a
A
003
v

, _ (4.4)

where the inequality in equation (4.4) holds if q 2 En. The bound in equation (4.3)

arises since the greatest number of permutations in S, with the same descent set is

E, [11].

To see how good the estimate is in Proposition 4.1.5, we will need the following

proposition:
Proposition 4.1.6 For S Q [n - 1] and IS] = n — 2, Ip(L,,(q),S)I is of the form

141501.511 = 4(3)“ + 00(3)”) (as q —» oo). (45)

Conversely, iffor S Q [n — 1] equation (1.5) holds, then IS] = n — 2.

81

Proof. For the forward direction, it suffices to show there exists exactly one permu-
tation 77 6 8,. with inv 77 = (1])—1 and with D(77) = S, where S Q [n— 1], IS] = n—2
is given. First suppose S = [n — 1] \ {i} with i 76 1. Let 77 = 771---77,, 6 S,, with
D(77) = S. Thus

771>--->77.'<77,-+1>77,-+2>--->77,,,

so either 771 = n or 77.-+1 = n. If 77,-+1 = n, then 771 can contribute at most 77 — 2 to the
total number of inversions. Since 77,- < 77,-+1, 77,- can contribute at most n — i — 1 to the
total number of inversions of 77. By equation (4.1), we cannot achieve inv 77 = (g) — 1,

so we must have 771 = 71.

Under the new assumption that 771 = n, 77,- can still contribute at most 77 — i — 1

n

2) — 1, 77, must

to the total number of inversions of 77. In order to have inv 77 = (

contribute exactly 77 - i — 1 to the total number of inversions, implying
77, > 77,-+3 > 77,-+3 > > 77,,.
Also, the other 77,, j 94 i, must contribute the maximum number of inversions to 77,
i.e., inv 77,- = n — j, j 96 i. Hence
771 > 172 > > 77.--1 > 77.-+1.
But 77,- < 77,-+1, so we have

771>--->77,-_1 >77,“ >77,->77,-+3>77,-+3>--->77,,,

implying
n—j+1forj5£i,i+1
77j= n—i forj=i
n—i+1 forj=i+1.
Next supposeS= In—l]\{1} = [2,n—1]. F0777 = 771---77,, 6 Sn with D(77) = S
wehave

771<773>773>--~>77,,,

82

implying 773 = n. Thus 73 contributes n — 2 to the total number of inversions of 77.

fl

2) - 1' Since 1'1 < 1'2, 1n can contribute at most 71 — 2

Furthermore, suppose inv 77 = (
to the total number of inversions of 77. In fact, by equation (4.1) «1 must contribute
exactly n — 2 to the total number of inversions of 77. Similarly, the remaining terms

must contribute n - j to the total number of inversions (j 95 1). Thus we have
771>773 > “'7,"

implying
n — 1 for j = l
77,- = n for j = 2
n—j+ l, forj =3,...,n.

The converse is clearly true for n = 3. Now suppose n > 3 and S Q [n — 1] with
Ip(L,,(q), S)I satisfying equation (4.5). Then there exists exactly one 77 = 771 - - - 77,, 6
5,, with D(77) = S and inv 77 = ('2‘) — 1. Suppose on the contrary that IS] < n-2. The
permutation n has at least two ascents, i.e. S Q [n-1]\{lc, l} for some I: 79 l 6 [n— 1].

This means 77;, < «1+1 and 771 < n+1. But then

I{j: Wk>7rjandk<j}|gn_k_1

and

I{j: 77;>77,andl<j}ISn—l—1.

Thus inv 77 S ('2‘) — 2, contradicting the fact inv 77 = (Z) — 1. Thus IS] = n — 2. D

We also have a recurrence for the Ip(L,,(q), S )I which appear in Proposition 4.1.6.
This recurrence enables us to easily evaluate Ip(L,,(q), S )I, and hence compare the
value of q which Theorem 4.1.2 is guaranteed to hold (Proposition 4.1.5) with the

actual smallest value of q for which it holds.

83

Proposition 4.1.7 For S Q [n — 1], with S = [n — l] \ {i} and n 2 3, Iu(L,,(q),S)I
satisfies the following recurrence:

Fori9£1,n—1,

|#(Ln(q). S)I = q""‘|#(Ln-1(q), [n - 2l\{i---1})|+

(In-Tlfll‘an—KQL l” " 21)] + |/1(Ln-1(9). l” — 2] \ {3})” (4-6)

Fori=l

I”(Ln(Q)7 5)I = 9"'2(I#(Ln_x(q). ln - 2])l + |#(Ln_1(<1),12,n - 2DI), (4-7)

andfori=n—1

|u(Ln(q). 5)l = q""l#(Ln—1(q). [n - 3])l + lawn—1(9). [n - 2])|- (4-8)
The boundary conditions are:

Ip(Ln(Q). [n —1])| = q(’;)
|/l(Ln(q),0)| = 1.

Proof. Supposen Z3andS=[n—1]\{i}withi7€1,n—1. For77=771~-77n 6 Sn

with D(r) = S, either 771 = n or 77,-+1 = n. Thus

|n(Ln(q).S)l = Z: q"“’"+ Z q""’"- (49)
776$”,D(77)=S 776$",D(77)=S
771:7; 77.+1=n

Deleting n from 77 gives

|#(L..(q).S)I = q"“|p(Ln-1(q).[n-21\{i-1})|+

q"”'1(I/7(Ln_1(q), [n - 2l)| + 17414—1016 - 2] \ {i})l)-

For i = 1 the first summand on the right side of equation (4.9) is zero, so by virtually

the same argument we obtain the recurrence in equation (4.7). Similarly, for i = n — l

84

Table 4.1: Comparison of the Predicted q with the Actual q, n = 1,... ,10

 

Predicted Actual
n q 2 En q
2
5
16
61
272
1385
7936
10 50521

 

cooosrczouaxoa
ODQOCQOOWODNM

 

 

 

 

 

we note the second summand on the right side of equation (4.9) will only contribute

one term when we delete n from 77, so we also obtain equation (4.8). D

In Table 4.1 we compare the predicted q so that Theorem 4.1.2 is guaranteed to
hold with the actual q. As one can see, there is room to improve the estimate in

Proposition 4.1.5.

4.2 Related Extremal Questions

We are currently focusing upon four main extremal problems in our research. What

follows is a brief description of each.
I. Classification of Posets with Rank-selected Extremal Configuration

For the Boolean algebra and the n-octahedron, the Mébius function attains a
maximum over lower order ideals by taking a certain rank-selected lower order ideal.
(See [15] and Theorem 1.0.1). Given the results for these two posets, we would
like to address a much more difficult question: identify those posets whose extremal

configuration maximizing the M6bius function over lower order ideals corresponds to

85

a rank-selected lower order ideal. Since the Boolean algebra and the n-octahedron
are examples of face lattices of convex polytopes, we expect the face lattices of convex

polytopes to naturally belong to this class of posets.
II. New Applications of the cd-index

The cd-index is a relatively new object of study. As we saw in chapter 3, for certain
posets the cd-index encodes information about the Mébius function of rank-selections.
The answer to the question of maximizing the Mébius function over arbitrary rank-
selections from the n-octahedron (and more generally, from any face lattice of a
convex polytope) was an easy consequence of recent work of Purtill and Stanley on
the coefficients of the cd-index. We are looking for other results for 0,, and 8,,
which the cd-index answers quite naturally. Also, we would like to prove Stanley’s

Conjecture 3.2.4 or find a counterexample.
III. Extremal Questions for Other Posets

The q—analog of the Boolean algebra B" is L,,(q), so it would make sense for us
to study the q-analog of 0,,. This poset is 1,,(q), the poset of isotropic subspaces.
For 1,,(q) we plan to address extremal questions analogous to the ones studied in this

dissertation.
IV. Permutations and Their Inverses

One can study the absolute value of the M6bius function of rank-selected subposets
from the Boolean algebra in terms of permutations in the symmetric group. A related
question posed by Ira Gessel is: for fixed 71 let fn( A, B) be the number of permutations
in the symmetric group on n elements with descent set A such that the descent set
of the inverse is B. For what A and B is fn(A,B) the greatest? The data we have
looked at suggests that A and B are “alternating”. We hope to prove this result by

applying an algorithmic technique similar to one developed by de Bruijn [11].

Bibliography

[1] M. Aigner, Combinatorial Theory, Grundlehren Series 234, Springer Verlag,
New York, 1979.

[2] K. Baclawski, Cohen-Macaulay connectivity and geometric lattices, European

J. Combin. 3 (1982), 293-305.

[3] M. Bayer and L. Billera, Generalized Dehn-Sommerville relations for poly-
topes, spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985),
143-157.

[4] M. Bayer and A. Klapper, A new index for polytopes, Discrete Comput. Geom.
6 (1991), 33-47.

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

[6] A. Bjérner, The Homology and Shellability of Matroids and Geometric Lat-

tices, in “Matroid Applications”, N. White, ed., Cambridge University Press,
1991, 226-283.

[7] A. Bjérner, A. M. Garsia and R. P. Stanley, An introduction to Cohen-
Macaulay partially ordered sets, in “Ordered Sets”, I. Rival, ed., Reidel, Dor-
drecht, 1982, 583-615.

[8] A. Bjérner and G. Kalai, An extended Euler-Poincare theorem, Acta Math.
161 (1988), 279-303.

[9] A. Bj6rner and M. Wachs, On lexicographically shellable posets, Trans. Amer.
Math. Soc. 277 (1983), no. 1, 323-341.

[10] Béla Bollobés, “Combinatorics: Set Systems, Hypergraphs, Families of Vec-
tors, and Combinatorial Probability,” Cambridge University Press, Cam-
bridge, 1986.

[11] N. G. de Bruijn, Permutations with given ups and downs, Nieuw Arch. Wisk.
18 (1970), 61-65.

[12] J. Eckhoff, Die Euler-Charakteristik von Vereinigungen konvexer Mengen im
Rd, Abh. Math. Sem. Univ. Hamburg 50 (1980), 135-146.
86

87

[13] I. Niven, A combinatorial problem of finite sequences, Nieuw Arch. Wisk. 16

(1968), 116-123.

[14] M. Purtill, André permutations, lexicographic shellability and the cd-index of
a convex polytope, Trans. Amer. Math. Soc., to appear.

[15] B. E. Sagan, Y.-N. Yeh and G. Ziegler, Maximizing M6bius functions on sub-

sets of Boolean algebras, Discrete Math., to appear.

[16] R. P. Stanley, “Ordered Structures and Partitions”, Memoirs of the AMS 119
(1972).

[17] R. P. Stanley, “Enumerative Combinatorics, Vol. I,” Wadsworth and
Brooks/ Cole, Pacific Grove, 1986.

[18] R. P. Stanley, Flag f-vectors and the cd-index, preprint, August 31, 1992.
[19] R. P. Stanley, Personal communication, March 8, 1993.

[20] BS. Steékin, Imbedding theorems for Mébius functions, Soviet Math. Dokl.
24 (1981), 232-235 (translated from Dolcl. Akad. Nauk SSSR 260 (1981), no.
1,4043).

[21] G. M. Ziegler, Posets with maximal M6bius function, J. Combin. Theory Ser.
A, 56 (1991), 203-222.

   

"I11111111111111l“