Random-player maker-breaker games

MaRDI QIDQ888617zbMATH OpenFDO

Authors Michael Krivelevich, Gal Kronenberg

Publication date 2 November 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00445, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p9

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random graphspositional games

Mathematics Subject Classification ID

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

Abstract: In a $(1:b)$ Maker-Breaker game, a primary question is to find the maximal value of $b$ that allows Maker to win the game (that is, the critical bias $b^{\ast }$). ErdH{o}s conjectured that the critical bias for many Maker-Breaker games played on the edge set of $K_n$ is the same as if both players claim edges randomly. Indeed, in many Maker-Breaker games, "ErdH{o}s Paradigm" turned out to be true. Therefore, the next natural question to ask is the (typical) value of the critical bias for Maker-Breaker games where only one player claims edges randomly. A random-player Maker-Breaker game is a two-player game, played the same as an ordinary (biased) Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims $b$ elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions; the $(1:b)$ random-Breaker game and the $(m:1)$ random-Maker game. We analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect-matching game and the $k$-vertex-connectivity game (played on the edge sets of $K_n$). For each of these games we find or estimate the asymptotic values of $b$ that allow each player to typically win the game. In fact, we provide the "smart" player with an explicit winning strategy for the corresponding value of $b$.

Recommendations

• Biased games on random boards
• Sharp thresholds for half-random games. I.
• Sharp thresholds for half-random games. II
• Positional games on random graphs
• Maker-Breaker games on randomly perturbed graphs

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 6303013 (Why is no real title available?)
• A Solution of the Shannon Switching Game
• Asymptotic random graph intuition for the biased connectivity game
• Biased Positional Games
• Biased positional games for which random strategies are nearly optimal
• Combinatorial Games
• Efficient winning strategies in random-turn maker-breaker games
• Fast strategies in maker-breaker games played on random boards
• Fast winning strategies in maker-breaker games
• Hitting time results for maker-breaker games
• Positional games
• Random graphs.
• Random-Turn Hex and Other Selection Games
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Weak and strong \(k\)-connectivity games

Cited in

(11)

• Connector-breaker games on random boards
• Two-player pebbling on diameter 2 graphs
• Maker-Breaker games on randomly perturbed graphs
• Random strategies are nearly optimal for generalized van der Waerden games
• Efficient winning strategies in random-turn maker-breaker games
• Sharp thresholds for half-random games. I.
• Hitting time results for maker-breaker games
• Generating random graphs in biased maker-breaker games
• Sharp thresholds for half-random games. II
• Positional games on random graphs
• The Maker-Breaker Rado game on a random set of integers

This page was built for publication: Random-player maker-breaker games

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