Ahlswede–Daykin inequality

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A fundamental tool in statistical mechanics and probabilistic combinatorics (especially random graphs and the probabilistic method), 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 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_{x\in X}f(x)


X\vee Y = \{x\vee y\mid x\in X, y\in Y\}
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 Fishburn–Shepp inequality.

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


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