Transversals and Independence in Hypergraphs with Applications

Michael Henning
University of Johannesburg

Christian L\"{o}wenstein
Ulm University

Anders Yeo
Singapore University of Technology and Design



Content: The transversal number, $\tau(H)$, of a hypergraph $H$ is the minimum cardinality of a subset of vertices in $H$ that has a nonempty intersection with every edge of $H$. A hypergraph is $k$-uniform if every edge has size~$k$. We present several bounds on the transversal number of uniform hypergraphs and discuss several conjectured bounds. Let $H$ be a hypergraph on $n$ vertices and $m$ edges. We discuss the Chv\'{a}tal-McDiarmid bound which states that for $k \ge 2$, if $H$ is a $k$-uniform hypergraph, then $\tau(H)\le ( n + \left\lfloor \frac k2 \right\rfloor m )/ \left\lfloor \frac{3k}2 \right\rfloor $. We characterize the connected hypergraphs that achieve equality in this bound. We present recent results on the conjecture that for all $k \ge 2$, if $H$ is a $k$-uniform hypergraph with maximum degree~$3$, then $\tau(H) \le n/k + m/6$. Motivated by the Thomass\'{e}-Yeo conjecture that every $5$-uniform hypergraph has a transversal of size at most~$\frac{4}{11}n$, we prove an upper bound of strictly less than~$(\frac{4}{11} + \frac{1}{72})n$ on the transversal number. We investigate upper bounds on the transversal number of linear hypergraphs, where a hypergraph is linear if every two edges intersect in at most one vertex. We also present results on independence and strong independence in hypergraphs. Applications of transversals in hypergraphs to, among others, colorings in hypergraphs, and domination and total domination in hypergraphs are given. The interplay with transversals in hypergraphs and total domination in graphs is explored.

Back to all abstracts