论文标题
用于超图的递归theta主体
A recursive theta body for hypergraphs
论文作者
论文摘要
Grötschel，Lovász和Schrijver在1986年引入的图形的theta体是对源自lovászTheta数字的独立集合的可拖延松弛。在本文中，我们递归地将theta主体延伸到超图。我们获得了此扩展的基本特性，并将其与Filmus，Golubev和Lifshitz的高维霍夫曼（Hoffman Bound）联系起来。我们讨论了两个应用程序：无三角形图和壁炉架定理，以及在锤子立方体中避开三角形集的密度的边界。
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.
