Transversals in 4-uniform hypergraphs

Michael A. Henning¹ ; Anders Yeo²

¹University of Johannesburg
²University of Southern Denmark

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

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].

Détail

DOI : 10.37236/5304

Classification : 05D15, 05C65, 05C69
Mots-clés : transversal, hypergraph