{
  "id": "2106.08975",
  "version": "v1",
  "published": "2021-06-16T17:16:49.000Z",
  "updated": "2021-06-16T17:16:49.000Z",
  "title": "Short proofs for long induced paths",
  "authors": [
    "Nemanja Draganić",
    "Stefan Glock",
    "Michael Krivelevich"
  ],
  "comment": "9 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We present a modification of the DFS graph search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\\hat{R}_{\\mathrm{ind}}(P_n)\\leq 5\\cdot 10^7n$, thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and {\\L}uczak. We also provide a bound for the $k$-color version, showing that $\\hat{R}_{\\mathrm{ind}}^k(P_n)=O(k^3\\log^4k)n$. Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\\frac{1+\\varepsilon}{n})$, contains typically an induced path of length $\\Theta(\\varepsilon^2) n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-06-16T17:16:49.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "short proof",
      "dfs graph search algorithm",
      "regularity lemma argument",
      "binomial random graph",
      "paths satisfies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}