Fishburn-Shepp inequality

From Encyclopedia of Mathematics
Revision as of 19:05, 9 January 2016 by Richard Pinch (talk | contribs) (links)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

$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


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.


[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
How to Cite This Entry:
Fishburn-Shepp inequality. Encyclopedia of Mathematics. URL:
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