Sharp thresholds for half-random games. II

DOI10.1007/S00373-016-1753-4MaRDI QIDQ2014222zbMATHOpenAlexFDO

Authors Jonas Groschwitz, Tibor Szabó

Publication date 10 August 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

connectivityrandomized strategypositional gamessharp thresholdHamiltonicityfast win

Mathematics Subject Classification ID

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

Abstract: We study biased Maker-Breaker positional games between two players, one of whom is playing randomly against an opponent with an optimal strategy. In this work we focus on the case of Breaker playing randomly and Maker being "clever". The reverse scenario is treated in a separate paper. We determine the sharp threshold bias of classical games played on the edge set of the complete graph $K_n$, such as connectivity, perfect matching, Hamiltonicity, and minimum degree-$1$. In all of these games, the threshold is equal to the trivial upper bound implied by the number of edges needed for Maker to occupy a winning set. Moreover, we show that the clever Maker can not only win against an asymptotically optimal bias, but can do so very fast, wasting only logarithmically many moves (while the winning set sizes are linear in $n$).

Recommendations

• Sharp thresholds for half-random games. I.
• Positional games on random graphs
• Random-player maker-breaker games
• Biased games on random boards
• Biased positional games for which random strategies are nearly optimal

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Fast winning strategies in avoider-enforcer games
• Fast winning strategies in maker-breaker games
• On two problems regarding the Hamiltonian cycle game
• On winning fast in Avoider-Enforcer games
• Random-player maker-breaker games
• Sharp thresholds for half-random games. I.
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Weak and strong \(k\)-connectivity games
• Winning strong games through fast strategies for weak games

Cited in

(6)

• Random-player maker-breaker games
• Random strategies are nearly optimal for generalized van der Waerden games
• Asymptotic random graph intuition for the biased connectivity game
• Efficient winning strategies in random-turn maker-breaker games
• Sharp thresholds for half-random games. I.
• Positional games on random graphs

This page was built for publication: Sharp thresholds for half-random games. II

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