Misplaced Pages

Ahlswede–Daykin inequality

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Four functions inequality) Correlation-type inequality for four functions on a finite distributive lattice

The Ahlswede–Daykin inequality (Ahlswede & Daykin 1978), 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 probabilistic combinatorics (especially random graphs and the probabilistic method).

The inequality states that if f 1 , f 2 , f 3 , f 4 {\displaystyle f_{1},f_{2},f_{3},f_{4}} are nonnegative functions on a finite distributive lattice such that

f 1 ( x ) f 2 ( y ) ≤ f 3 ( x ∨ y ) f 4 ( x ∧ y ) {\displaystyle f_{1}(x)f_{2}(y)\leq f_{3}(x\vee y)f_{4}(x\wedge y)}

for all x, y in the lattice, then

f 1 ( X ) f 2 ( Y ) ≤ f 3 ( X ∨ Y ) f 4 ( X ∧ Y ) {\displaystyle f_{1}(X)f_{2}(Y)\leq f_{3}(X\vee Y)f_{4}(X\wedge Y)}

for all subsets X, Y of the lattice, where

f ( X ) = ∑ x ∈ X f ( x ) {\displaystyle f(X)=\sum _{x\in X}f(x)}

and

X ∨ Y = { x ∨ y ∣ x ∈ X , y ∈ Y } {\displaystyle X\vee Y=\{x\vee y\mid x\in X,y\in Y\}}
X ∧ Y = { x ∧ y ∣ x ∈ X , y ∈ Y } . {\displaystyle X\wedge Y=\{x\wedge y\mid x\in X,y\in Y\}.}

The Ahlswede–Daykin inequality can be used to provide a short proof of both the Holley inequality and the FKG inequality. It also implies the XYZ inequality.

For a proof, see the original article (Ahlswede & Daykin 1978) or (Alon & Spencer 2000).

Generalizations

The "four functions theorem" was independently generalized to 2k functions in (Aharoni & Keich 1996) and (Rinott & Saks 1991).

References

Categories: