Georgia Institute of Technology College of Sciences

We discuss the Maker-Breaker component game, played on the edge set of a sparse random graph. Given a graph G and positive integers s and b, the s-component (1:b) game is defined as follows. In every round Maker claims one free edge of G and Breaker claims b free edges. Maker wins this game if her graph contains a connected component of size at least s; otherwise, Breaker wins the game. For the Erdos-Renyi graph G(n,p), we show that the maximum component size achievable by Maker undergoes a phase transition around p = lambda_{b+2}/n, where lambda_k is the threshold for the appearance of a non-empty k-core in G(n,p) To this end, we analyze the stabilization time of the k-core process in G(n,p). Joint work with Michael Krivelevich, Tobias Mueller, Alon Naor, and Nicholas Wormald.