Fast winning strategies in Maker-Breaker games
Fast winning strategies in Maker-Breaker games
复制标题
Maker-Breaker 游戏中的快速制胜策略
DOI：
10.1016/j.jctb.2008.04.001
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Tibor Szabó
中科院分区：
文献类型：
--
作者：
Dan Hefetz;Michael Krivelevich;Miloš Stojaković;Tibor Szabó
我们考虑完全图Knon n个顶点的边集上的无偏Maker-Breaker对策。不少这样的游戏在文献中进行了研究，并被称为制造商的胜利。在这里，我们感兴趣的是估计庄家为了赢得这些游戏所需的最少移动次数。我们证明了以下结果，足够大的n：其他几个相关的结果以及派生。
We consider unbiased Maker–Breaker games played on the edge set of the complete graph Knon n vertices. Quite a few such games were researched in the literature and are known to be Maker's win. Here we are interested in estimating the minimum number of moves needed for Maker in order to win these games. We prove the following results, for sufficiently large n: Several other related results are derived as well.