Upper transversals in hypergraphs

A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. For k >= 1, if H is a hypergraph with every edge of size at least k, then a k-transversal in H is a transversal that intersects every edge of H in at least k vertices. In particular, a 1-transversal is a transversal. The upper k-transversal number gamma(k)(H) of H is the maximum cardinality of a minimal k-transversal in H. We obtain asymptotically best possible lower bounds on gamma(k)(H) for uniform hypergraphs H. More precisely, we show that for r >= 2 and for every integer k is an element of[r], if H is a connected r-uniform hypergraph with n vertices, then gamma(k)(H) > 2/3 ((r-k+1)root n) For r > k >= 1 and epsilon > 0, we show that there exist infinitely many r-uniform hypergraphs, H-r,H-k'* of order n and a function f(r, k) of r and k satisfying gamma(k)(H-r,H-k*) < (1 + epsilon) . f(r, k) . (r-k+1)root n. (C) 2019 Elsevier Ltd. All rights reserved.