Miloš Stojaković : Breaker games on random boards

Abstract: In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph H). Breaker wins otherwise.

We take a closer look at various Maker-Breaker games played on the edge sets of random graphs.