Abstract

Discrete Localization and Correlation Inequalities for Set Functions

Michael Saks
Mon Feb. 9 at 1:10pm in Hill 423

The Ahlswede-Daykin 4-function theorem (4FT) is a fundamental inequality for set functions (real valued functions whose domain is the set of subsets of some finite set). In this talk, I'll present three different generalizations of the 4FT. First, the conclusion of the 4FT is generalized to norms other than the L_1 norm. Secondly, a refinement of the 4FT is proved showing that the hypothesis of the 4FT implies a family of inequalities whose sum is the conclusion of the 4FT. Finally, it is also shown that the hypothesis of the four function theorem is preserved under a form of convolution.
All of these theorems are deduced from another theorem proven here: given two real valued set functions f_1,f_2 defined on the subsets of a finite set S each having nonnegative sum, there exists a positive multiplicative set function m and two subsets A and B of S such that for each i in {1,2}, m(A)f_i(A) + m(B)f_i(B) +m(A union B)f_i(A union B)+ m(A intersection B)f_i(A intersection B) is nonnegative. This theorem is an analog for discrete set functions of a geometric result of Lov\'asz and Simonovits.
This is joint work with Laci Lov\'asz.