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 ϒ_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)>[Formula presented]nr−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)⋅nr−k+1.