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", is a correlation-type inequality for four functions on a finite distributive lattice.

It states that if are nonnegative functions on a finite distributive lattice such that

for all x, y in the lattice, then

for all subsets X, Y of the lattice, where

and

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).

Generalizations

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

References

• 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, MR0491189 
• 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 0-471-37046-0, MR1885388 
• Fishburn, P.C. (2001), "Ahlswede–Daykin inequality", in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1556080104, http://www.encyclopediaofmath.org/index.php?title=a/a110440 
• Aharoni, Ron; Keich, Uri (1996), "A Generalization of the Ahlswede Daykin Inequality", Discrete Mathematics 152: 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