Fast strategies in Maker-Breaker games played on random boards

Dennis Clemens, Asaf Ferber, Michael Krivelevich, Anita Liebenau

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

In this paper we analyse classical Maker-Breaker games played on the edge set of a sparse random board G similar to 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 similar to 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
Original languageEnglish
Pages (from-to)897 - 915
Number of pages19
JournalCombinatorics, Probability and Computing
Volume21
Issue number6
DOIs
Publication statusPublished - 2012
Externally publishedYes

Cite this