{
  "id": "2407.11495",
  "version": "v1",
  "published": "2024-07-16T08:32:33.000Z",
  "updated": "2024-07-16T08:32:33.000Z",
  "title": "Long cycles in percolated expanders",
  "authors": [
    "Maurício Collares",
    "Sahar Diskin",
    "Joshua Erde",
    "Michael Krivelevich"
  ],
  "comment": "7 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Given a graph $G$ and probability $p$, we form the random subgraph $G_p$ by retaining each edge of $G$ independently with probability $p$. Given $d\\in\\mathbb{N}$ and constants $0<c<1, \\varepsilon>0$, we show that if every subset $S\\subseteq V(G)$ of size exactly $\\frac{c|V(G)|}{d}$ satisfies $|N(S)|\\ge d|S|$ and $p=\\frac{1+\\varepsilon}{d}$, then the probability that $G_p$ does not contain a cycle of length $\\Omega(\\varepsilon^2c^2|V(G)|)$ is exponentially small in $|V(G)|$. As an intermediate step, we also show that given $k,d\\in \\mathbb{N}$ and a constant $\\varepsilon>0$, if every subset $S\\subseteq V(G)$ of size exactly $k$ satisfies $|N(S)|\\ge kd$ and $p=\\frac{1+\\varepsilon}{d}$, then the probability that $G_p$ does not contain a path of length $\\Omega(\\varepsilon^2 kd)$ is exponentially small. We further discuss applications of these results to $K_{s,t}$-free graphs of maximal density.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-16T08:32:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "long cycles",
      "percolated expanders",
      "probability",
      "exponentially small",
      "free graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}