Transversals in 4-uniform hypergraphs (Q727047)

Summary: Let \(H\) be a \(4\)-uniform hypergraph on \(n\) vertices. The transversal number \(\tau(H)\) of \(H\) is the minimum number of vertices that intersect every edge. The result in [J. Comb. Theory, Ser. B 50, No. 1, 129--133 (1990; Zbl 0739.05068)] by \textit{F.-C. Lai} and \textit{G. H. Chang} implies that \(\tau(H) \leq 7n/18\) when \(H\) is \(3\)-regular. The main result in [Combinatorica 27, No. 4, 473--487 (2007; Zbl 1164.05052)] by \textit{S. Thomassé} and \textit{A. Yeo} implies an improved bound of \(\tau(H) \leq 8n/21\). We provide a further improvement and prove that \(\tau(H) \leq 3n/8\), which is best possible due to a hypergraph of order eight. More generally, we show that if \(H\) is a \(4\)-uniform hypergraph on \(n\) vertices and \(m\) edges with maximum degree \(\Delta(H) \leq 3\), then \(\tau(H) \leq n/4 + m/6\), which proves a known conjecture. We show that an easy corollary of our main result is that if \(H\) is a \(4\)-uniform hypergraph with \(n\) vertices and \(n\) edges, then \(\tau(H) \leq \frac{3}{7}n\), which was the main result of the Thomassé-Yeo paper [loc. cit.].