Multistage positional games

DOI10.1016/J.DISC.2023.113478MaRDI QIDQ6156060zbMATH OpenOpenAlexFDO

Authors Juri Barkey, Dennis Clemens, Fabian Hamann, Mirjana Mikalački

Publication date 12 June 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

games on graphsmultistage gamesmaker-breaker gamesBeck's criterion

Mathematics Subject Classification ID

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

Abstract: We initiate the study of a new variant of the Maker-Breaker positional game, which we call multistage game. Given a hypergraph $mathcalH=(mathcalX,mathcalF)$ and a bias $bge1$, the $(1:b)$ multistage Maker-Breaker game on $mathcalH$ is played in several stages as follows. Each stage is played as a usual $(1:b)$ Maker-Breaker game, until all the elements of the board get claimed by one of the players, with the first stage being played on $mathcalH$. In every subsequent stage, the game is played on the board reduced to the elements that Maker claimed in the previous stage, and with the winning sets reduced to those fully contained in the new board. The game proceeds until no winning sets remain, and the goal of Maker is to prolong the duration of the game for as many stages as possible. In this paper we estimate the maximum duration of the $(1:b)$ multistage Maker-Breaker game, for biases $b$ subpolynomial in $n$, for some standard graph games played on the edge set of $K_n$: the connectivity game, the Hamilton cycle game, the non-$k$-colorability game, the pancyclicity game and the $H$-game. While the first three games exhibit a probabilistic intuition, it turns out that the last two games fail to do so.

Recommendations

• Positional games on random graphs
• Winning fast in biased maker-breaker games
• Fast strategies in biased Maker-Breaker games
• Biased games on random boards
• Biased Positional Games

Cites work

• scientific article; zbMATH DE number 3878974 (Why is no real title available?)
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• scientific article; zbMATH DE number 17673 (Why is no real title available?)
• scientific article; zbMATH DE number 932175 (Why is no real title available?)
• A Solution of the Shannon Switching Game
• Asymptotic random graph intuition for the biased connectivity game
• Avoider-Enforcer games
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Generating random graphs in biased maker-breaker games
• Hamilton cycles in highly connected and expanding graphs
• Hamiltonian circuits in random graphs
• Hypergraph containers
• Independent sets in hypergraphs
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• On a combinatorial game
• On positional games
• On the threshold for the maker-breaker H-game
• Pancyclicity of Hamiltonian and highly connected graphs
• Planarity, Colorability, and Minor Games
• Positional games
• Positional games on random graphs
• Regularity and Positional Games
• Remarks on positional games. I
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The random graph intuition for the tournament game
• Threshold functions for small subgraphs
• Van der Waerden and Ramsey type games

Cited in

(6)

• scientific article; zbMATH DE number 6429510 (Why is no real title available?)
• Evolution modeling and control of networked dynamic games with event-triggering mechanism
• Tree universality in positional games
• scientific article; zbMATH DE number 929818 (Why is no real title available?)
• scientific article; zbMATH DE number 1023206 (Why is no real title available?)
• scientific article; zbMATH DE number 3980979 (Why is no real title available?)

This page was built for publication: Multistage positional games

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