Ramsey, Paper, Scissors. Issue 4 (20th July 2020)
- Record Type:
- Journal Article
- Title:
- Ramsey, Paper, Scissors. Issue 4 (20th July 2020)
- Main Title:
- Ramsey, Paper, Scissors
- Authors:
- Fox, Jacob
He, Xiaoyu
Wigderson, Yuval - 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 ).
- Is Part Of:
- Random structures & algorithms. Volume 57:Issue 4(2020)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 57:Issue 4(2020)
- Issue Display:
- Volume 57, Issue 4 (2020)
- Year:
- 2020
- Volume:
- 57
- Issue:
- 4
- Issue Sort Value:
- 2020-0057-0004-0000
- Page Start:
- 1157
- Page End:
- 1173
- Publication Date:
- 2020-07-20
- Subjects:
- combinatorial games -- Ramsey numbers
Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.20950 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 14603.xml