Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

Manuel Kauers, Ryan O'Donnell, Li Yang Tan, Yuan Zhou

Research output: Contribution to journalArticle

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 "Χ(FRn 1/4) = ω(1)", relaxations cannot even certify "Χ(FR1/4n > 3n. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

Original languageEnglish (US)
Pages (from-to)1-21
Number of pages21
JournalDiscrete Analysis
Volume4
Issue number2016
StatePublished - Jan 1 2016
Externally publishedYes

Fingerprint

Sum of squares
Reverse Inequality
Q-integers
Proof System
Graph in graph theory
Formulation
Generalization

ASJC Scopus subject areas

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

Cite this

Kauers, M., O'Donnell, R., Tan, L. Y., & Zhou, Y. (2016). Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. Discrete Analysis, 4(2016), 1-21.

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. / Kauers, Manuel; O'Donnell, Ryan; Tan, Li Yang; Zhou, Yuan.

In: Discrete Analysis, Vol. 4, No. 2016, 01.01.2016, p. 1-21.

Research output: Contribution to journalArticle

Kauers, M, O'Donnell, R, Tan, LY & Zhou, Y 2016, 'Hypercontractive inequalities via SOS, and the Frankl-Rödl graph', Discrete Analysis, vol. 4, no. 2016, pp. 1-21.
Kauers, Manuel ; O'Donnell, Ryan ; Tan, Li Yang ; Zhou, Yuan. / Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. In: Discrete Analysis. 2016 ; Vol. 4, No. 2016. pp. 1-21.
@article{05b09755c4494b7497e2224d49e80b70,
title = "Hypercontractive inequalities via SOS, and the Frankl-R{\"o}dl graph",
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{\"o}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 {"}Χ(FRn 1/4) = ω(1){"}, relaxations cannot even certify {"}Χ(FR1/4n > 3n. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.",
author = "Manuel Kauers and Ryan O'Donnell and Tan, {Li Yang} and Yuan Zhou",
year = "2016",
month = "1",
day = "1",
language = "English (US)",
volume = "4",
pages = "1--21",
journal = "Discrete Analysis",
issn = "2397-3129",
publisher = "Alliance of Diamond Open Access Journals",
number = "2016",

}

TY - JOUR

T1 - Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

AU - Kauers, Manuel

AU - O'Donnell, Ryan

AU - Tan, Li Yang

AU - Zhou, Yuan

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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 "Χ(FRn 1/4) = ω(1)", relaxations cannot even certify "Χ(FR1/4n > 3n. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

AB - 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 "Χ(FRn 1/4) = ω(1)", relaxations cannot even certify "Χ(FR1/4n > 3n. Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

UR - http://www.scopus.com/inward/record.url?scp=85038570800&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038570800&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85038570800

VL - 4

SP - 1

EP - 21

JO - Discrete Analysis

JF - Discrete Analysis

SN - 2397-3129

IS - 2016

ER -