×

Small transversals in uniform hypergraphs. (English) Zbl 0848.05049

Summary: Suppose that in a collection \(H\) of \(r\)-element sets, for any \(p\) sets there is a set of at most \(t\) elements that meets all of them. We study the following problem: find a sharp upper bound \(f(r,p,t)\) on the cardinality of a smallest set meeting all members of \(H\). We determine the exact values of \(f(r,p,2)\) for \(p \leq 6 \) and every \(r\), of \(f(r,t + 1,t)\) and \(f(r,t + 2, t)\) for every \(r\) and \(t\), and prove that \(f(r,p,t) = O(rp^{- 1/t})\) for every fixed \(t\) when \(r,p \to \infty\).

MSC:

05C65 Hypergraphs
PDFBibTeX XMLCite