论文标题
$ g_ {n，p} $上的沃克破坏游戏
Walker-Breaker Games on $G_{n,p}$
论文作者
论文摘要
制造商突破性连接游戏和汉密尔顿自行车游戏属于位置游戏理论中最佳研究的游戏，包括偏见的游戏，随机图上的游戏和快速获胜策略。最近，连接器的游戏版本，其中连接器必须声称边缘，以使她的图形在整个游戏中保持连接，以及Walker-Break-Breaker游戏变体，沃克必须根据步行的边缘声称自己的边缘受到了越来越多的关注。 例如，伦敦和Pluhár在完整的图表$ k_n $上研究了连接器断开连接游戏的阈值偏差，并表明当制造商的偏见等于$ 1 $或$ 2 $时，情况有很大的区别。此外，第一和第三作者以及Kirsch的最新结果表明，在随机图$ g \ sim g_ {n，p}上，$（2：2）$（2：2）$（2：2）的阈值概率$ P $是$ n^{ - 2/3+O（1）} $。我们将这一结果进一步发展为沃克（Walker-Breaker）游戏，并证明这种概率也足以使沃克（Walker）创建汉密尔顿周期。
The Maker-Breaker connectivity game and Hamilton cycle game belong to the best studied games in positional games theory, including results on biased games, games on random graphs and fast winning strategies. Recently, the Connector-Breaker game variant, in which Connector has to claim edges such that her graph stays connected throughout the game, as well as the Walker-Breaker game variant, in which Walker has to claim her edges according to a walk, have received growing attention. For instance, London and Pluhár studied the threshold bias for the Connector-Breaker connectivity game on a complete graph $K_n$, and showed that there is a big difference between the cases when Maker's bias equals $1$ or $2$. Moreover, a recent result by the first and third author as well as Kirsch shows that the threshold probability $p$ for the $(2:2)$ Connector-Breaker connectivity game on a random graph $G\sim G_{n,p}$ is of order $n^{-2/3+o(1)}$. We extent this result further to Walker-Breaker games and prove that this probability is also enough for Walker to create a Hamilton cycle.
