Biased positional games and the phase transition
Let L(n, q) be the game in which two players, Maker and Breaker, alternately claim l and q edges of the complete graph K-n, 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 similar to n and discuss the differences between this phenomenon and a similar one, which occurs in the evolution of random graphs. (C) 2001 John Wiley & Sons, Inc.
phase transition random graphs combinatorial games