Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture. Issue 1 (16th April 2022)

• Record Type: Journal Article
• Authors: Bansal, Nikhil; Harris, David G.
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 52
• Page End: 67
• Publication Date: 2022-04-16
• Subjects: hypergraph -- iterative rounding -- matching; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21086
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ∗ $$ {\sum}_{e\in M}\left(|e|-1+1/|e|\right)\kern0.3em w(e)\ge {w}^{\ast } $$, where w ∗ $$ {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 ∑ e ∈ M ( | e | − δ ( e ) ) w ( e ) ≥ w ∗ $$ {\sum}_{e\in M}\left(|e|-\delta (e)\right)\kern0.3em w(e)\ge {w}^{\ast } $$, where δ ( e ) = | e | / ( | e | 2 + | e | − 1 ) $$ \delta (e)=\mid e\mid /\left({\left|e\right|}^2+|e|-1\right) $$, improving upon the baseline guarantee of ∑ e ∈ M | e | w ( e ) ≥ w ∗ $$ {\sum}_{e\in M}\mid e\mid \kern0.3em w(e)\ge {w}^{\ast } $$ .