Desigualdade de Ahlswede-Daykin - Ahlswede–Daykin inequality

Uma ferramenta fundamental em mecânica estatística e combinatória probabilística (especialmente gráficos aleatórios e o método probabilístico ), a desigualdade de Ahlswede-Daykin ( Ahlswede & Daykin 1978 ), também conhecida como o teorema das quatro funções (ou desigualdade ), é uma desigualdade do tipo de correlação para quatro funções em uma rede distributiva finita .

Afirma que se são funções não negativas em uma rede distributiva finita, de modo que ${\ displaystyle f_ {1}, f_ {2}, f_ {3}, f_ {4}}$

${\ displaystyle f_ {1} (x) f_ {2} (y) \ leq f_ {3} (x \ vee y) f_ {4} (x \ wedge y)}$

para todos os x , y na rede, então

${\ displaystyle f_ {1} (X) f_ {2} (Y) \ leq f_ {3} (X \ vee Y) f_ {4} (X \ wedge Y)}$

para todos os subconjuntos X , Y da rede, onde

${\ displaystyle f (X) = \ sum _ {x \ in X} f (x)}$

e

${\ displaystyle X \ vee Y = \ {x \ vee y \ mid x \ in X, y \ in Y \}}$

${\ displaystyle X \ wedge Y = \ {x \ wedge y \ mid x \ in X, y \ in Y \}.}$

A desigualdade de Ahlswede-Daykin pode ser usada para fornecer uma pequena prova da desigualdade de Holley e da desigualdade de FKG . Também implica a desigualdade XYZ .

Para uma prova, veja o artigo original ( Ahlswede & Daykin 1978 ) ou ( Alon & Spencer 2000 ).

Generalizações

O "teorema das quatro funções" foi generalizado independentemente para 2 k funções em ( Aharoni & Keich 1996 ) e ( Rinott & Saks 1991 ).

Referências

• Ahlswede, Rudolf; Daykin, David E. (1978), "Uma desigualdade para os pesos de duas famílias de conjuntos, suas uniões e interseções", 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, JH (2000), The probabilistic method. Segunda edição. Com um apêndice sobre a vida e obra de Paul Erdős. , Wiley-Interscience, New York, ISBN 978-0-471-37046-8, MR  1885388
• Fishburn, PC (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