{
  "id": "2004.03359",
  "version": "v1",
  "published": "2020-04-07T13:34:09.000Z",
  "updated": "2020-04-07T13:34:09.000Z",
  "title": "Large induced matchings in random graphs",
  "authors": [
    "Oliver Cooley",
    "Nemanja Draganić",
    "Mihyun Kang",
    "Benny Sudakov"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by Erd\\H{o}s and Bollob\\'as, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/n\\le p \\le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2\\log_q(np)$, where $q= \\frac{1}{1-p}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-04-07T13:34:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C70"
    ],
    "keywords": [
      "large induced matchings",
      "binomial random graph",
      "high probability",
      "independence number",
      "large constant"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}