论文标题
构造障碍游戏
The Constructor-Blocker Game
论文作者
论文摘要
我们研究了Turán问题的以下游戏版本。对于两个固定的图形$ f $和$ h $，两个播放器和构造函数和阻止器，或者声称完整图$ k_n $的无人认领边缘。构造函数只能声称边缘，因此他永远不会声称任何$ f $的副本的所有边缘，即他的图必须保留$ f $ free，而Blocker可以在没有限制的情况下要求无人认领的边缘。当构造函数无法索取进一步的边缘或所有边缘索赔时，游戏结束。游戏的分数是$ h $的副本数量，以及构造函数声称的所有边缘。构造函数的目的是最大程度地提高分数，而Blocker试图保持分数尽可能低。我们用$ g（N，H，F）$表示，当两个玩家都在最佳玩法和构造师开始游戏时，游戏的得分。 在本文中，当$ f $和$ h $都是星星时，当$ f $ f = p_4 $，$ h = p_3 $时，我们将获得$ g（n，h，f）$的确切值。我们确定$ g（n，h，f）$的渐近学当$ f $是一颗星时，而$ h $是一棵树，当$ f = p_5 $，$ h = k_3 $时，我们在$ g（n，p_4，p_5）$上得出上下界限。
We study the following game version of the generalized graph Turán problem. For two fixed graphs $F$ and $H$, two players, Constructor and Blocker, alternately claim unclaimed edges of the complete graph $K_n$. Constructor can only claim edges so that he never claims all edges of any copy of $F$, i.e. his graph must remain $F$-free, while Blocker can claim unclaimed edges without restrictions. The game ends when Constructor cannot claim further edges or when all edges have been claimed. The score of the game is the number of copies of $H$ with all edges claimed by Constructor. Constructor's aim is to maximize the score, while Blocker tries to keep the score as low as possible. We denote by $g(n,H,F)$ the score of the game when both players play optimally and Constructor starts the game. In this paper, we obtain the exact value of $g(n,H,F)$ when both $F$ and $H$ are stars and when $F=P_4$, $H=P_3$. We determine the asymptotics of $g(n,H,F)$ when $F$ is a star and $H$ is a tree and when $F=P_5$, $H=K_3$, and we derive upper and lower bounds on $g(n,P_4,P_5)$.
