Avoider-Forcer Games on Hypergraphs with Small Rank
Keywords: combinatorial games, Avoider-Forcer game, Avoider-Enforcer games
AbstractWe study biased $(a:f)$ Avoider-Forcer games played on hypergraphs, in the strict and monotone versions. We give a sufficient condition for Avoider's win, useful in the case of games on hypergraphs whose rank is smaller than $f$. We apply this result to estimate the threshold bias in Avoider-Forcer $(1:f)$ games in which Avoider is trying not to build a copy of a fixed graph $G$ in $K_n$. We also study the $d$-degree $(1:f)$ game in which Avoider's aim is to avoid a spanning subgraph of the minimal degree at least $d$ in $K_n$. We show that the strict 1-degree game has the threshold which is the same as the threshold of the Avoider-Forcer connectivity game.