Fishburn-Shepp inequality

$xyz$ inequality

An inequality for linear extensions of a finite partially ordered set $(X,\prec)$. Elements $x,y\in X$ are incomparable if $x\neq y$ and neither $x\prec y$ nor $y\prec x$. Denote by $<_0$ a general linear order extension of $\prec$ on $X$, let $N$ be the number of linear extensions $<_0$, and let $N(a_1<_0b_1,\ldots,a_n<_0b_n)$ be the number of linear extensions in which $a_i<_0b_i$ for $i=1,\ldots,n$.

The Fishburn–Shepp inequality says that if $x$, $y$ and $z$ are mutually incomparable members of $(X,\prec)$, then

$$N(x<_0 y)N(x<_0 z)<N(x<_0 y,x<_0 z)N.$$

This was first proved for $\leq$ in [a3], then for $<$ in [a2]. The Ahlswede–Daykin inequality [a1] plays a key role in the proof.

The inequality is also written as

$$\mu(x<_0y)\mu(x<_0z)<\mu(x<_0y,x<_0z),$$

where $\mu(A)$ denotes the probability that a randomly chosen linear extension $<_0$ of $\prec$ satisfies $A$. When written as $\mu(x<_0y,x<_0z)/\mu(x<_0y)>\mu(x<_0z)$, one sees that the probability of $x<_0z$ increases when it is true that also $x<_0y$. Some plausible related inequalities are false [a3].

See also Correlation inequalities; FKG inequality; Holley inequality.

References

[a1]	R. Ahlswede, D.E. Daykin, "An inequality for the weights of two families, their unions and intersections" Z. Wahrscheinlichkeitsth. verw. Gebiete , 43 (1978) pp. 183–185
[a2]	P.C. Fishburn, "A correlational inequality for linear extensions of a poset" Order , 1 (1984) pp. 127–137
[a3]	L.A. Shepp, "The XYZ conjecture and the FKG inequality" Ann. of Probab. , 10 (1982) pp. 824–827