Heavy transversals and indecomposable hypergraphs
The Gilmore-criterion [see \textit{C. Berge} and \textit{P. Duchet}, Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 49--55 (1975; Zbl 0325.05125)] says that a hypergraph \(H\) has the \(n\)-Helly property if and only if for every \(A\subseteq V(H)\), \(| A| =n+1\), the partial hypergraph \(H'\) with edge set \(\{e\in E(H) : | e\cap A| >n \}\) satisfies \( \tau(H')\leq 1\). The authors generalize this condition to weighted hypergraphs with multiple edges in the following way: There exists a function \(f(n)\) such that for all weighted \(n\)-Helly hypergraphs \((H,w)\), \(\tau(H^B)\leq 1\) holds for every \(B\subseteq V(H)\) if and only if \(\tau(H^A)\leq 1\) for every \(A\subseteq V(H)\) with \(| A| \leq f(n)\). Here \(\tau\) denotes the transversal number of the graph, \(w\) is a weight function on \(H\) and for a multisubset \(A\) of \(V(H)\) they denote by \(H^A\) the partial hypergraph generated by \(\{e\in E : | e\cap A| >w(A) \}\). Using a construction of \textit{Z. Füredi} [Discrete Math. 101, 59-64 (1992; Zbl 0755.05081)] for every \(n>9\) they construct an \(n\)-Helly hypergraph with two weights such that the smallest set of vertices satisfying \(\tau(H^S)>1\) has cardinality at least \((n/3)2^{(n-6)/2} \).
scientific article; zbMATH DE number 2099017