A Recursive Theta Body for Hypergraphs

Davi Castro-Silva, Fernando Mário de Oliveira Filho*, Lucas Slot, Frank Vallentin

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

38 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)909-938
Number of pages30
JournalCombinatorica
Volume43
Issue number5
DOIs
Publication statusPublished - 2023

Keywords

  • Hoffman bound
  • Hypergraph chromatic number
  • Hypergraph independence number
  • Lovász theta number
  • Semidefinite programming
  • Theta body

Fingerprint

Dive into the research topics of 'A Recursive Theta Body for Hypergraphs'. Together they form a unique fingerprint.

Cite this