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$.
@article{10_37236_7267,
author = {Michael A. Henning and Anders Yeo},
title = {On upper transversals in 3-uniform hypergraphs},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {4},
doi = {10.37236/7267},
zbl = {1402.05159},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7267/}
}
TY - JOUR
AU - Michael A. Henning
AU - Anders Yeo
TI - On upper transversals in 3-uniform hypergraphs
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/7267/
DO - 10.37236/7267
ID - 10_37236_7267
ER -
%0 Journal Article
%A Michael A. Henning
%A Anders Yeo
%T On upper transversals in 3-uniform hypergraphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7267/
%R 10.37236/7267
%F 10_37236_7267
Michael A. Henning; Anders Yeo. On upper transversals in 3-uniform hypergraphs. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7267
