Domination in tournaments
Domination in tournaments
复制标题
在锦标赛中称霸
DOI：
10.1016/j.jctb.2017.10.001
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Thomassé, Stéphan
中科院分区：
文献类型：
--
作者：
Chudnovsky, Maria;Kim, Ringi;Liu, Chun-Hung;Seymour, Paul;Thomassé, Stéphan
我们研究了吴和辉的以下猜想：对于每场比赛S，无S比赛类别都有有界支配数。我们证明这个猜想一般来说是错误的，但是当 Si 是 2-可色的（即它的顶点集可以划分为两个传递集）时是正确的；后者是直接应用 VC 维度。我们的目标是超越这一点；我们给出了一个满足猜想的非2色锦标赛S。这里的关键因素（也许比结果本身更有趣）是我们通过证明破碎集的集合是稀疏的来克服 VC 维的无界性。
We investigate the following conjecture of Hehui Wu: for every tournamentS, the class ofS-free tournaments has bounded domination number. We show that the conjecture is false in general, but true whenSis 2-colourable (that is, its vertex set can be partitioned into two transitive sets); the latter follows by a direct application of VC-dimension. Our goal is to go beyond this; we give a non-2-colourable tournamentSthat satisfies the conjecture. The key ingredient here (perhaps more interesting than the result itself) is that we overcome the unboundedness of the VC-dimension by showing that the set of shattered sets is sparse.
登录
查看更多内容
DOI：
--
发表时间：
1994
期刊：
Comb.
影响因子：
--
作者：
G. Ding;P. Seymour;P. Winkler
通讯作者：
P. Winkler
锦标赛传递色彩的主导地位
DOI：
--
发表时间：
2013
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Dömötör Pálvölgyi;A. Gyárfás
通讯作者：
A. Gyárfás
影响因子：
1.1
作者：
David C. Fisher;J. Ryan
通讯作者：
J. Ryan
关于在锦标赛中寻找最小统治盘
影响因子：
1.1
作者：
N. Megiddo;U. Vishkin
通讯作者：
U. Vishkin
在 k-major 锦标赛中占据主导地位
DOI：
--
发表时间：
2006
期刊：
J. Comb. Theory B
影响因子：
--
作者：
N. Alon;G. Brightwell;H. Kierstead;A. Kostochka;P. Winkler
通讯作者：
P. Winkler