## Abstract

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 < γ ≤ 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4gamma;]certifies the statement "the maximum independent set in the Frankl-Rödl graph FR_{γ}^{n} has fractional size o(1)''.Here FR_{γ}^{n} = (V, E) is the graph with V = (0,1)^{n} and (x, y) ∈ E wheneverΔ(x, y) = (1-γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "Χ(FR^{n} _{1/4}) = ω(1)", relaxations cannot even certify "Χ(FR_{1/4}^{n} > 3^{n}. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

Original language | English (US) |
---|---|

Pages (from-to) | 1-21 |

Number of pages | 21 |

Journal | Discrete Analysis |

Volume | 4 |

Issue number | 2016 |

State | Published - 2016 |

Externally published | Yes |

## ASJC Scopus subject areas

- Algebra and Number Theory
- Geometry and Topology
- Discrete Mathematics and Combinatorics