Ahlswede–Daykin inequality

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 ${\displaystyle f_{1},f_{2},f_{3},f_{4}}$ are nonnegative functions on a finite distributive lattice such that

${\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

${\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

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

and

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

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