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
Previous Page Next Page