### Lecture 4

In the third week we moved directly to the course’s “**punchline**” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity.

Before that we started with a very nice discrete isoperimetric question on a graph which is very much related to the graph of the discrete cube.

Consider the graph *G* whose vertices are 0-1 vectors of length *n* with precisely *r* ’1′s, and with edges corresponding to vertices of Hamming distance* two*. (Which is the minimal Hamming distance between distinct vertices.) Given a set

*A*of

*m*vertices, how small can be? (We already talked about intersecting families of sets of constant size – the Erdos-Ko-Rado theorem and, in general, it is a nice challenge to extend some of the ideas/methods of the course to constant weight situation.)

And now for the main part of the lecture.

* 1) Basics harmonic analysis on the discrete cube. *We considered the vector space of real functions on the discrete cube and defined an inner product structure. We also defined the

*p*-th norm for . Next we defined the

*and showed that they form a orthonormal basis. This now leads to the Fourier-Walsh expansion for an arbitrary real function*

**Fourier-Walsh functions***f*on the discrete cube , and we could easily verify

*Parseval formula.** 2) Influence and Fourier.* If

*f*is a real function on and its Fourier-Walsh expansion. We showed that . It follows that . The Fourier-theoretic proof for

*I(f)*≥

*4 t (1-t)*where

*t=μ(f)*now follows easily.

**3) Chinchine, hypercontractivity and the discrete isoperimetric inequality.**

Next we discussed what will it take to prove the better estimate *I(f) ≥ K t* log *t. *We stated Chinchine inequality, and explained why is Chinchine inequality relevant: For Boolean functions the *p*th power of the *p*-norm does not depend on *p*. (It always equals *t*.) Therefore if *t* is small, the *p*-th norms themselves much be well apart! After spending a few moments on the history of the inequality (as told to me by *Ron Blei)* we discussed what kind of extension do we need, and stated the Bonami-Gross-Beckner inequality. We use Bonami’s inequality to proof of the inequality *I(f) ≥ K t* log *t* and briefly talked about what more does it give.

### Lecture 5

**1) Review and examples.** We reviewed what we did in the previous lecture and considered a few examples: Dictatiorship; the AND function (an opportunity to mention the uncertainty principle,) and MAJORITY on three variables. We also mentioned another connection between influences and Fourier-Walsh coefficients: for a monotone (non decreasing) Boolean function* f*, .

**2) KKL’s theorem**

**KKL’s theorem:** There is an absolute constant *K* so that for every Boolean function *f,* with *t=μ(f)*, there exists *k*, *1 ≤ k ≤ n* such that

To prove of KKL’s theorem: we repeat, to a large extent, the steps from Lecture 4 (of course, the proof of KKL’s theorem was where this line of argument came from.) We showed that if all individual influences are below than .

We mentioned one corollary: For Boolean function invariant under a transitive group of permutations, all individual influences are equal and therefore .

**3) Further problems**

In the last part of the lecture we mentioned seven problems regarding influence of variables and KKL’s theorem (and I added two here):

1) What can be said about balanced Boolean functions with small total influence?

2) What can be said about Boolean functions for which *I(f) ≤ K t log (1/t)*, for some constant K, where* t=μ(f)?*

3) What can be said about the connection between the symmetry group and the minimum total influence?

4) What can be said about Boolean functions (*1/3 ≤ μ(f)≤ 2/3,* say) for which .?

5) What more can be said about the vector of influences ?

6)* What is the sharp constant in KKL’s theorem?

7)* What about edge expansions of (small) sets of vertices in general graphs?

8) Under what conditions for β >0.

9) What about influence of larger sets? In particular, what is the smallest* t* (as a function of *n *) such that if there is a set *S* of variables *S ≤ 0.3n* with ?

(This post is a short version, I will add details later on.)