Ramsey, Paper, Scissors. Issue 4 (20th July 2020)

• Record Type: Journal Article
• Authors: Fox, Jacob; He, Xiaoyu; Wigderson, Yuval
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1157
• Page End: 1173
• Publication Date: 2020-07-20
• Subjects: combinatorial games -- Ramsey numbers; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20950
• Languages: English
• ISSNs: 1042-9832

Abstract

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 < A n log n, while Decider wins with high probability if s > B n log n . This is a factor of Θ ( log n ) ) larger than the lower bound coming from the off‐diagonal Ramsey number r (3, s ).