2006/01/26 by Milos Stojakovic, Tibor Szabo · 1 citation
Mathematics · #math.CO #math.PR #msc:05C80 #msc:91A24
published as Random Structures & Algorithms 26 (2005), 204-223
arxiv created 2006/01/26 · arxiv updated 2009/12/01
We introduce and study Maker/Breaker-type positional games on random graphs. Our main concern is to determine the threshold probability pF for the existence of Maker's strategy to claim a member of F in the unbiased game played on the edges of random graph G(n,p), for various target families F of winning sets. More generally, for each probability above this threshold we study the smallest bias b such that Maker wins the (1 b) biased game. We investigate these functions for a number of basic games, like the connectivity game, the perfect matching game, the clique game and the Hamiltonian cycle game.