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

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

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

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

Research output: Contribution to journal › Article › peer-review

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_γⁿ has fractional size o(1)''.Here FR_γⁿ = (V, E) is the graph with V = (0,1)ⁿ 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ⁿ _1/4) = ω(1)", relaxations cannot even certify "Χ(FR_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.

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

Library availability

Discover UIUC Full Text

Cite this

@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",

note = "Funding Information: ∗Institute for Algebra, Johannes Kepler Universit{\"a}t. Supported by FWF grant Y464-N18. †Department of Computer Science, Carnegie Mellon University. Supported by NSF grants CCF-0747250 CCF-1116594, a Sloan fellowship, and a grant from the MSR–CMU Center for Computational Thinking. ‡Department of Computer Science, Columbia University. Research done while visiting CMU. §Also supported by a grant from the Simons Foundation (Award Number 252545). Publisher Copyright: {\textcopyright} 2016.",

year = "2016",

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

N1 - Funding Information: ∗Institute for Algebra, Johannes Kepler Universität. Supported by FWF grant Y464-N18. †Department of Computer Science, Carnegie Mellon University. Supported by NSF grants CCF-0747250 CCF-1116594, a Sloan fellowship, and a grant from the MSR–CMU Center for Computational Thinking. ‡Department of Computer Science, Columbia University. Research done while visiting CMU. §Also supported by a grant from the Simons Foundation (Award Number 252545). Publisher Copyright: © 2016.

PY - 2016

Y1 - 2016

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

SN - 2397-3129

VL - 4

SP - 1

EP - 21

JO - Discrete Analysis

JF - Discrete Analysis

IS - 2016

ER -

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

Abstract

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this