Hypergraphs with large transversal number

For k >= 2, let H be a k-uniform hypergraph on n vertices and m edges. The transversal number tau(H) of H is the minimum number of vertices that intersect every edge. We consider the following question: Is tau(H) <= n/k + m/6? For k >= 4, we show that the inequality in the question does not always hold. However, the examples we present all satisfy Delta(H) >= 4. A natural question is therefore whether tau(H) <= n/k + m/6 holds when Delta(H) <= 3. Although we do not know the answer, we prove that the bound holds when Delta(H) <= 2, and for that case we characterize the hypergraphs for which equality holds. Furthermore, we prove that the bound holds when k = 2 (with no restriction on the maximum degree), and again there we characterize the hypergraphs for which equality holds. Chvatal and McDiarmid [V. Chvatal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26] proved that the bound holds for k = 3 (again with no restriction on the maximum degree). We characterize the extremal hypergraphs in this case. (C) 2013 Elsevier B.V. All rights reserved.