Heavy transversals and indecomposable hypergraphs
type: Item
instance of: scholarly article
title: Heavy transversals and indecomposable hypergraphs
zbMATH Open document ID: 1047.05031
author: André E. Kézdy
author: Jeno Lehel
author: Robert C. Powers
published in: Combinatorica
publication date: 2004-09-07T00:00:00Z
review text: 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} \).
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 05D15
zbMATH DE Number: 2099017
zbMATH Keywords: weigthed hypergraphs
zbMATH Keywords: \(n\)-Helly property
zbMATH Keywords: indecomposable
reviewed by: Csaba Szabó
MaRDI profile type: Publication
full work available at URL: s00493-003-0023-2
OpenAlex ID: W2028351601
DOI: 10.1007/S00493-003-0023-2
description: scientific article; zbMATH DE number 2099017