XYZ inequality

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 Shepp (1982). An extension was given by Peter Fishburn in Fishburn (1984).

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

$P(x\prec y)P(x\prec z)\leqslant 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)\leqslant P(x\prec z\mid x\prec y).$

The proof uses the Ahlswede–Daykin inequality.

See also

• FKG inequality

References

• Fishburn, Peter C. (1984), "A correlational inequality for linear extensions of a poset", Order, 1 (2): 127–137, doi:10.1007/BF00565648, ISSN 0167-8094, MR 0764320, S2CID 121406218
• "Fishburn-Shepp inequality", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Shepp, L. A. (1982), "The XYZ conjecture and the FKG inequality", The Annals of Probability, 10 (3), Institute of Mathematical Statistics: 824–827, doi:10.1214/aop/1176993791, ISSN 0091-1798, JSTOR 2243391, MR 0659563