Ahlswede–Daykin inequality

Short description: Correlation-type inequality for four functions on a finite distributive lattice

The Ahlswede–Daykin inequality (Ahlswede Daykin), 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 (Ahlswede Daykin) or (Alon Spencer).

Generalizations

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

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

• Ahlswede, Rudolf; Daykin, David E. (1978), "An inequality for the weights of two families of sets, their unions and intersections", Probability Theory and Related Fields 43 (3): 183–185, doi:10.1007/BF00536201, ISSN 0178-8051 
• Alon, N.; Spencer, J. H. (2000), The probabilistic method. Second edition. With an appendix on the life and work of Paul Erdős., Wiley-Interscience, New York, ISBN 978-0-471-37046-8 
• Hazewinkel, Michiel, ed. (2001), "Ahlswede–Daykin inequality", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Main_Page 
• Aharoni, Ron; Keich, Uri (1996), "A Generalization of the Ahlswede Daykin Inequality", Discrete Mathematics 152 (1–3): 1–12, doi:10.1016/0012-365X(94)00294-S 
• Rinott, Yosef; Saks, Michael (1991), "Correlation inequalities and a conjecture for permanents", Combinatorica 13 (3): 269–277, doi:10.1007/BF01202353