Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture

Abstract

A classic conjecture of Füredi, Kahn and Seymour (1993) states that given any hypergraph with non-negative edge weights $w(e)$, there exists a matching $M$ such that ${\sum }_{e\in M}(|e|-1+1/|e|)w(e)\ge w^{\ast }$, where $w^{\ast }$ is the value of an optimum fractional matching. We show the conjecture is true for rank-3 hypergraphs, and is achieved by a natural iterated rounding algorithm. While the general conjecture remains open, we give several new improved bounds. In particular, we show that the iterated rounding algorithm gives ${\sum }_{e\in M}(|e|-\delta (e))w(e)\ge w^{\ast }$, where $\delta (e)=|e|/(|e{|}^2+|e|-1)$, improving upon the baseline guarantee of ${\sum }_{e\in M}|e|w(e)\ge w^{\ast }$.