XYZ inequality

Template:Short description Template:No footnotes In combinatorial mathematics, the XYZ inequality, also called the Fishburn–Shepp inequality, is an inequality for the number of linear extensions of finite partial orders. The inequality was conjectured by Ivan Rival and Bill Sands in 1981. It was proved by Lawrence Shepp in Template:Harvtxt. An extension was given by Peter Fishburn in Template:Harvtxt.

It states that if x, y, and z are incomparable elements of a finite poset, then

$P(x\prec y)P(x\prec z)⩽P((x\prec y)\wedge (x\prec z))$,

where P(A) is the probability that a linear order extending the partial order $\prec$ has the property A.

In other words, the probability that $x\prec z$ increases if one adds the condition that $x\prec y$. In the language of conditional probability,

$P(x\prec z)⩽P(x\prec z\mid x\prec y).$

The proof uses the Ahlswede–Daykin inequality.

See also

• FKG inequality

References

• Template:Citation
• Template:Eom
• Template:Citation