Nicholas Day

Umeå University
, BH 227

Abstract

Maker-Breaker percolation games

Maker-Breaker games are an important class of combinatorial positional games played between two players, Maker and Breaker.  In this talk I will give a brief introduction into Maker-Breaker games, and then focus on two instances of such games, namely the Maker-Breaker-percolation game and the Maker-Breaker-crossing game.  The (p,q)-Maker-Breaker-percolation game is played by two players, Maker and Breaker, who take turns claiming edges from the two-dimensional integer lattice.  On each of her turns Maker claims p different unclaimed edges, while on each of his turns Breaker claims q different unclaimed edges. Maker's aim is to build arbitrarily long paths from the origin of the lattice, while Breaker's aim is to prevent this from happening.  We say that Maker wins the game if she can guarantee that, among the set of unclaimed edges and edges that Maker has claimed, there is always a path from the origin escaping to infinity.  The (p,q)-Maker-Breaker-crossing game is similar to the above percolation game, except that it is played on a finite two dimensional grid and Maker's aim is to create a path of edges that crosses from the left side of the grid to the right side, while Breaker's aim is to prevent this from happening.

I will give a number of results for such Maker-Breaker games, and discuss their relations to each other and the well known combinatorial games of Hex, Bridg-it and the Shannon switching game.

This talk is based on joint work with Victor Falgas-Ravry.