A Recursive Theta Body for Hypergraphs

Journal article (2023)

Authors

Davi Castro-Silva Centrum Wiskunde & Informatica (CWI)
F.M. de Oliveira Filho Discrete Mathematics and Optimization - EEMCS
Lucas Slot ETH Zürich
Frank Vallentin Universität zu Köln
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Copyright: © 2023 Davi Castro-Silva, F.M. de Oliveira Filho, Lucas Slot, Frank Vallentin
DOI: https://doi.org/10.1007/s00493-023-00040-9
More Info
expand_more

Published Date

2023

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

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.