Hypercontractive inequalities via SOS, and the Frankl--R\"odl graph

Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant $0<\gamma \le 1\mathrm{/}4$, the SOS/Lasserre SDP hierarchy at degree $4\lceil \frac{1}{4\gamma }\rceil$ certifies the statement “the maximum independent set in the Frankl–R"odl graph ${\mathrm{F}\mathrm{R}}_{\gamma }^n$ has fractional size~$o(1)$”. Here ${\mathrm{F}\mathrm{R}}_{\gamma }^n=(V,E)$ is the graph with $V=\{0,1{\}}^n$ and $(x,y)\in E$ whenever $\mathrm{\Delta }(x,y)=(1-\gamma )n$ (an even integer). In particular, we show the degree-$4$ SOS algorithm certifies the chromatic number lower bound “$\chi ({\mathrm{F}\mathrm{R}}_{1\mathrm{/}4}^n)=\omega (1)$”, even though ${\mathrm{F}\mathrm{R}}_{1\mathrm{/}4}^n$ is the canonical integrality gap instance for which standard SDP relaxations cannot even certify “$\chi ({\mathrm{F}\mathrm{R}}_{1\mathrm{/}4}^n)>3$”. Finally, we also give an SOS proof of (a generalization of) the sharp $(2,q)$-hypercontractive inequality for any even integer $q$.