From Wikipedia, the free encyclopedia
Correlation-type inequality for four functions on a finite distributive lattice
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 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
{\displaystyle f_{1},f_{2},f_{3},f_{4}}
are nonnegative functions on a finite distributive lattice such that
f
1
(
x
)
f
2
(
y
)
≤
f
3
(
x
∨
y
)
f
4
(
x
∧
y
)
{\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
f
1
(
X
)
f
2
(
Y
)
≤
f
3
(
X
∨
Y
)
f
4
(
X
∧
Y
)
{\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
f
(
X
)
=
∑
x
∈
X
f
(
x
)
{\displaystyle f(X)=\sum _{x\in X}f(x)}
and
X
∨
Y
=
{
x
∨
y
∣
x
∈
X
,
y
∈
Y
}
{\displaystyle X\vee Y=\{x\vee y\mid x\in X,y\in Y\}}
X
∧
Y
=
{
x
∧
y
∣
x
∈
X
,
y
∈
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
XYZ 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,
CiteSeerX
10.1.1.380.8629 ,
doi :
10.1007/BF00536201 ,
ISSN
0178-8051 ,
MR
0491189 ,
S2CID
120659862
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 ,
MR
1885388
Fishburn, P.C. (2001) [1994],
"Ahlswede–Daykin inequality" ,
Encyclopedia of Mathematics ,
EMS Press
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 ,
S2CID
206791629