article published yes Jacob Fox author Xiaoyu He author Yuval Wigderson author 2d0023a0-1567-11f0-833d-d5c1e476d4b5 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 turnProposer proposes a potential edge and Decider simultane-ously decides (without knowing Proposer’s choice) whether toadd it to the graph. Proposer cannot propose an edge whichwould create a triangle in the graph. The game ends whenProposer has no legal moves remaining, and Proposer wins ifthe final graph has independence number at least s. We provea threshold phenomenon exists for this game by exhibitingrandomized strategies for both players that are optimal up toconstants. Namely, there exist constants 0 < A < B such that(under optimal play) Proposer wins with high probability ifs < A√n log n, while Decider wins with high probability ifs > B√n log n. This is a factor of Θ(√log n)) larger than thelower bound coming from the off-diagonal Ramsey numberr(3, s). Wiley2020 eng 1042-9832 1098-2418 1906.0109210.1002/rsa.20950 5741157-1173 yes J. Fox, X. He, and Y. Wigderson, “Ramsey, Paper, Scissors,” <i>Random Structures &#38; Algorithms</i>, vol. 57, no. 4. Wiley, pp. 1157–1173, 2020. Fox, Jacob, et al. “Ramsey, Paper, Scissors.” <i>Random Structures &#38; Algorithms</i>, vol. 57, no. 4, Wiley, 2020, pp. 1157–73, doi:<a href="https://doi.org/10.1002/rsa.20950">10.1002/rsa.20950</a>. Fox J, He X, Wigderson Y. 2020. Ramsey, Paper, Scissors. Random Structures &#38; Algorithms. 57(4), 1157–1173. J. Fox, X. He, Y. Wigderson, Random Structures &#38; Algorithms 57 (2020) 1157–1173. Fox J, He X, Wigderson Y. Ramsey, Paper, Scissors. <i>Random Structures &#38; Algorithms</i>. 2020;57(4):1157-1173. doi:<a href="https://doi.org/10.1002/rsa.20950">10.1002/rsa.20950</a> Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey, Paper, Scissors.” <i>Random Structures &#38; Algorithms</i>. Wiley, 2020. <a href="https://doi.org/10.1002/rsa.20950">https://doi.org/10.1002/rsa.20950</a>. Fox, J., He, X., &#38; Wigderson, Y. (2020). Ramsey, Paper, Scissors. <i>Random Structures &#38; Algorithms</i>. Wiley. <a href="https://doi.org/10.1002/rsa.20950">https://doi.org/10.1002/rsa.20950</a> 221662026-06-29T10:54:10Z2026-07-14T08:31:05Z