Covering small subgraphs of (hyper)tournaments with spanning acyclic subgraphs (Q2205125)

Summary: 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.