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.

We describe a factor-revealing convex optimization problem for the integrality gap of the maximum-cut semidefinite programming relaxation: for each n 2 we present a convex optimization problem whose optimal value is the largest possible ratio between the value of an optimal rank-n solution to the relaxation and the value of an optimal cut. This problem is then used to compute lower bounds for the integrality gap.

For each (Formula presented.) we construct a measurable subset of the unit ball in (Formula presented.) that does not contain pairs of points at distance 1 and whose volume is greater than (Formula presented.) times the volume of the unit ball. This disproves a conjecture of Larman and Rogers from 1972.