Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs

Abstract

While the edges of every tournament can be covered with two spanning acyclic subgraphs, this is not so if we set out to cover all acyclic $H$-subgraphs of a tournament with spanning acyclic subgraphs, even for very simple $H$ such as the $2$-edge directed path or the $2$-edge out-star. We prove new bounds for the minimum number of elements in such coverings and for some $H$ our bounds determine the exact order of magnitude.

A $k$-tournament is an orientation of the complete $k$-graph, where each $k$-set is given a total order (so tournaments are $2$-tournaments). As opposed to tournaments, already covering the edges of a $3$-tournament with the minimum number of spanning acyclic subhypergraphs is a nontrivial problem. We prove a new lower bound for this problem which asymptotically matches the known lower bound of covering all ordered triples of a set.