
arXiv: 1210.7618
ABSTRACTIn this paper we analyze biased Maker‐Breaker games and Avoider‐Enforcer games, both played on the edge set of a random board . 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 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 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 , and loses otherwise.We prove that, for every is typically such that the critical bias for all the aforementioned Maker‐Breaker games is asymptotically . We also prove that in the case , the critical bias is . These results settle a conjecture of Stojaković and Szabó. For Avoider‐Enforcer games, we prove that for , the critical bias for all the aforementioned games is . © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,651–676, 2015
Stochastic games, stochastic differential games, positional games, Games on graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, 2-person games, Positional games (pursuit and evasion, etc.), random graphs
Stochastic games, stochastic differential games, positional games, Games on graphs (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, 2-person games, Positional games (pursuit and evasion, etc.), random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 10 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
