In
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 ap ...
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 ext ...
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 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.
Bio ...
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. A poset consists of a set together with a binary r ...
, then
:
,
where ''P''(A) is the probability that a linear order extending the partial order
has the property A.
In other words, the probability that
increases if one adds the condition that
. 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 occu ...
,
:
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 probabilisti ...
.
See also
*
FKG inequality
In mathematics, the Fortuin–Kasteleyn–Ginibre (FKG) inequality is a correlation inequality, a fundamental tool in statistical mechanics and probabilistic combinatorics (especially random graphs and the probabilistic method), due to . Informall ...
References
*
*
*
{{DEFAULTSORT:XYZ inequality
Inequalities
Theorems in combinatorics
Independence (probability theory)