Tibor Szabó

We study biased Maker/Breaker games on the edges of the complete graph, as introduced by Chvátal and Erdős. We show that Maker, occupying one edge in each of his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 − o(1)) · $ {n \over \ln n} $ edges in each turn. This improves a result of Beck, and is asymptotically best possible as witnessed by the Breaker‐strategy of Chvátal and Erdős. We also give a strategy for Maker to occupy a graph with minimum degree c (where c = c(n) is a slowly growing function of n) while playing against a Breaker who takes b ≤ (1 − o(1)) · $ {n \over \ln n} $ edges in each turn. This result improves earlier bounds by Krivelevich and Szabó. Both of our results support the surprising random graph intuition: the threshold bias is asymptotically the same for the game played by two “clever” players and the game played by two “random” players. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009

We study the Hamilton cycle Maker–Breaker game, played on the edges of the random graph G(n,p). We prove a conjecture from (Stojaković and Szabó, Random Struct and Algorithms 26 (2005), 204–223.), asserting that the property that Maker is able to win this game, has a sharp threshold at $\log n \over n$ . Our theorem can be considered a game‐theoretic strengthening of classical results from the theory of random graphs: not only does G(n,p) almost surely admit a Hamilton cycle for $p = ( 1 + \varepsilon) {{\log n} \over {n}}$ , but Maker is able to build one while playing against an adversary. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009