论文标题
随机扰动图上的位置游戏
Positional games on randomly perturbed graphs
论文作者
论文摘要
Maker-Breaker Games在HyperGraph $（x，\ Mathcal {f}）$上播放，其中$ \ Mathcal {f} \ subseteq 2^x $表示获胜的家族。两位玩家都从董事会$ x $中索取了预定义的边缘（称为偏差），如果她能够占据\ Mathcal {f} $中的任何获胜套装$ f \，则制造商将赢得游戏。这些游戏在完整的图表$ k_n $或随机图上播放时对这些游戏进行了很好的研究，$ g_ {n，p} $。在本文中，我们考虑在随机的扰动图上播放的制造商打破游戏。这些图由确定图$g_α$的结合，至少$αn$和二项式随机图$ g_ {n，p} $。根据$α$和Breaker's Bias $ b $，我们确定了赢得Hamiltonity游戏的阈值概率的顺序，以及$G_α\ Cup G_ {n，p} $上的$ K $ -Connectivity Game，我们在$ b = 1 $时讨论$ h $ -game。此外，我们为所有提到的游戏的服务员 - 客户版本提供了最佳结果。
Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game if she is able to occupy any winning set $F \in \mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_α$ with minimum degree at least $αn$ and a binomial random graph $G_{n,p}$. Depending on $α$ and Breaker's bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_α\cup G_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Client versions of all mentioned games.
