# 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].

How to Cite This Entry:
Fishburn-Shepp inequality. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fishburn-Shepp_inequality&oldid=37414
This article was adapted from an original article by P.C. FishburnL.A. Shepp (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article