Tag Archives: Winter School Discrete Analysis 2012

1. Exercises Exercise 1 Show that for the tribes function, . Show that for monotone Boolean functions, If is Boolean, there is a monotone Boolean function such that Let . Recall that is the number of neighbours of where . … Continue reading →

1. Sharp threshold phenomena 1.1. Threshold width Suppose is a monotone Boolean function. Then is a non decreasing function of . Russo’s Lemma (appears earlier in Margulis, and even earlier in reliability theory) is Lemma 1 Definition 2 For , … Continue reading →

Before I go on, let me come back to the discussion of optimality of KKL Theorem. It is sharp inasmuch as is large. One can be a bit more precise, even if one is merely interested in . Theorem 1 … Continue reading →

1. Proof of the KKL Theorem Harper’s theorem deals with the sum of influences. It is a bit stronger than the direct consequences of Fourier expansion described by Mossel yesterday. The KKL Theorem is even stronger. 1.1. Fourier expression for … Continue reading →

1. Discrete Fourier analysis Today, I state a theorem. This afternoon, Mossel explains how harmonic analysis can be used in combinatorics. The Parseval identity, though elementary, turns out to be very powerful. Tomorrow, I will give an additional ingredient, hypercontractivity. … Continue reading →