Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture. Issue 1 (16th April 2022) - Bansal, Nikhil; Harris, David G.
Abstract: A classic conjecture of Füredi, Kahn, and Seymour (1993) states that any hypergraph with non‐negative edge weights w ( e ) w(e) has a matching M M such that ∑ e ∈ M ( | e | − 1 + 1 / | e | ) w ( e ) ≥ w ∗ _eM(|e|-1+1/|e|)0.3em w(e)w^* , where w ∗ w^* 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 ∑ e ∈ M ( | e | − δ ( e ) ) w ( e ) ≥ w ∗ _eM(|e|-δ (e))0.3em w(e)w^* , where δ ( e ) = | e | / ( | e | 2 + | e | − 1 ) δ (e)=e/(|e|^2+|e|-1) , improving upon the baseline guarantee of ∑ e ∈ M | e | w ( e ) ≥ w ∗ _eMe0.3em w(e)w^* .