| Abstract: | Let 𝔏(n, q) be the game in which two players, Maker and Breaker, alternately claim 1 and q edges of the complete graph Kn, respectively. Maker's goal is to maximize the number of vertices in the largest component of his graph; Breaker tries to make it as small as possible. Let L(n,q) denote the size of the largest component in Maker's graph when both players follow their optimal strategies. We study the behavior of L(n, q) for large n and q=q(n). In particular, we show that the value of L(n, q) abruptly changes for q∼n and discuss the differences between this phenomenon and a similar one, which occurs in the evolution of random graphs. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 141–152, 2001 |
