{
  "id": "1810.05190",
  "version": "v1",
  "published": "2018-10-11T18:14:57.000Z",
  "updated": "2018-10-11T18:14:57.000Z",
  "title": "Maker-Breaker Percolation Games I: Crossing Grids",
  "authors": [
    "A. Nicholas Day",
    "Victor Falgas-Ravry"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Motivated by problems in percolation theory, we study the following 2-player positional game. Let $\\Lambda_{m \\times n}$ be a rectangular grid-graph with $m$ vertices in each row and $n$ vertices in each column. Two players, Maker and Breaker, play in alternating turns. On each of her turns, Maker claims $p$ (as-yet unclaimed) edges of the board $\\Lambda_{m \\times n}$, while on each of his turns Breaker claims $q$ (as-yet unclaimed) edges of the board and destroys them. Maker wins the game if she manages to claim all the edges of a crossing path joining the left-hand side of the board to its right-hand side, otherwise Breaker wins. We call this game the $(p,q)$-crossing game on $\\Lambda_{m \\times n}$. Given $m,n\\in \\mathbb{N}$, for which pairs $(p,q)$ does Maker have a winning strategy for the $(p,q)$-crossing game on $\\Lambda_{m \\times n}$? The $(1,1)$-case corresponds exactly to the popular game of Bridg-it, which is well understood due to it being a special case of the older Shannon switching game. In this paper, we study the general $(p,q)$-case. Our main result is to establish the following transition: $\\bullet$ If $p\\geqslant 2q$, then Maker wins the game on arbitrarily long versions of the narrowest board possible, i.e. Maker has a winning strategy for the $(2q, q)$-crossing game on $\\Lambda_{m \\times(q+1)}$ for any $m\\in \\mathbb{N}$; $\\bullet$ if $p\\leqslant 2q-1$, then for every width $n$ of the board, Breaker has a winning strategy for the $(p,q)$-crossing game on $\\Lambda_{m \\times n}$ for all sufficiently large board-lengths $m$. Our winning strategies in both cases adapt more generally to other grids and crossing games. In addition we pose many new questions and problems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-10-11T18:14:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "maker-breaker percolation games",
      "crossing game",
      "winning strategy",
      "crossing grids",
      "maker wins"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}