{
  "id": "1906.01092",
  "version": "v1",
  "published": "2019-06-03T21:45:52.000Z",
  "updated": "2019-06-03T21:45:52.000Z",
  "title": "Ramsey, Paper, Scissors",
  "authors": [
    "Jacob Fox",
    "Xiaoyu He",
    "Yuval Wigderson"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-03T21:45:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "high probability",
      "two-player graph ramsey game",
      "off-diagonal ramsey number",
      "empty graph",
      "turn proposer"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}