Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs
Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs
复制标题
用跨越非循环子图覆盖（超级）锦标赛的小子图
DOI：
10.37236/9336
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
R. Yuster
中科院分区：
文献类型：
--
作者：
R. Yuster
虽然每个竞赛图的边都可以被两个生成无环子图覆盖，但如果我们用生成无环子图覆盖竞赛图的所有无环$H$-子图，即使是非常简单的$H$，如$2$-边有向路或$2$-边出星，情况也不是这样。我们证明了新的界限的最小数量的元素在这样的覆盖和一些H$我们的界限确定的确切数量级。
一个$k$-竞赛图是完全$k$-图的一个定向图，其中每个$k$-集被赋予一个全序（所以竞赛图是$2$-竞赛图）。与竞赛图相反，用最少数量的生成无环子超图覆盖$3$-竞赛图的边是一个非平凡的问题。我们证明了这个问题的一个新的下界渐近匹配已知的下限覆盖所有有序三元组的集合。
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.