A $k$-hypertournament $H$ on $n$ vertices is a pair $(V(H),A(H))$, where $V(H)$ is a set of vertices and $A(H)$ is a set of $k$-tuples of vertices, called arcs, such that for any $k$-subset $S$ of $V(H)$, $A(H)$ contains exactly one of the $k!$ $k$-tuples whose entries belong to $S$. Clearly, a 2-hypertournament is a tournament. An antidirected path in $H$ is a sequence $x_1 a_1 x_2 a_2 x_3 \ldots x_{ t-1} a_{ t-1} x_t$ of distinct vertices $x_1, x_2, \ldots, x_t$ and distinct arcs $a_1, a_{ 2},\ldots, a_{ t-1}$ such that for any $i\in \{ 2,3,\ldots, t-1\}$, either $x_{ i-1}$ precedes $x_{ i}$ in $a_{ i-1}$ and $x_{ i+1}$ precedes $x_{ i}$ in $a_{ i}$, or $x_{ i}$ precedes $x_{ i-1}$ in $a_{ i-1}$ and $x_{ i}$ precedes $x_{ i+1}$ in $a_{ i}$. An antidirected path that includes all vertices of $H$ is known as an antidirected hamiltonian path. In this paper, we prove that except for four hypertournaments, $T_3^{ c}, T_5^{ c}, T_7^{ c}$ and $H_{ 4}$, every $k$-hypertournament with $n$ vetices, where $2\leq k\leq n-1$, has an antidirected hamiltonian path, which extends Gr\"{ u}nbaum's theorem on tournaments (except for three tournaments, $T_3^{ c}, T_5^{ c}$ and $T_7^{ c}$, every tournament has an antidirected hamiltonian path).
Categories: math.CO