Fall 2013

On Correlation Inequalities for Monotone Subsets of the Discrete Cube

Monday, September 30th, 2013 4:10 pm5:00 pm

Add to Calendar

The well-known correlation inequality of Harris (1960) asserts that any two monotone subsets of the discrete cube are non-negaitvely correlated. In 1996, Talagrand established a lower bound on this correlation in terms of how much the two subsets are influenced by the same coordinates. Talagrand's result (or the main lemma used in its proof) was central in the proof of several later results, such as the BKS noise sensitivity theorem and a lower bound on the boundary of monotone subsets of the discrete cube.

While Talagrand's result is known to be tight, with several diverse examples of tightness, all known examples of this type are "symmetric", in the sense that the influence of each coordinate is roughly the same for the two examined subsets. In particular, there is no example of tightness in which one of the subsets is balanced while the other is of a small measure.

In this talk we discuss lower bounds similar to Talagrand's one, which appear to be stronger in the "asymmetric" cases, and propose a conjectured bound which will unify Talagrand's bound with the newly obtained ones.

Video was unavailable for this talk. We apologize for any inconvenience.