{
  "id": "1907.00210",
  "version": "v1",
  "published": "2019-06-29T14:37:56.000Z",
  "updated": "2019-06-29T14:37:56.000Z",
  "title": "Maker-Breaker Percolation Games II: Escaping to Infinity",
  "authors": [
    "A. Nicholas Day",
    "Victor Falgas-Ravry"
  ],
  "comment": "19 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\Lambda$ be an infinite connected graph, and let $v_0$ be a vertex of $\\Lambda$. We consider the following positional game. Two players, Maker and Breaker, play in alternating turns. Initially all edges of $\\Lambda$ are marked as unsafe. On each of her turns, Maker marks $p$ unsafe edges as safe, while on each of his turns Breaker takes $q$ unsafe edges and deletes them from the graph. Breaker wins if at any time in the game the component containing $v_0$ becomes finite. Otherwise if Maker is able to ensure that $v_0$ remains in an infinite component indefinitely, then we say she has a winning strategy. This game can be thought of as a variant of the celebrated Shannon switching game. Given $(p,q)$ and $(\\Lambda, v_0)$, we would like to know: which of the two players has a winning strategy? Our main result in this paper establishes that when $\\Lambda = \\mathbb{Z}^2$ and $v_0$ is any vertex, Maker has a winning strategy whenever $p\\geq 2q$, while Breaker has a winning strategy whenever $2p\\leq q$. In addition, we completely determine which of the two players has a winning strategy for every pair $(p,q)$ when $\\Lambda$ is an infinite $d$-regular tree. Finally, we give some results for general graphs and lattices and pose some open problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-29T14:37:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57",
      "91A43",
      "05D99"
    ],
    "keywords": [
      "maker-breaker percolation games",
      "winning strategy",
      "unsafe edges",
      "turns breaker",
      "breaker wins"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}