Avoider-Forcer Games on Hypergraphs with Small Rank

  • Małgorzata Bednarska-Bzdęga
Keywords: combinatorial games, Avoider-Forcer game, Avoider-Enforcer games

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. 

Published
2014-01-12
Article Number
P1.2