Maker-breaker percolation games. II: Escaping to infinity

DOI10.1016/J.JCTB.2020.06.006MaRDI QIDQ1984532zbMATH OpenOpenAlexFDO

Authors A. Nicholas Day, Victor Falgas-Ravry

Publication date 16 September 2021

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

maker-breaker gamespositional gamesShannon switching game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: Let $Lambda$ be an infinite connected graph, and let $v_0$ be a vertex of $Lambda$. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of $Lambda$ are marked as unsafe. On each of her turns, Maker marks $p$ unsafe edges as safe, while on each of his turns Breaker takes $q$ unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing $v_0$ becomes finite. Otherwise if Maker is able to ensure that $v_0$ remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given $(p,q)$ and $(Lambda,v_0)$, we would like to know: which of the two players has a winning strategy? Our main result in this paper establishes that when $Lambda=mathbb{Z}^2$ and $v_0$ is any vertex, Maker has a winning strategy whenever $pgeq2q$, while Breaker has a winning strategy whenever $2pleqq$. In addition, we completely determine which of the two players has a winning strategy for every pair $(p,q)$ when $Lambda$ is an infinite $d$-regular tree. Finally, we give some results for general graphs and lattices and pose some open problems.

Recommendations

• Maker–Breaker percolation games I: crossing grids
• Maker-breaker games on random geometric graphs
• Maker-Breaker games on randomly perturbed graphs
• Percolation and the complexity of games
• Hitting time results for maker-breaker games (extended abstract)
• On the threshold for the maker-breaker H-game
• Percolation games, probabilistic cellular automata, and the hard-core model
• The Maker-Breaker Rado game on a random set of integers
• On the WalkerMaker-WalkerBreaker games
• MAKER–BREAKER GAMES ON AND

Cites work

• A Solution of the Shannon Switching Game
• A solution to the angel problem
• A solution to the Box 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
• Conway's Angel in three dimensions
• Deterministic Graph Games and a Probabilistic Intuition
• Energy games in multiweighted automata
• scientific article; zbMATH DE number 988819 (Why is no real title available?)
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 524119 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Maker–Breaker percolation games I: crossing grids
• Percolation
• Positional games on random graphs
• Reachability games on extended vector addition systems with states
• Remarks on positional games. I
• Strategies for the Shannon Switching Game
• The angel and the devil in three dimensions
• The Angel Game in the Plane
• The Angel of Power 2 Wins
• 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

(10)

• Percolation games, probabilistic cellular automata, and the hard-core model
• Shutout games on graphs
• Maker–Breaker percolation games I: crossing grids
• Trapping games on random boards
• MAKER–BREAKER GAMES ON AND
• Maker-breaker domination game on trees when Staller wins
• Adversarial graph burning densities
• The rational number game
• 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. II: Escaping to infinity

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