Options
Fast strategies in Maker-Breaker games played on random boards
Publikationstyp
Journal Article
Date Issued
2012-09-10
Sprache
English
TORE-URI
Volume
21
Issue
6
Start Page
897
End Page
915
Citation
Combinatorics Probability and Computing 6 (21): 897-915 (2012-11-01)
Publisher DOI
Scopus ID
Publisher
Cambridge Univ. Press
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 ∼ 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.
DDC Class
510: Mathematik