Неравенство Альсведе – Дайкина

Неравенство корреляционного типа для четырех функций на конечной дистрибутивной решетке

Неравенство Альсведе-Дайкина (Ahlswede & Daykin 1978), также известное как теорема о четырех функциях (или неравенство ), представляет собой неравенство корреляционного типа для четырех функций на конечной дистрибутивной решетке . Это фундаментальный инструмент статистической механики и вероятностной комбинаторики (особенно случайных графов и вероятностного метода ).

Неравенство утверждает, что if — неотрицательные функции на конечной дистрибутивной решетке такие, что ${\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)}$

для всех x , y в решетке, то

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

для всех подмножеств X , Y решетки, где

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

и

${\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\}.}$

Неравенство Альсведе-Дайкина можно использовать для краткого доказательства как неравенства Холли , так и неравенства ФКГ . Это также подразумевает неравенство XYZ .

Доказательство см. в оригинальной статье (Ahlswede & Daykin 1978) или (Alon & Spencer 2000).

Обобщения

«Теорема о четырех функциях» была независимо обобщена на 2 k функций в (Aharoni & Keich 1996) и (Rinott & Saks 1991).

Рекомендации

• Альсведе, Рудольф; Дайкин, Дэвид Э. (1978), «Неравенство для весов двух семейств множеств, их объединений и пересечений», Теория вероятностей и смежные области , 43 (3): 183–185, CiteSeerX  10.1.1.380.8629 , doi :10.1007/BF00536201, ISSN  0178-8051, MR  0491189, S2CID  120659862
• Алон, Н.; Спенсер, Дж. Х. (2000), Вероятностный метод. Второе издание. С приложением о жизни и творчестве Пауля Эрдеша. , Wiley-Interscience, Нью-Йорк, ISBN 978-0-471-37046-8, МР  1885388
• Фишберн, ПК (2001) [1994], «Неравенство Алсведе – Дайкина», Энциклопедия математики , EMS Press
• Ахарони, Рон; Кейч, Ури (1996), «Обобщение неравенства Альсведе Дайкина», Discrete Mathematics , 152 (1–3): 1–12, doi : 10.1016/0012-365X(94)00294-S
• Ринотт, Йозеф; Сакс, Майкл (1991), «Корреляционные неравенства и гипотеза о перманентах», Combinatorica , 13 (3): 269–277, doi : 10.1007/BF01202353, S2CID  206791629