The FKG Inequality and Some Monotonicity Properties of Partial Orders

Let $( a_1 , \cdots ,a_m ,b_1 , \cdots ,b_n )$ be a random permutation of $1,2, \cdots ,m + n$. Let P be a partial order on the a’s and b’s involving only inequalities of the form $a_i < a_j $ or $b_i < b_j $, and let $P'$ be an extension of P to include inequalities of the form $a_i < b_j$; i.e, $P' = P \cup P''$, where $P''$ involves only inequalities of the form $a_i < b_j $. We prove the natural conjecture of R. L. Graham, A. C. Yao, and F. F. Yao [SIAM J. Alg. Discr. Meth. 1 (1980), pp. 251–258] that in particular (*) $\Pr ( a_1 < b_1 |P' ) \geq \Pr ( a_1 < b_1 |P )$. We give a simple example to show that the more general inequality (*) where P is allowed to contain inequalities of the form $a_i < b_j $ is false. This is surprising because as Graham, Yao, and Yao proved, the general inequality (*) does hold if P totally orders both the a’s and the b’s separately. We give a new proof of the latter result. Our proofs are based on the FKG inequality.