Paper Info
Title
Maker-Breaker Percolation Games I: Crossing Grids
Abstract
Motivated by problems in percolation theory, we study the following two-player positional game. Let ?(mxn) be a rectangular grid-graph with m vertices in each row and n vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims p (as yet unclaimed) edges of the board ?(mxn), while on each of his turns Breaker claims q (as yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the (p, q)-crossing game on ?(mxn).Given m, n is an element of N, for which pairs (p, q) does Maker have a winning strategy for the (p, q)-crossing game on ?(mxn)? The (1, 1)-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper we study the general (p, q)-case. Our main result is to establish the following transition.If >= 2, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2, )-crossing game on ?x(+1 for any is an element of N.pqqqmq)mIf p <= 2q - 1, then for every width n of the board, Breaker has a winning strategy for the (p, q)-crossing game on ?mxn for all sufficiently large board-lengths m.Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.
Year
DOI
Venue
2021
10.1017/S0963548320000097
COMBINATORICS PROBABILITY & COMPUTING
Keywords
DocType
Volume
05C57, 05D99, 91A43
Journal
30
Issue
ISSN
Citations 
2
0963-5483
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
A. Nicholas Day100.34
Victor Falgas-Ravry2287.46