Maker–Breaker percolation games I: crossing grids

DOI10.1017/S0963548320000097MaRDI QIDQ4993258zbMATH OpenOpenAlexFDO

Authors A. Nicholas Day, Victor Falgas-Ravry

Publication date 15 June 2021

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1810.05190

zbMATH Keywords

percolation theorytwo-player positional game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Extremal combinatorics (05D99) 2-person games (91A05) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: Motivated by problems in percolation theory, we study the following 2-player positional game. Let $Lambd{a}_{mimesn}$ 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 $Lambd{a}_{mimesn}$, 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 $Lambd{a}_{mimesn}$. Given $m,ninmathbbN$, for which pairs $(p,q)$ does Maker have a winning strategy for the $(p,q)$-crossing game on $Lambd{a}_{mimesn}$? 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 $pgeqslant2q$, then Maker wins the game on arbitrarily long versions of the narrowest board possible, i.e. Maker has a winning strategy for the $(2q,q)$-crossing game on $Lambd{a}_{mimes(q+1)}$ for any $minmathbbN$; $$ if $pleqslant2q-1$, then for every width $n$ of the board, Breaker has a winning strategy for the $(p,q)$-crossing game on $Lambd{a}_{mimesn}$ 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.

Recommendations

• Maker-breaker percolation games. II: Escaping to infinity
• Maker-breaker games on random geometric graphs
• Maker-Breaker games on randomly perturbed graphs
• Percolation and the complexity of games
• The Minesweeper Game: Percolation and Complexity
• On the WalkerMaker-WalkerBreaker games
• Percolation games, probabilistic cellular automata, and the hard-core model
• The Maker-Breaker Rado game on a random set of integers
• Maker-Breaker total domination game on cubic graphs

Cites work

• A Solution of the Shannon Switching Game
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Biased positional games and the phase transition
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Deterministic Graph Games and a Probabilistic Intuition
• Hex and combinatorics
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 524119 (Why is no real title available?)
• Maker-breaker percolation games. II: Escaping to infinity
• On a combinatorial game
• On the optimality of the uniform random strategy
• Percolation
• Positional games on random graphs
• Remarks on positional games. I
• Self-avoiding walks crossing a square
• Strategies for the Shannon Switching Game
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The critical probability of bond percolation on the square lattice equals 1/2

Cited in

(11)

• Maker-breaker percolation games. II: Escaping to infinity
• Search for an immobile hider on a stochastic network
• Percolation games, probabilistic cellular automata, and the hard-core model
• Chain-making games in grid-like posets
• PathWalker-Breaker games on complete bipartite graphs
• An n-in-a-row type game
• Calculating the Crossing Probability on the Square Tessellation of a Connection Game with Random Move Order: The Algorithm and Its Complexity
• Trapping games on random boards
• Maker-breaker domination game on trees when Staller wins
• The Maker-Breaker percolation game on the square lattice
• The Maker-Breaker percolation game on a random board

This page was built for publication: Maker–Breaker percolation games I: crossing grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993258)