  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 \leq 1/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{FR}^{n}_{\gamma}$ has
fractional size~$o(1)$". Here $\mathrm{FR}^{n}_{\gamma} = (V,E)$ is the graph
with $V = \{0,1\}^n$ and $(x,y) \in E$ whenever $\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{FR}^{n}_{1/4}) = \omega(1)$",
even though $\mathrm{FR}^{n}_{1/4}$ is the canonical integrality gap instance
for which standard SDP relaxations cannot even certify
"$\chi(\mathrm{FR}^{n}_{1/4}) > 3$". Finally, we also give an SOS proof of (a
generalization of) the sharp $(2,q)$-hypercontractive inequality for any even
integer $q$.
