On Upper Transversals in 3-Uniform Hypergraphs

Abstract

A set $S$ of vertices in a hypergraph $H$ is a transversal if it has a nonempty intersection with every edge of $H$. The upper transversal number $\Upsilon(H)$ of $H$ is the maximum cardinality of a minimal transversal in $H$. We show that if $H$ is a connected $3$-uniform hypergraph of order $n$, then $\Upsilon(H) > 1.4855 \sqrt[3]{n} - 2$. For $n$ sufficiently large, we construct infinitely many connected $3$-uniform hypergraphs, $H$, of order~$n$ satisfying $\Upsilon(H) < 2.5199 \sqrt[3]{n}$. We conjecture that $\displaystyle{\sup_{n \to \infty}  \, \left( \inf  \frac{ \Upsilon(H) }{ \sqrt[3]{n} } \right) = \sqrt[3]{16} }$, where the infimum is taken over all connected $3$-uniform hypergraphs $H$ of order $n$.