Avoider-Forcer Games on Hypergraphs with Small Rank

Małgorzata Bednarska-Bzdęga

Abstract


We 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. 


Keywords


combinatorial games; Avoider-Forcer game, Avoider-Enforcer games

Full Text: PDF