The Ahlswede–Daykin inequality , also known as the four functions theorem (or inequality), is a

correlation In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics ...

-type inequality for four functions on a finite distributive lattice. It is a fundamental tool in

statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...

and

probabilistic combinatorics The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects ...

(especially random graphs and the probabilistic method). The inequality states that if

f_1,f_2,f_3,f_4

are nonnegative functions on a finite distributive lattice such that :

f_1(x)f_2(y)\le f_3(x\vee y)f_4(x\wedge y)

for all ''x'', ''y'' in the lattice, then :

f_1(X)f_2(Y)\le f_3(X\vee Y)f_4(X\wedge Y)

for all subsets ''X'', ''Y'' of the lattice, where :

f(X) = \sum_f(x)

and :

X\vee Y = \

X\wedge Y = \.

The Ahlswede–Daykin inequality can be used to provide a short proof of both the

Holley 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 . Informal ...

and the

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 . Informally ...

. It also implies the

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 ...

. For a proof, see the original article or .

Generalizations

The "four functions theorem" was independently generalized to 2''k'' functions in and .

References

* * * * * {{DEFAULTSORT:Ahlswede-Daykin inequality Inequalities Theorems in combinatorics Statistical mechanics