Premium
Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
Author(s) -
Bansal Nikhil,
Harris David G.
Publication year - 2023
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21086
Subject(s) - conjecture , mathematics , combinatorics , hypergraph , iterated function , rounding , matching (statistics) , rank (graph theory) , value (mathematics) , discrete mathematics , computer science , statistics , mathematical analysis , operating system
A classic conjecture of Füredi, Kahn, and Seymour (1993) states that any hypergraph with non‐negative edge weightsw ( e ) $$ w(e) $$ has a matchingM $$ 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 } $$ , wherew ∗$$ {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 } $$ .