A Sharp Bound on the Integrality Gap in the 3-set

Given a hypergraph with edges of size at most 3, the 3-set cover problem asks to determine the minimum size of a family of edges that covers the vertex set. As the problem is NP-hard, it is natural to consider its fractional (linear programming) relaxation, which is the most common tool for providing a lower bound on the value of the optimal solution. The ratio between the actual value and that of the fractional relaxation is called the integrality gap. A classic bound of Lovász implies that the integrality gap in this problem is at most 11/6. This has been improved to 5/3

by Fujito and Okumura. In this talk, we prove that the integrality gap is at most 3/2, which is best possible. A corollary of this result is that the vertex set of any 3-uniform, regular hypergraph on 𝑛 vertices can be covered by 𝑛/2 (or fewer) edges. This solves the 𝑘=3 case of a problem of de~A.~Moreira and Kohayakawa. As another application, we derive a certain variant of the Gale-Shapley stable marriage theorem for triples.