Computer Science/Discrete Mathematics Seminar I

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 $n$ vertices can be covered by $n/2$ (or fewer) edges. This solves the $k=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.