View source for Fishburn-Shepp inequality

{{TEX|done}}
''$xyz$ inequality''

An inequality for linear extensions of a finite [[Partially ordered set|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 generic 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 [[#References|[a3]]], then for $<$ in [[#References|[a2]]]. The [[Ahlswede–Daykin inequality|Ahlswede–Daykin inequality]] [[#References|[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|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 [[#References|[a3]]].

See also [[Correlation inequalities|Correlation inequalities]]; [[FKG inequality|FKG inequality]]; [[Holley inequality|Holley inequality]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.C. Fishburn,   "A correlational inequality for linear extensions of a poset"  ''Order'' , '''1'''  (1984)  pp. 127–137</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L.A. Shepp,   "The XYZ conjecture and the FKG inequality"  ''Ann. of Probab.'' , '''10'''  (1982)  pp. 824–827</TD></TR></table>