combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many app ...

mathematics, the XYZ inequality, also called the Fishburn–Shepp inequality, is an inequality for the number of

linear extension In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extens ...

s of finite

partial order In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...

s. The inequality was conjectured by Ivan Rival and Bill Sands in 1981. It was proved by

Lawrence Shepp Lawrence Alan Shepp (September 9, 1936 Brooklyn, NY – April 23, 2013, Tucson, AZ) was an American mathematician, specializing in statistics and computational tomography. Shepp obtained his PhD from Princeton University in 1961 with a disserta ...

in . An extension was given by

Peter Fishburn Peter Clingerman Fishburn (September 2, 1936 – June 10, 2021) was an American mathematician, known as a pioneer in the field of decision theory. In collaboration with Steven Brams, Fishburn published a paper about approval voting in 1978. Biog ...

in . It states that if ''x'', ''y'', and ''z'' are incomparable elements of a finite

poset In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

, 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 In probability theory, conditional probability is a measure of the probability of an event occurring, given that another event (by assumption, presumption, assertion or evidence) has already occurred. This particular method relies on event B occur ...

, :

P(x \prec z) \leqslant P(x \prec z \mid x \prec y).

The proof uses the

Ahlswede–Daykin inequality The Ahlswede–Daykin inequality , also known as the four functions theorem (or inequality), is a correlation-type inequality for four functions on a finite distributive lattice. It is a fundamental tool in statistical mechanics and probabilis ...

References

* * * {{DEFAULTSORT:XYZ inequality Inequalities Theorems in combinatorics Independence (probability theory)

See also

References