Chapter 1

The Poset Conjecture

1.1 Introduction

Many of the results that are in this paper have been discovered (as often happens in mathe-

matics) in the author's attempts to understand and solve a specific, particular problem. In

this chapter this problem is stated, some elementary results about it and some equivalent

formulations of it are derived and some special cases in which the conjecture is known to be

true are reviewed. It is hoped that this will motivate the reader in the reading of the general

theory that will be developed in the next three chapters.

In this chapter the reader is assumed to be familiar with all the basic concepts of modern

enumerative combinatorics (as can be found e. g. in [63]) and with the theory of (Sub -

partitions as developed in [57] or [58].

1.2 Statement of the Poset Conjecture

Let P be a (finite) partially ordered set (or, poset, for short). Recall that a labeling of P is

a bijection UJ : P — [p] where p = \P\. The pair (P, UJ) is called a labeled poset. The labeling

UJ is called natural if x,y 6 P and x y implies u(x) u(y).

If (P,u?) is a labeled poset and s £ N then a (P,w)-partition with largest part s is

an order reversing map a : P —• [s] such that x y and OJ{X) u?(y) implies a(x) a(y)

(where, by convention, [0] == 0 ).

We denote with H(P, w;s) (respectively, e5(P,u)) the number of (P,u;)-partitions (re-

spectively, surjective (P, u;)-partitions) with largest part s. So, for example, es(P, uS) = 0

if s \P\ and O(P,o;;0) = e0(P,uS) = 0. Now, by an elementary counting argument, we

easily see that

n(PW;*) = S:e.(PW)(*) (1)

S = l

for all x £ N . This shows that 0(P , u\x) is a polynomial function of x of degree |P|. The

polynomial 0(P,LO\X) 6 Q[x] is called the order polynomial of (P,a;) and is a fundamental

1Received

by the editor August 10, 1988.

2This work is a revised version of the author's Ph.D. Thesis (Massachusetts Institute of Technology, 1988)

written under the direction of Professor Richard P. Stanley.

1