{
  "id": "math/0601659",
  "version": "v1",
  "published": "2006-01-26T22:08:17.000Z",
  "updated": "2006-01-26T22:08:17.000Z",
  "title": "Positional games on random graphs",
  "authors": [
    "Milos Stojakovic",
    "Tibor Szabo"
  ],
  "journal": "Random Structures & Algorithms 26 (2005), 204-223",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We introduce and study Maker/Breaker-type positional games on random graphs. Our main concern is to determine the threshold probability $p_{F}$ for the existence of Maker's strategy to claim a member of $F$ in the unbiased game played on the edges of random graph $G(n,p)$, for various target families $F$ of winning sets. More generally, for each probability above this threshold we study the smallest bias $b$ such that Maker wins the $(1\\:b)$ biased game. We investigate these functions for a number of basic games, like the connectivity game, the perfect matching game, the clique game and the Hamiltonian cycle game.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-01-26T22:08:17.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A24",
      "05C80"
    ],
    "keywords": [
      "random graph",
      "study maker/breaker-type positional games",
      "hamiltonian cycle game",
      "clique game",
      "threshold probability"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......1659S"
    }
  }
}