A Recursive Theta Body for Hypergraphs

Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot, Frank VallentinComb 2023 · OpenReview

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.

Introduction

In combinatorial optimization, finding the maximum independent set—the largest collection of vertices with no edges between them—is a notoriously difficult NP-hard problem. For standard graphs, the Lovász theta number ($\vartheta$) is a legendary "sandwich" parameter: it can be computed efficiently using semidefinite programming (SDP) and always sits between the independence number and the chromatic number of the complement graph.

Extending this success to hypergraphs (where edges can connect more than two vertices) has been a long-standing challenge. Previous generalizations often struggled to balance theoretical strength with computational feasibility. This research introduces a novel, recursive generalization of the theta body and theta number that preserves the elegant properties of the original graph version while scaling to higher-order interactions.

The core innovation is a recursive definition based on the concept of a "link."

  • The Link: For an $r$-uniform hypergraph (where every edge has $r$ vertices), the "link" of a vertex $x$ is an $(r-1)$-uniform hypergraph consisting of all sets that form an edge when combined with $x$.
  • Recursive Theta Body: The authors define the theta body of an $r$-uniform hypergraph by requiring that the rows of a specific matrix belong to the theta bodies of the links of its vertices. This recursion continues until it reaches the base case of standard graphs ($r=2$) or $r=1$ hypergraphs.
  • Optimization and Symmetry: For a fixed $r$, this recursive structure can be optimized in polynomial time. To handle large, highly symmetric hypergraphs like those based on the Hamming cube, the authors utilize group theory to reduce the massive SDP into a manageable optimization problem involving orthogonal polynomials (specifically Krawtchouk and Hahn polynomials).

Key Insights and Theoretical Connections

The "Sandwich" Property

The authors prove that their hypergraph theta body still "sandwiches" the true independent set polytope between itself and the simpler (but harder to optimize) clique-inequality polytope. This ensures the relaxation remains a powerful tool for bounding the independence number of hypergraphs.

Spectral Alignment

A major theoretical contribution is the connection to the high-dimensional Hoffman bound. The authors demonstrate that their theta number is always at least as strong as this recently developed spectral bound, providing a unified view of SDP and spectral methods in higher dimensions.

Applications and Results

As a theoretical work, the framework was evaluated on fundamental combinatorial structures rather than traditional datasets:

  • Mantel’s Theorem: The authors provide a new, SDP-based proof of Mantel’s Theorem, showing that the maximum number of edges in a triangle-free graph on $n$ vertices is exactly $\lfloor n^2/4 \rfloor$. Their theta number provides the tight bound of $n^2/4$.
  • The Hamming Cube ($\mathbb{H}^n$): The framework was used to study "triangle-avoiding" sets in the set of all binary strings of length $n$. The authors derived a closed-form formula for the theta number of these sets.
  • Exponential Decay Conjecture: Based on numerical results, the authors propose Conjecture 7.3: for certain parameters, the density of triangle-avoiding sets in the Hamming cube decays exponentially as the dimension $n$ increases, suggesting these sets become vanishingly rare in high-dimensional spaces.

Limitations and Future Work

While the method is polynomial-time for a fixed edge size $r$, the complexity grows significantly as $r$ increases. If $r$ scales with the number of vertices, the approach may become computationally intractable. Furthermore, while the original graph theta number behaves well under the "strong product" of graphs (Shannon capacity), it remains an open question whether this recursive hypergraph version satisfies similar product formulas. Proving the proposed exponential decay in the Hamming cube analytically remains a primary goal for future research.

Summary updated

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.
BibTeX
@inproceedings{castrosilva2023recursive,
  author = {Davi Castro-Silva and Fernando Mário de Oliveira Filho and Lucas Slot and Frank Vallentin},
  title = {{A Recursive Theta Body for Hypergraphs}},
  booktitle = {Comb},
  year = {2023},
  url = {https://openreview.net/forum?id=TskcotcOBs},
}
Figure