{
  "id": "1809.01907",
  "version": "v1",
  "published": "2018-09-06T09:55:28.000Z",
  "updated": "2018-09-06T09:55:28.000Z",
  "title": "The sharp threshold for jigsaw percolation in random graphs",
  "authors": [
    "Oliver Cooley",
    "Tobias Kapetanopoulos",
    "Tamás Makai"
  ],
  "comment": "22 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We analyse the jigsaw percolation process, which may be seen as a measure of whether two graphs on the same vertex set are `jointly connected'. Bollob\\'as, Riordan, Slivken and Smith proved that when the two graphs are independent binomial random graphs, whether the jigsaw process percolates undergoes a phase transition when the product of the two probabilities is $\\Theta\\left( \\frac{1}{n\\ln n} \\right)$. We show that this threshold is sharp, and that it lies at $\\frac{1}{4n\\ln n}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-09-06T09:55:28.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "60K35",
      "60C05"
    ],
    "keywords": [
      "sharp threshold",
      "independent binomial random graphs",
      "jigsaw process percolates undergoes",
      "jigsaw percolation process",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}