Ahlswede–Daykin inequality
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 [math]\displaystyle{ f_1,f_2,f_3,f_4 }[/math] are nonnegative functions on a finite distributive lattice such that
- [math]\displaystyle{ f_1(x)f_2(y)\le f_3(x\vee y)f_4(x\wedge y) }[/math]
for all x, y in the lattice, then
- [math]\displaystyle{ f_1(X)f_2(Y)\le f_3(X\vee Y)f_4(X\wedge Y) }[/math]
for all subsets X, Y of the lattice, where
- [math]\displaystyle{ f(X) = \sum_{x\in X}f(x) }[/math]
and
- [math]\displaystyle{ X\vee Y = \{x\vee y\mid x\in X, y\in Y\} }[/math]
- [math]\displaystyle{ X\wedge Y = \{x\wedge y\mid x\in X, y\in Y\}. }[/math]
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).
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
- 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
 |  |
