Lecture 6
Last week we discussed two applications of the Fourier-Walsh plus hypercontractivity method and in this lecture we will discuss one additional application:
The lecture was based on a 5-pages paper by Ehud Friedgut and Jeff Kahn: On the number of copies of one hypergraph in another Israel Journal of Mathematics Vol. 105 (1998) pp. 251-256.
In this application our method has nice but not optimal consequences, and another method – applying Shearer’s inequality, gives the optimal result.
1) The question: Given a hypegraph H with k vertices what is the maximum number of labeled copies of H inside a hypegraph G with 
There are cases where the answer is known with great precision. The Kruskal-Katona theorem gives the answer when H is the hypegraph whose edges are all the r-subsets of a vertex set V of size k.
In our study we will fix H and care only about the asymptotic behavior as a function of 
2) Stable sets and fractional stable sets. A stable set S in a hypergraph H (also called independent set) is a set of vertices so that every edge contains at most one vertex from S. The stable number 
Now comes an idea which is very important in graph theory, of considering the linear programming relaxation of combinatorial parameters. A fractional stable set is an assignment of non negative weights to the vertices, so the sum of weights in every edge is at most one. So this is a “fuzzy set” of a kind the membership of a vertex to a set is described by a number in the interval [0,1] rather than the set {0,1}. The size of a fractional stable set is the sum of weights of all vertices. The fractional stable number 
3) Cover and fractional cover numbers
We next described covering and fractional covering (of vertices by edges) in hypergraphs, the covering number 
4) The answer:
Friedgut-Kahn theorem: The number of copies of H is a hypergraph G with
and this bound is sharp.
The case of graphs was proved (in a different language) by Noga Alon in his M. Sc. thesis, and Noga’s first publication On the number of subgraphs of prescribed type pf graphs with a given number of edges,( Israel J. Math. 38(1981), 116-130).) Part of the challenge was to find the right extension for Alon’s theorem.
5) The lower bound.
Next we explained the nice and simple construction giving the lower bound, which is based on the weights realizing the fractional stable number of H.
6) Bonami’s inequality in a dual form
Our next thing was to state a consequence of Bonami’s hypercontractive inequality, which is a direct extension of Chinchine inequality. Then we showed a weaker upper bound than the actual theorem based on the Bonami inequality .
It is an interesting open question to apply harmonic analysis to the general case. (I believe it is tractable.)
7) Traces and Shearer’s lemma
Next we defined the trace of a hypergraph on a subset W of vertex-set V and stated Shearer’s lemma.
8) More about traces and a little more extremal combinatorics
Not having enough time to complete the proof of Friedgut-Kahn theorem using Shearer’s lemma, we proved the fundamental Sauer-Shelah inequality (see this post), and stated Frankl’s conjecture (see this post, and this one (sec 3d) ).
Lecture 7
We started with the proof of the Friedgut-Kahn bound using Shearer’s lemma. Then we explained the simple connection between influences and traces and mentioned the connection of Shearer’s lemma (and the Loomis-Whitney theorem) to edge-sioperimetry.
Our next application: First Passage percolation. We gave a short introduction to models of percolation and started to discuss our fourth application of the Fourier+hypercontractivity method: An upper bound for the variance of first passage percolation. Here the method gives the best known result, but unlike KKL’s theorem the result is not sharp. We are third way toward a proof so I may write about it next time. The discussion of first passage percolation is based on the paper First Passage Percolation Has Sublinear Distance Variance by Benjamini, Kalai and Schramm.
Combinatorics and more 