{
  "id": "2407.16458",
  "version": "v1",
  "published": "2024-07-23T13:15:06.000Z",
  "updated": "2024-07-23T13:15:06.000Z",
  "title": "Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs",
  "authors": [
    "Sahar Diskin",
    "Joshua Erde",
    "Mihyun Kang",
    "Michael Krivelevich"
  ],
  "comment": "7 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a graph $G$ and $p\\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $\\epsilon>0$, there exists a constant $C>0$ such that the following holds. Let $d\\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\\ge \\frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-\\epsilon)|V(G)|$ vertices. We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\\ge \\frac{\\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-23T13:15:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random subgraph",
      "regular subgraphs",
      "large matchings",
      "regular graph",
      "expected average degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}