Transversals in $4$-uniform linear hypergraphs

Abstract

Let $H$ be a hypergraph of order $n_H=|V(H)|$ and size $m_H=|E(H)|$. The transversal number $\tau (H)$ of a hypergraph $H$ is the minimum number of vertices that intersect every edge of $H$. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A $k$-uniform hypergraph has all edges of size $k$. For $k\ge 2$, let ${\mathcal{L}}_k$ denote the class of $k$-uniform linear hypergraphs. We consider the problem of determining the best possible constants $q_k$ (which depends only on $k$) such that $\tau (H)\le q_k(n_H+m_H)$ for all $H\in {\mathcal{L}}_k$. It is known that $q_2=\frac{1}{3}$ and $q_3=\frac{1}{4}$. In this paper we show that $q_4=\frac{1}{5}$, which is better than for non-linear hypergraphs. Using the affine plane $AG(2,4)$ of order 4, we show there are a large number of densities of hypergraphs $H\in {\mathcal{L}}_4$ such that $\tau (H)=\frac{1}{5}(n_H+m_H)$.