Sannolikhet, statistik och kombinatorik: Maker-Breaker percolation games

  • Datum:
  • Plats: Ångströmlaboratoriet 64119
  • Föreläsare: Nicholas Day, Umeå universitet
  • Arrangör: Matematiska institutionen
  • Kontaktperson: Xing Shi Cai
  • Seminarium

Abstract: The (p,q)-percolation game is a Maker-Breaker game played by two players, Maker and Breaker, on the edge set of 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. Informally speaking, Maker's aim is to build an arbitrarily long path from the origin of the lattice, while Breaker's aim is to prevent this from happening. More formally speaking, we say that Maker wins the game if she can guarantee on every turn 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)-crossing game is similar to the above Maker-Breaker 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.

In this talk we will give a number of results for such Maker-Breaker games, and discuss their relations to each other, as well as the combinatorial games of Hex, Bridg-it and the Shannon switching game. We will also discuss the biased Erdős–Selfridge criterion, and how it relates our games to the classical model of bond percolation on the integer lattice. Finally, we will discuss certain variations of these games, such as what happens when you play the percolation game on regular trees or other infinite lattices.

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