A Recursive Theta Body for Hypergraphs
Davi Castro-Silva (Centrum Wiskunde & Informatica (CWI))
Fernando Mário De Oliveira Filho (TU Delft - Discrete Mathematics and Optimization)
Lucas Slot (ETH Zürich)
Frank Vallentin (Universität zu Köln)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The theta body of a graph, introduced by Grötschel, Lovász, and Schrijver (in 1986), is a tractable relaxation of the independent-set polytope derived from the Lovász theta number. In this paper, we recursively extend the theta body, and hence the theta number, to hypergraphs. We obtain fundamental properties of this extension and relate it to the high-dimensional Hoffman bound of Filmus, Golubev, and Lifshitz. We discuss two applications: triangle-free graphs and Mantel’s theorem, and bounds on the density of triangle-avoiding sets in the Hamming cube.
help_outline