Chapter 10 notes

As mentioned, the standard template introduced by Bonami [Bon70] for proving the Hypercontractivity Theorem for $\pm 1$ bits is to first prove the Two-Point Inequality, and then do the induction described in Exercise 3. Bonami’s original proof of the Two-Point Inequality reduced to the $1 \leq p < q \leq 2$ case as we did, but then her calculus was a little more cumbersome. We followed the proof of the Two-Point Inequality from [Jan97]. Our use of two-function hypercontractivity theorems to facilitate induction and avoid the use of Exercise 3 is non-traditional; it was inspired by [MOR+06,BBH+12,KOTZ13]. The other main approach for proving the Hypercontractivity Theorem is to derive it from the Log-Sobolev Inequality (see Exercise 23), as was done by Gross [Gro75].

We are not aware of the Generalized Small-Set Expansion Theorem appearing previously in the literature; however, in a sense it’s almost identical to the Reverse Small-Set Expansion Theorem, which is due to [MOR+06]. The Reverse Hypercontractivity Inequality itself is due to Borell [Bor82]; the presentation in Exercises 69 follows [MOR+06]. For more on reverse hypercontractivity, including the very surprising fact that the Reverse Hypercontractivity Inequality holds with no change in constants for every product probability space, see [MOS12b].

As mentioned in Chapter 9 the definition of a hypercontractive random variable is due to Krakowiak and Szulga [KS88]. Many of the basic facts from Section 2 (and also Exercise 2) are from this work and the earlier work of Borell [Bor84]; see also, e.g., [KW92,Jan97,Szu98,MOO10]. As mentioned, the main part of Theorem 17 (the case of biased bits) is essentially from Latała and Oleszkiewicz [LO94]; see also [Ole03]. Our Exercise 20 fleshes out (and slightly simplifies) their computations but introduces no new idea. Earlier works [BKK+92,Tal94,FK96b,Fri98] had established forms of the General Hypercontractivity Theorem for $\lambda$-biased bits, giving as applications KKL-type theorems in this setting with the correct asymptotic dependence on $\lambda$. We should also mention that the sharp log-Sobolev inequality for product space domains (mentioned in Exercise 27) was derived independently of the Lata{\l}a–Oleszkiewicz work by Higuchi and Yoshida [HY95] (without proof), by Diaconis and Saloff-Coste [DS96] (with proof), and possibly also by Oscar Rothaus (see [BL98]). Unlike in the case of uniform $\pm 1$ bits, it’s not known how to derive Lata{\l}a and Oleszkiewicz’s optimal biased hypercontractive inequality from the optimal biased log-Sobolev inequality.

Kahane [Kah68] has been credited with pioneering the randomization/symmetrization trick for random variables. The entirety of Section 4 is due to Bourgain [Bou79], though our presentation was significantly informed by the expertise of Krzysztof Oleszkiewicz (and our proof of Lemma 41 is slightly different). Like Bourgain, we don’t give any explicit dependence for the constant $C_q$ in Theorem 37; however, Kwapień [Kwa10] has shown that one may take $C_{q’} = C_q = O(q/\log q)$ for $q \geq 2$. Our proof of Bourgain’s Theorem 45 follows the original [Bou99] extremely closely, though we also valued the easier-to-read version of Bal [Bal13].

The biased edge-isoperimetric inequality (9) from Exercise 27 was proved by induction on $n$, without the additional $o_p(1)$ error, by Russo [Rus82] (and also independently by Kahn and Kalai [KK07]). We remark that this work and the earlier [Rus81] already contain the germ of the idea that monotone functions with small influences have sharp thresholds. Regarding the sharp threshold for $3$-colourability discussed in Exercise 42, Alon and Spencer [AS08] contains a nice elementary proof of the fact that at the critical probability for $3$-colourability, every subgraph on $\epsilon v$ vertices is $3$-colourable, for some universal $\epsilon > 0$. The existence of a sharp threshold for $k$-colourability was proven by Achlioptas and Friedgut [AF99], with Achlioptas and Naor [AN05] essentially determining the location.