Upper transversals in hypergraphs.

Abstract 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 ϒ k (H) of H is the maximum cardinality of a minimal k -transversal in H. We obtain asymptotically best possible lower bounds on ϒ k (H) for uniform hypergraphs H. More precisely, we show that for r ≥ 2 and for every integer k ∈ [ r ] , if H is a connected r -uniform hypergraph with n vertices, then ϒ k (H) > 2 3 n r − k + 1 . For r > k ≥ 1 and ε > 0 , we show that there exist infinitely many r -uniform hypergraphs, H r , k ∗ , of order n and a function f (r , k) of r and k satisfying ϒ k (H r , k ∗) < (1 + ε) ⋅ f (r , k) ⋅ n r − k + 1. [ABSTRACT FROM AUTHOR]