Biased games on random boards

In this paper we analyze biased Maker-Breaker games and Avoider-Enforcer games, both played on the edge set of a random board G ∼ G ( n , p ) . In Maker-Breaker games there are two players, denoted by Maker and Breaker. In each round, Maker claims one previously unclaimed edge of G and Breaker responds by claiming b previously unclaimed edges. We consider the Hamiltonicity game, the perfect matching game and the k-vertex-connectivity game, where Maker's goal is to build a graph which possesses the relevant property. Avoider-Enforcer games are the reverse analogue of Maker-Breaker games with a slight modification, where the two players claim at least 1 and at least b previously unclaimed edges per move, respectively, and Avoider aims to avoid building a graph which possesses the relevant property. Maker-Breaker games are known to be “bias-monotone”, that is, if Maker wins the (1,b) game, he also wins the ( 1 , b − 1 ) game. Therefore, it makes sense to define the critical bias of a game, b *, to be the “breaking point” of the game. That is, Maker wins the (1,b) game whenever b < b * and loses otherwise. An analogous definition of the critical bias exists for Avoider-Enforcer games: here, the critical bias of a game b * is such that Avoider wins the (1,b) game for every b ≥ b * , and loses otherwise. We prove that, for every p = ω ( ln ⁡ n n ) , G ∼ G ( n , p ) is typically such that the critical bias for all the aforementioned Maker-Breaker games is asymptotically b * = n p ln ⁡ n . We also prove that in the case p = Θ ( ln ⁡ n n ) , the critical bias is b * = Θ ( n p ln ⁡ n ) . These results settle a conjecture of Stojakovic and Szabo. For Avoider-Enforcer games, we prove that for p = Ω ( ln ⁡ n n ) , the critical bias for all the aforementioned games is b * = Θ ( n p ln ⁡ n ) . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,651–676, 2015