The Avoider-Enforcer Game in Hypergraphs of Rank 3

Abstract

In the Avoider-Enforcer convention of positional games, two players-Avoider and Enforcer-take turns selecting vertices from a hypergraph $H$. Enforcer wins if, by the time all vertices of $H$ have been selected, Avoider has completely filled an edge of $H$ with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms.