Probabilistic One-Player Ramsey Games via Deterministic Two-Player Games

DOI10.1137/110826308zbMATH Open1256.05150arXiv0911.3810OpenAlexW2083596217MaRDI QIDQ4899043FDOQ4899043

Authors: Michael Belfrage, Torsten Mütze, Reto Spöhel 

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Consider the following probabilistic one-player game: The board is a graph with $n$ vertices, which initially contains no edges. In each step, a new edge is drawn uniformly at random from all non-edges and is presented to the player, henceforth called Painter. Painter must assign one of $r$ available colors to each edge immediately, where $rgeq2$ is a fixed integer. The game is over as soon as a monochromatic copy of some fixed graph $F$ has been created, and Painter's goal is to 'survive' for as many steps as possible before this happens. We present a new technique for deriving upper bounds on the threshold of this game, i.e., on the typical number of steps Painter will survive with an optimal strategy. More specifically, we consider a deterministic two-player variant of the game where the edges are not chosen randomly, but by a second player Builder. However, Builder has to adhere to the restriction that, for some real number $d$, the ratio of edges to vertices in all subgraphs of the evolving board never exceeds $d$. We show that the existence of a winning strategy for Builder in this deterministic game implies an upper bound of $n^{2-1/d}$ for the threshold of the original probabilistic game. Moreover, we show that the best bound that can be derived in this way is indeed the threshold of the game if $F$ is a forest. We illustrate our technique with several examples, and derive new explicit bounds for the case when $F$ is a path.

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

Recommendations

• Zero-sum dynamic games and a stochastic variation of Ramsey's theorem
• Deterministic Graph Games and a Probabilistic Intuition
• scientific article; zbMATH DE number 1047712
• On Ramsey-type positional games
• Derandomization in game-theoretic probability
• Bounds on Ramsey games via alterations
• Publication:4723588
• Upper bounds for online Ramsey games in random graphs
• Online Ramsey games in random graphs
• Offline thresholds for Ramsey-type games on random graphs

zbMATH Keywords

random graphRamsey propertyonline process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Generalized Ramsey theory (05C55) Games on graphs (graph-theoretic aspects) (05C57) Ramsey theory (05D10) Probabilistic games; gambling (91A60)

Cited In (3)

• Proper colouring painter-builder game
• Coloring random graphs online without creating monochromatic subgraphs
• Online Ramsey games for more than two colors

This page was built for publication: Probabilistic One-Player Ramsey Games via Deterministic Two-Player Games

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