Maker–Breaker percolation games I: crossing grids. (15th March 2021)

• Record Type: Journal Article
• Authors: Day, A. Nicholas; Falgas-Ravry, Victor
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 2(2021)
• Page Start: 200
• Page End: 227
• Publication Date: 2021-03-15
• Subjects: 05C57, -- 05D99, -- 91A43; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000097
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: Motivated by problems in percolation theory, we study the following two-player positional game. Let Λ m × n 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 Λ m × n, 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 Λ m × n . Given m, n ∈ ℕ, for which pairs ( p, q ) does Maker have a winning strategy for the ( p, q )-crossing game on Λ m × n ? 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 p ≥ 2 q, then Maker wins the game on arbitrarily long versions of the narrowest board possible, that is, Maker has a winning strategy for the (2 q, q )-crossing game on Λ m ×( q +1 ) for any m ∈ ℕ. If p ≤ 2 q − 1, then for every width n of the board, Breaker has a winning strategy for the ( p, q )-crossing game on Λ m × n 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.