2012/03/15 by Dennis Clemens, Clemens, Dennis, Asaf Ferber +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #math.CO
paper · pdf · doi:10.48550/arxiv.1203.3444
arxiv created 2012/03/15 · openalex publication_date 2012/03/15 · arxiv updated 2012/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we analyze classical Maker-Breaker games played on the edge set of a sparse random board G∼ \gnp. We consider the Hamiltonicity game, the perfect matching game and the k-connectivity game. We prove that for p(n)≥ polylog(n)/n, the board G∼ \gnp is typically such that Maker can win these games asymptotically as fast as possible, i.e. within n+o(n), n/2+o(n) and kn/2+o(n) moves respectively.