Ramsey, paper, scissors

DOI10.1002/RSA.20950MaRDI QIDQ3386531zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Xiaoyu He, Yuval Wigderson

Publication date 5 January 2021

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

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

zbMATH Keywords

combinatorial gamesRamsey numbers

Mathematics Subject Classification ID

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

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)$.

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

Cites work

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

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)