Heavy Transversals and Indecomposable Hypergraphs

摘要

A weighted hypergraph is a hypergraph H = (V, E) with a weighting function $ w:V to R $ , where R is the set of reals. A multiset S ⊆ V generates a partial hypergraph H S with edges $ {left{ {e in E{kern 1pt} :{kern 1pt} {left| {e cap S} right|} > w{left( S right)}} right}} $ , where both the cardinality $ {left| {e cap S} right|} $ and the total weight w(S) are counted with multiplicities of vertices in S. The transversal number of H is represented by τ(H). We prove the following: there exists a function f(n) such that, for any weighted n-Helly hypergraph H, τ(H B ) ≤ 1, for all multisets B ⊆ V if and only if τ(H A ) ≤ 1, for all multisets A ⊆ V with $ {left| A right|} leqslant f{left( n right)} $ . We provide lower and upper bounds for f(n) using a link between indecomposable hypergraphs and critical weighted n-Helly hypergraphs.