Average height in a partially ordered set

✍ Scribed by P. Winkler

• Publisher: Elsevier Science
• Year: 1982
• Tongue: English
• Weight: 457 KB
• Volume: 39
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(82)90157-1

✦ Synopsis

The average height of an element x in a finite poset P is the expected number of elements below x in a random linear extension of P. We prove a number of theorems about average height, some intuitive and some not, using a recent result of L.A. Shepp.

Let P be an arbitrary finite poset having n elements, and let Q(P) be the set of one-to-one order-preserving maps from P onto (0, 1,2,. . . , n -1). Let L(P) be the cardinality of e(P), i.e. the number of linear extensions of P.

If x and y are elements of P, we use the expression F U {x < y} to denote the poset with the same underlying set as P whose order relation is the smallest one containing the order relation of P and the pair (x, y). The probability that ?I is smaller than y, denoted Pr(x < y), is defined as L(P U{x < y})/L(P). Thus if a linear extension f~ @(P) is chosen at random, Pr(x C y) = Pr(&) C f(y)). We assume throughout that all linear extensions are equally likely.

Any collection of inequalities involving elements of P may be regarded as an event and identified with the set of linear extensions in @(P) in which all the inequalities hold. The usual notation for conditional probabilities then obtains, so that, for example, Pr(a<b)c<d)=L(PU{acb,c<d})/L(Pu(ccd}).