Ahlswede–Daykin inequality

Template:Short description The Ahlswede–Daykin inequality Template:Harv, 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$ 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)$

and

$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 XYZ inequality.

For a proof, see the original article Template:Harv or Template:Harv.

Generalizations

The "four functions theorem" was independently generalized to 2k functions in Template:Harv and Template:Harv.

History

The story of the discovery of the Ahlswede–Daykin inequality was described in the Introduction to the A. Ahlswede et al. book:

"The history of the idea of the AD-inequality is very interesting. As Daykin came to a visit to Bielefeld, Ahlswede was just wallpapering. He stood on the ladder, and Daykin wanted to tell him from a newly proven inequality. The declaration was complicated, and Ahlswede said that probably a more general (and easier) theorem should hold. He made directly—on the ladder—a proposal which already was the AD-inequality."

Sources

• Template:Citation
• Template:Citation
• Template:Eom
• Template:Citation
• Template:Citation