---
OA_place: repository
OA_type: green
_id: '22166'
abstract:
- lang: eng
  text: 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).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: Fox J, He X, Wigderson Y. 2020. Ramsey, Paper, Scissors. Random Structures
    &#38; Algorithms. 57(4), 1157–1173.
  mla: 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>.
  short: J. Fox, X. He, Y. Wigderson, Random Structures &#38; Algorithms 57 (2020)
    1157–1173.
date_created: 2026-06-29T10:54:10Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2026-07-14T08:31:05Z
day: '01'
doi: 10.1002/rsa.20950
extern: '1'
external_id:
  arxiv:
  - '1906.01092'
intvolume: '        57'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1906.01092
month: '12'
oa: 1
oa_version: Preprint
page: 1157-1173
publication: Random Structures & Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey, Paper, Scissors
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 57
year: '2020'
...