Sharp thresholds for half-random games. I.

DOI10.1002/RSA.20681MaRDI QIDQ2953698zbMATH OpenOpenAlexFDO

Authors Jonas Groschwitz, Tibor Szabó

Publication date 5 January 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph gamesHamiltonicitypositional gamesrandomized strategysharp threshold

Mathematics Subject Classification ID

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

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 paper we consider the scenario when Maker plays randomly and Breaker is "clever", and determine the sharp threshold bias of classical graph games, such as connectivity, Hamiltonicity, and minimum degree-$k$. We treat the other case, that is when Breaker plays randomly, in a separate paper. The traditional, deterministic version of these games, with two optimal players playing, are known to obey the so-called probabilistic intuition. That is, the threshold bias of these games is asymptotically equal to the threshold bias of their random counterpart, where players just take edges uniformly at random. We find, that despite this remarkably precise agreement of the results of the deterministic and the random games, playing randomly against an optimal opponent is not a good idea: the threshold bias becomes significantly more tilted towards the random player. An important qualitative aspect of the probabilistic intuition carries through nevertheless: the bottleneck for Maker to occupy a connected graph is still the ability to avoid isolated vertices in her graph.

Recommendations

• Sharp thresholds for half-random games. II
• Random-player maker-breaker games
• Positional games on random graphs
• Biased games on random boards
• Asymptotic random graph intuition for the biased connectivity game

Cites work

• Achlioptas process phase transitions are continuous
• Asymptotic random graph intuition for the biased connectivity game
• Avoiding a giant component
• Biased Positional Games
• Biased positional games and small hypergraphs with large covers
• Biased positional games for which random strategies are nearly optimal
• Dirac's theorem for random graphs
• scientific article; zbMATH DE number 3922707 (Why is no real title available?)
• scientific article; zbMATH DE number 3970795 (Why is no real title available?)
• Picker-chooser fixed graph games
• Planarity, Colorability, and Minor Games
• Positional games and the second moment method
• Random-player maker-breaker games
• Remarks on positional games. I
• Robust Hamiltonicity of Dirac graphs
• Sharp thresholds for half-random games. II
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛

Cited in

(5)

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

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

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