Avoider–Enforcer games

Let p and q be positive integers and let H be any hypergraph. In a ( p , q , H ) Avoider–Enforcer game two players, called Avoider and Enforcer, take turns selecting previously unclaimed vertices of H . Avoider selects p vertices per move and Enforcer selects q vertices per move. Avoider loses if he claims all the vertices of some hyperedge of H ; otherwise Enforcer loses. We prove a sufficient condition for Avoider to win the ( p , q , H ) game. We then use this condition to show that Enforcer can win the ( 1 , q ) perfect matching game on K 2 n for every q ⩽ c n / log n for an appropriate constant c, and the ( 1 , q ) Hamilton cycle game on K n for every q ⩽ c n log log log log n / log n log log log n for an appropriate constant c. We also determine exactly those values of q for which Enforcer can win the ( 1 , q ) connectivity game on K n . This result is quite surprising as it substantially differs from its Maker–Breaker analog. Our method extends easily to improve a result of Lu [X. Lu, A note on biased and non-biased games, Discrete Appl. Math. 60 (1995) 285–291], regarding forcing an opponent to pack many pairwise edge disjoint spanning trees in his graph.