Maker-Breaker Games on Random Geometric Graphs
Published in Random Structures and Algorithms, 2014
A. Beveridge, A. Dudek, A. Frieze, T. Mu ̀ˆller, M. Stojaković, Maker-Breaker Games on Random Geometric Graphs, Random Structures and Algorithms, Vol 45, No. 4 (2014), pp. 553-607.
Preprint link: https://arxiv.org/abs/1309.5759
In a Maker-Breaker game on a graph G, Breaker and Maker alternately claim edges of G. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played on random geometric graphs: the connectivity game, the Hamilton cycle game, the perfect matching game, and the subgraph game. For each of our four games we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n \rightarrow \infty$, the graph becomes Maker-win the very moment it satisfies a simple necessary condition.