Biased games on random boards1. Issue 4 (24th February 2014) - Ferber, Asaf; Glebov, Roman; Krivelevich, Michael; Naor, Alon
ABSTRACT In this paper we analyze biased Maker‐Breaker games and Avoider‐Enforcer games, both played on the edge set of a random board <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kdmp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G∼G(n, p)</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kdpq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(1, b−1)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kf4x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b<b*</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kf9h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b≥b*</alternatives>, and loses otherwise. We prove that, for every <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kdzv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=ω(ln⁡nn), G∼G(n, p)</alternatives> is typically such that the critical bias for all the aforementioned Maker‐Breaker games is asymptotically <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kf3d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b*=npln⁡n</alternatives>. We also prove that in the case <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kfhm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=Θ(ln⁡nn)</alternatives>, the critical bias is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kfnp" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b*=Θ(npln⁡n)</alternatives>. These results settle a conjecture of Stojaković and Szabó. For Avoider‐Enforcer games, we prove that for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kfb1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=Ω(ln⁡nn)</alternatives>, the critical bias for all the aforementioned games is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgjmx7kqp2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />b*=Θ(npln⁡n)</alternatives>. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46, 651–676, 2015