Fishburn–Shepp inequality

In combinatorial mathematics, the Fishburn–Shepp inequality is an inequality for the number of extensions of partial orders to linear orders, found by Fishburn (1984) and Shepp (1982).

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

where P(*) is the probability that a linear order < extending the partial order has the property *.

In other words the probability that x < z strictly increases if one adds the condition that x < y. In the language of conditional probability,

The proof uses the Ahlswede–Daykin inequality.

References

This article is issued from Wikipedia - version of the 9/24/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.