On saturation games

详细信息    查看全文

• 作者：Dan Hefetz^a ; ^{d.hefetz@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Michael Krivelevich^b ; ^{krivelev@post.tau.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Alon Naor^b ; ^{alonnaor@post.tau.ac.il" class="auth_mail" title="E-mail the corresponding author} ; Milo&scaron ; Stojakovi膰^c ; ^{milos.stojakovic@dmi.uns.ac.rs" class="auth_mail" title="E-mail the corresponding author}
• 刊名：European Journal of Combinatorics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：51
• 期：Complete
• 页码：315-335
• 全文大小：462 K

文摘

A graph G=(V,E)$G=(V,E)$ is said to be saturated   with respect to a monotone increasing graph property deab18b1d942ec29f0" title="Click to view the MathML source">P$\mathcal{P}$, if G∉P$G\notin \mathcal{P}$ but G∪{e}∈P$G\cup \left\{e\right\}\in \mathcal{P}$ for every $e\in \left(\genfrac{}{}{00}{}{V}{2}\right)鈭?/mo><mi>E</mi>$. The saturation game  (n,P)$(n,\mathcal{P})$ is played as follows. Two players, called Mini and Max, progressively build a graph G⊆K_n$G\subseteq K_n$, which does not satisfy deab18b1d942ec29f0" title="Click to view the MathML source">P$\mathcal{P}$. Starting with the empty graph on n$n$ vertices, the two players take turns adding edges , for which G∪{e}∉P$G\cup \left\{e\right\}\notin \mathcal{P}$, until no such edge exists (i.e. until G$G$ becomes deab18b1d942ec29f0" title="Click to view the MathML source">P$\mathcal{P}$-saturated), at which point the game is over. Max’s goal is to maximize the length of the game, whereas Mini aims to minimize it. The score   of the game, denoted by s(n,P)$s(n,\mathcal{P})$, is the number of edges in G$G$ at the end of the game, assuming both players follow their optimal strategies.

We prove lower and upper bounds on the score of games in which the property the players need to avoid is being k$k$-connected, having chromatic number at least k$k$, and admitting a matching of a given size. In doing so we demonstrate that the score of certain games can be as large as the Turán number or as low as the saturation number of the respective graph property, and also that the score might strongly depend on the identity of the first player to move.