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

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

Неравенство утверждает, что если $f_{1},f_{2},f_{3},f_{4}$ — неотрицательные функции на конечной дистрибутивной решетке такие, что

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

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

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

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

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

и

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

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

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

Доказательство см. в оригинальной статье ( Alswede & 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