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.
| Additional Metadata | |
|---|---|
| , , , , , | |
| doi.org/10.1007/s00493-023-00040-9 | |
| Combinatorica | |
| Mixed-Integer Nonlinear Optimization | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Castro-Silva, D., de Oliveira Filho, F. M., Slot, L., & Vallentin, F. (2023). A recursive theta body for hypergraphs. Combinatorica. doi:10.1007/s00493-023-00040-9 |
|
