Ramsey, paper, scissors

DOI10.1002/RSA.20950zbMATH Open1454.91048arXiv1906.01092OpenAlexW3044615997MaRDI QIDQ3386531FDOQ3386531

Authors: Jacob Fox, Xiaoyu He, Yuval Wigderson 

Publication date: 5 January 2021

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

Abstract: We introduce a graph Ramsey game called Ramsey, Paper, Scissors. This game has two players, Proposer and Decider. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a potential edge and Decider simultaneously decides (without knowing Proposer's choice) whether to add it to the graph. Proposer cannot propose an edge which would create a triangle in the graph. The game ends when Proposer has no legal moves remaining, and Proposer wins if the final graph has independence number at least $s$. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. Namely, there exist constants $0<A<B$ such that (under optimal play) Proposer wins with high probability if $s<Asqrtnlogn$, while Decider wins with high probability if $s>Bsqrtnlogn$. This is a factor of $Theta(sqrtlogn)$ larger than the lower bound coming from the off-diagonal Ramsey number $r(3,s)$.

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

Recommendations

• Ramsey Games Against a One-Armed Bandit
• A Winning Strategy for the Ramsey Graph Game
• On the threshold for the maker-breaker \(H\)-game
• Balanced online Ramsey games in random graphs
• Offline thresholds for Ramsey-type games on random graphs

zbMATH Keywords

combinatorial gamesRamsey numbers

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• The triangle-free process
• Positional games
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On a combinatorial game
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• Title not available (Why is that?)
• Ramsey's theorem - a new lower bound
• The triangle-free process and the Ramsey number \(R(3,k)\)
• The early evolution of the \(H\)-free process
• Ramsey Games Against a One-Armed Bandit
• Graph Theory and Probability. II
• Bounding Ramsey numbers through large deviation inequalities
• Online Ramsey numbers and the subgraph query problem
• Eighty years of Ramsey \(R(3, k)\)\dots and counting!

Cited In (2)

• Bounds on Ramsey games via alterations
• On 1-subdivisions of transitive tournaments

This page was built for publication: Ramsey, paper, scissors

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