go-v.orgdoi

The FKG Inequality and Some Monotonicity Properties of Partial Orders

Larry A Shepp · SIAM Journal on Algebraic and Discrete Methods · 1980

  • DOI 10.1137/0601034
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 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)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 04:44 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0601034
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.