{
  "id": "1503.05612",
  "version": "v1",
  "published": "2015-03-18T23:16:21.000Z",
  "updated": "2015-03-18T23:16:21.000Z",
  "title": "Almost-spanning universality in random graphs",
  "authors": [
    "David Conlon",
    "Asaf Ferber",
    "Rajko Nenadov",
    "Nemanja Škorić"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph $G$ is said to be $\\mathcal H(n,\\Delta)$-universal if it contains every graph on $n$ vertices with maximum degree at most $\\Delta$. It is known that for any $\\varepsilon > 0$ and any natural number $\\Delta$ there exists $c > 0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\\mathcal H((1-\\varepsilon)n,\\Delta)$-universal for $p \\geq c (\\log n/n)^{1/\\Delta}$. Bypassing this natural boundary, we show that for $\\Delta \\geq 3$ the same conclusion holds when $p = \\omega\\left(n^{-\\frac{1}{\\Delta-1}}\\log^5 n\\right)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-03-18T23:16:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random graph",
      "almost-spanning universality",
      "maximum degree",
      "natural number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150305612C"
    }
  }
}