Premium
Biased positional games and the phase transition
Author(s) -
Bednarska Małgorzata,
Łuczak Tomasz
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200103)18:2<141::aid-rsa1002>3.0.co;2-w
Subject(s) - transition (genetics) , phase (matter) , psychology , physics , chemistry , quantum mechanics , biochemistry , gene
Let ( n , q ) be the game in which two players, Maker and Breaker, alternately claim 1 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 ∼ 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