The FKG Inequality and Some Monotonicity Properties of Partial Orders
Larry A Shepp · SIAM Journal on Algebraic and Discrete Methods · 1980
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Algebraic and Discrete Methods · Society for Industrial and Applied Mathematics · article · 1980
Abstract
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.
Open the resolved locator · 10.1137/0601034
Metadata licence: OpenAlex metadata (CC0)