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
- [math]\displaystyle{ P(x\prec y)P(x\prec z) \leqslant P((x\prec y) \wedge (x\prec z)) }[/math],
where P(A) is the probability that a linear order extending the partial order [math]\displaystyle{ \prec }[/math] has the property A.
In other words, the probability that [math]\displaystyle{ x\prec z }[/math] increases if one adds the condition that [math]\displaystyle{ x\prec y }[/math]. In the language of conditional probability,
- [math]\displaystyle{ P(x \prec z) \leqslant P(x \prec z \mid x \prec y). }[/math]
The proof uses the Ahlswede–Daykin inequality.
See also
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
- Hazewinkel, Michiel, ed. (2001), "Fishburn-Shepp inequality", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page
- Shepp, L. A. (1982), "The XYZ conjecture and the FKG inequality", The Annals of Probability (Institute of Mathematical Statistics) 10 (3): 824–827, doi:10.1214/aop/1176993791, ISSN 0091-1798, https://repository.upenn.edu/cgi/viewcontent.cgi?article=1268&context=statistics_papers
 |  |
