论文标题
集团因素游戏的阈值偏见
The threshold bias of the clique-factor game
论文作者
论文摘要
让$ r \ ge 4 $成为整数，并在r \ mathbb {z} $中的完整图$ k_n $上考虑以下游戏：两个播放器，制造商和断路器，交替声称以前无人认可的$ k_n $的边缘，因此，在每个转折点中，Maker Maker声称一个且Breaker sake $ b \ in Mathbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb bbbbbbbbbbbbb {z} $。如果她的图形包含$ k_r $ - 因子，则会获胜，该$ n/r $ $ $ tertex-disschoint副本的$ k_r $，否则会赢。换句话说，我们认为$ b $ bialed $ k_r $ - 因素制造商 - 破坏者游戏。我们证明此游戏的阈值偏差为$ n^{2/（r+2）} $。这迈出了确定阈值偏差，以使限制度跨度图的阈值偏差扩展，并扩展了Allen等人的结果，后者将Case $ r \ in \ in \ {3,4 \} $最高到对数因子。
Let $r \ge 4$ be an integer and consider the following game on the complete graph $K_n$ for $n \in r \mathbb{Z}$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b \in \mathbb{N}$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider a $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^{2/(r+2)}$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al.\ who resolved the case $r \in \{3,4\}$ up to a logarithmic factor.
