Fast Strategies In Maker–Breaker Games Played on Random Boards

Abstract

In this paper we analyse classical Maker–Breaker games played on the edge set of a sparse random board G ~ n,p . 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 ~ n,p 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.