The XYZ Conjecture and the FKG Inequality

Consider random variables $x_1, \cdots, x_n$, independently and uniformly distributed on the unit interval. Suppose we are given partial information, $\Gamma$, about the unknown ordering of the $x$'s; e.g., $\Gamma = \{x_1 < x_{12}, x_7 < x_5, \cdots\}$. We prove the "XYZ conjecture" (originally due to Ivan Rival, Bill Sands, and extended by Peter Winkler, R. L. Graham, and other participants of the Symposium on Ordered Sets at Banff, 1981) that $P(x_1 < x_2|\Gamma) \leq P(x_1 < x_2|\Gamma, x_1 < x_3).$ The proof is based on the FKG inequality for correlations and shows by example that even when the hypothesis of the FKG inequality fails it may be possible to redefine the partial ordering so that the conclusion of the FKG inequality still holds.