Report Number: CS-TR-79-760
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.