
Michael A. Henning

Anders Yeo
Keywords:
Transversal, Hypergraph
Abstract
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. Combin. Theory Ser. B 50 (1990), 129—133] by Lai and Chang implies that $\tau(H) \le 7n/18$ when $H$ is $3$regular. The main result in [Combinatorica 27 (2007), 473—487] by Thomassé and Yeo implies an improved bound of $\tau(H) \le 8n/21$. We provide a further improvement and prove that $\tau(H) \le 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) \le 3$, then $\tau(H) \le 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) \le \frac{3}{7}n$, which was the main result of the ThomasséYeo paper [Combinatorica 27 (2007), 473—487].
Author Biographies
Michael A. Henning, University of Johannesburg
Department of Pure and Applied Mathematics
Anders Yeo, University of Southern Denmark
Department of Mathematics and Computer Science