Institution: Stanford University, Department of Computer Science

Title: Some monotonicity properties of partial orders

Author: Graham, Ronald L.

Author: Yao, Andrew C.

Author: Yao, F. Frances

Date: September 1979

Abstract: A fundamental quantity which arises in the sorting of n numbers $a_1$, $a_2$,..., $a_n$ is Pr($a_i$ < $a_j$ | P), the probability that $a_i$ < $a_j$ assuming that all linear extensions of the partial order P are equally likely. In this paper we establish various properties of Pr($a_i$ < $a_j$ | P) and related quantities. In particular, it is shown that Pr($a_i$ < $b_j$ | P') $\geq$ Pr($a_i$ < $b_j$ | P), if the partial order P consists of two disjoint linearly ordered sets A = {$a_1$ < $a_2$ < ... < $a_m$}, B = {$b_1$ < $b_2$ < ... < $b_n} and P' = P $\cup$ {any relations of the form $a_k$ < $b_l$}. These inequalities have applications in determining the complexity of certain sorting-like computations.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/760/CS-TR-79-760.pdf