# Bounds on the Game Transversal Number in Hypergraphs

Research paper by **Csilla Bujtás, Michael A. Henning, Zsolt Tuza**

Indexed on: **19 Jan '16**Published on: **19 Jan '16**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $H = (V,E)$ be a hypergraph with vertex set $V$ and edge set $E$ of order
$\nH = |V|$ and size $\mH = |E|$. A transversal in $H$ is a subset of vertices
in $H$ that has a nonempty intersection with every edge of $H$. A vertex hits
an edge if it belongs to that edge. The transversal game played on $H$ involves
of two players, \emph{Edge-hitter} and \emph{Staller}, who take turns choosing
a vertex from $H$. Each vertex chosen must hit at least one edge not hit by the
vertices previously chosen. The game ends when the set of vertices chosen
becomes a transversal in $H$. Edge-hitter wishes to minimize the number of
vertices chosen in the game, while Staller wishes to maximize it. The
\emph{game transversal number}, $\tau_g(H)$, of $H$ is the number of vertices
chosen when Edge-hitter starts the game and both players play optimally. We
compare the game transversal number of a hypergraph with its transversal
number, and also present an important fact concerning the monotonicity of
$\tau_g$, that we call the Transversal Continuation Principle. It is known that
if $H$ is a hypergraph with all edges of size at least~$2$, and $H$ is not a
$4$-cycle, then $\tau_g(H) \le \frac{4}{11}(\nH+\mH)$; and if $H$ is a
(loopless) graph, then $\tau_g(H) \le \frac{1}{3}(\nH + \mH + 1)$. We prove
that if $H$ is a $3$-uniform hypergraph, then $\tau_g(H) \le \frac{5}{16}(\nH +
\mH)$, and if $H$ is $4$-uniform, then $\tau_g(H) \le \frac{71}{252}(\nH +
\mH)$.