Jerusalem Mathematics Colloquium

Thursday, 14th June 2007, 4:00 pm
Mathematics Building, Lecture Hall 2


Natan Keller

"On the correlation of monotone functions on the discrete cube"

Abstract: A well-known theorem of Kleitman (1966) asserts that every two monotone families of subsets of an n-elememt set are non-negatively correlated. Kleitman's result, along with numerous generalizations, are extremely useful in Combinatorics. In 1996, Talagrand improved Kleitman's theorem and showed a lower bound on the correlation in terms of how much the characteristic functions of the monotone families depend simultaneously on the same variables.

In this talk we discuss various generalizations and improvements of Talagrand's result, including generalizations to monotone non-Boolean functions on the discrete cube endowed with a general product measure, generalizations to correlation of more than two families, and improved lower bounds on the correlation in the average case.

The new results are achieved using analytic tools, mainly the Fourier-Walsh expansion of functions on the discrete cube and a hypercontractive inequality due to Bonamie and Beckner.

Light refreshments will be served outside the lecture hall at 3:30.

List of talks, 2006-07
Archive of talks