Ramsey, Paper, Scissors

Jacob Fox, Xiaoyu He, Yuval Wigderson

Published 2019-06-03Version 1

In this paper, we introduce a two-player graph Ramsey game, which we call Ramsey, Paper, Scissors. In this game, two players Proposer and Decider play simultaneously. Starting from an empty graph on $n$ vertices, on each turn Proposer proposes a new pair of vertices and Decider decides (without knowing which pair is chosen) whether or not to add it as an edge in the graph. Proposer is forbidden from proposing a pair that would form a triangle in the graph, and Proposer wins if the final graph has independence number at least $s$. Otherwise Decider wins. We prove a threshold phenomenon exists for this game by exhibiting randomized strategies for both players that are optimal up to constants. That is, we show the existence of constants $0<A<B$ such that Proposer has a strategy that wins with high probability if $s<A \sqrt n \log n$, while Decider has a strategy that wins with high probability if $s> B \sqrt n \log n$. It is known that the off-diagonal Ramsey number $r(3,s)$ is $\Theta(s^2/\log s)$, so Proposer always wins when $s \leq c\sqrt{n\log n}$ for an appropriate $c > 0$. Thus, the threshold for Ramsey, Paper, Scissors is a factor of $\Theta(\sqrt{\log n})$ larger than this lower bound.