{
  "id": "2305.04850",
  "version": "v1",
  "published": "2023-05-08T16:47:00.000Z",
  "updated": "2023-05-08T16:47:00.000Z",
  "title": "Isomorphisms between dense random graphs",
  "authors": [
    "Erlang Surya",
    "Lutz Warnke",
    "Emily Zhu"
  ],
  "comment": "26 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM",
    "math.PR"
  ],
  "abstract": "We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-05-08T16:47:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C60",
      "60C05"
    ],
    "keywords": [
      "dense random graphs",
      "independent binomial random graphs",
      "sharp threshold result",
      "maximum common induced subgraph",
      "induced subgraph isomorphism problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}