A recursive theta body for hypergraphs

DOI10.1007/S00493-023-00040-9MaRDI QIDQ6081405zbMATH OpenOpenAlexFDO

Authors D. Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot, Frank Vallentin

Publication date 4 October 2023

Published in Combinatorica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2206.03929

zbMATH Keywords

Hoffman boundhypergraph chromatic numberhypergraph independence numberLovász theta numbersemidefinite programmingtheta body

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Abstract: The theta body of a graph, introduced by Gr"otschel, Lov'asz, and Schrijver in 1986, is a tractable relaxation of the independent-set polytope derived from the Lov'asz 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.

Recommendations

• The theta number of simplicial complexes
• The theta body and imperfection
• Theta bodies for polynomial ideals
• A recursive Lovász theta number for simplex-avoiding sets
• Independence in 5-uniform hypergraphs

Cited in

(1)

• Algebras, graphs and thetas

This page was built for publication: A recursive theta body for hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081405)