{
  "id": "1909.00030",
  "version": "v1",
  "published": "2019-08-30T18:34:47.000Z",
  "updated": "2019-08-30T18:34:47.000Z",
  "title": "Ramsey Goodness of Paths in Random Graphs",
  "authors": [
    "Luiz Moreira"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We say that a graph $G$ is Ramsey for $H_1$ versus $H_2$, and write $G \\to (H_1,H_2)$, if every red-blue colouring of the edges of $G$ contains either a red copy of $H_1$ or a blue copy of $H_2$. In this paper we study the threshold for the event that the Erd\\H{o}s--R\\'enyi random graph $G(N,p)$ is Ramsey for a clique versus a path. We show that $$G\\big( (1 + \\varepsilon) rn,p \\big) \\to (K_{r+1},P_n)$$ with high probability if $p \\gg n^{-2 / (r + 1)}$, and $$G\\big( rn + t, p \\big) \\to (K_{r+1},P_n)$$ with high probability if $p \\gg n^{-2 / (r + 2)}$ and $t \\gg 1/p$. Both of these results are sharp (in different ways), since with high probability $G(Cn,p) \\not\\to (K_{r+1}, P_n)$ for any constant $C > 0$ if $p \\ll n^{-2/(r + 1)}$, and $G(rn + t, p) \\not\\to (K_{r+1}, P_n)$ if $t \\ll 1/p$, for any $0 < p \\le 1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-08-30T18:34:47.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "ramsey goodness",
      "high probability",
      "blue copy",
      "red copy"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}