Credit to:
- Dor Minzer’s lecture notes
- Max Hopkins lecture notes
- O’Donnel’s book
Edge expansion of a weighted graph is defined as:
We say a graph is an expander if, for all
Small set expansion:
For any
Theorem 2.3 (The hypercontractive inequality).
For all
Theorem:
The
Proof: The key step will be to use the hypercontractive inequality. This is because we can express the expansion by the following inner-product:
Now using Holder and Hypercontractivity:
We conclude that:
Some other good things to remember:
- concentration, anti-concentration for low degree functions
- Junta’s are the classic example of non-expanding sets in the hypercube.
- Hypercontractivity: says stuff about the noise operator, and about relationships between different norms
- Small influence ⇒ you’re a Junta (Freidgut Junta theorem)
- KKL gives you a coordinate with high influence
- Expansion could be pretty good. It’s best if you get a graph that people already know about, or a Cayley graph. But in a pinch
might be useful.