论文标题
服务员 - 客户式集团因素游戏
Waiter-Client Clique-Factor Game
论文作者
论文摘要
修复两个整数$ n，k $，$ n $可除以$ k $，并在$ k_n $的边缘考虑两个玩家，服务员和客户端玩的游戏。从所有被标记为无人认领的边缘开始，在每回合中，服务员选择两个但无人认领的边缘。然后，客户端选择将其中一个添加到客户端的图表中，而另一个边缘则将其添加到服务员的图中。如果服务员最终强迫客户在客户端的图中创建$ k_k $ - factor，则会获胜。如果她不这样做，客户将获胜。 对于固定的$ k $和足够大的$ n $，可以很容易地表明，如果服务员最佳地打球（尤其是，这是我们结果的直接结果，即对于这样的$ n $，服务员可以很快获胜）。 Clemens等人提出的问题。如果服务员的目标是尽可能快地赢得比赛，则游戏将持续多长时间，客户会尽力推迟她，并且他们俩都在最佳地比赛中发挥了作用。我们用$τ_{wc}（\ Mathcal {f} _ {n，k_k- \ text {fac}}，1）$表示最佳数量的回合数。在本文中，我们获得了大型$ k $的第一个非平凡的下限。加上遵循Clemens等人的策略的简单上限，这给出了$ 2^{k/3-o（k）} n \Leqτ_{wc}（\ Mathcal {f} _ {n，k_k- \ k_k- \ k_k- \ text {fack}}，1）仅取决于$ k $和$ o（k）$项的常数也独立于$ n $。
Fix two integers $n, k$, with $n$ divisible by $k$, and consider the following game played by two players, Waiter and Client, on the edges of $K_n$. Starting with all the edges marked as unclaimed, in each round, Waiter picks two yet unclaimed edges. Client then chooses one of these edges to be added to Client's graph, while the other edge is added to Waiter's graph. Waiter wins if she eventually forces Client to create a $K_k$-factor in Client's graph. If she does not manage to do that, Client wins. For fixed $k$ and large enough $n$, it can be easily shown that Waiter wins if she plays optimally (in particular, this is an immediate consequence of our result that for such $n$, Waiter can win quite fast). The question posed by Clemens et al. is how long the game will last if Waiter aims to win as fast as she can, Client tries to delay her as much as he can, and they both play optimally. We denote this optimal number of rounds by $τ_{WC}(\mathcal{F}_{n,K_k-\text{fac}},1 ) $. In the present paper, we obtain the first non-trivial lower bound on this quantity for large $k$. Together with a simple upper bound following the strategy of Clemens et al., this gives $2^{k/3-o(k)}n \leq τ_{WC}(\mathcal{F}_{n,K_k-\text{fac}},1 ) \leq 2^k\frac{n}{k}+C(k)$, where $C(k)$ is a constant dependent only on $k$ and the $o(k)$ term is independent of $n$ as well.
