Some Monotonicity Properties of Partial Orders

Abstract

A fundamental quantity which arises in the sorting of n numbers $a_{1}, a_{2}, \cdots ,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^\prime )\geqq \Pr ( a_i < b_j |P )$ if the partial order P consists of two disjoint linearly ordered sets $A = \{ a_1 < a_2 < \cdots < a_m \},B = \{ b_1 < b_2 < \cdots < b_n \}$ and $P^\prime = P \cup \{ \text{any relations of the form} \, a_k < b_l\}$. These inequalities have applications in determining the complexity of certain sorting-like computations.