{
  "id": "1310.5873",
  "version": "v1",
  "published": "2013-10-22T10:43:05.000Z",
  "updated": "2013-10-22T10:43:05.000Z",
  "title": "Universality of random graphs for graphs of maximum degree two",
  "authors": [
    "Jeong Han Kim",
    "Sang June Lee"
  ],
  "comment": "13 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "For a family $\\mathcal{F}$ of graphs, a graph $G$ is called \\emph{$\\mathcal{F}$-universal} if $G$ contains every graph in $\\mathcal{F}$ as a subgraph. Let $\\mathcal{F}_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$. Dellamonica, Kohayakawa, R\\\"odl and Ruci\\'nski showed that, for $d\\geq 3$, the random graph $G(n,p)$ is $\\mathcal{F}_n(d)$-universal with high probability provided $p\\geq C\\big(\\frac{\\log n}{n}\\big)^{1/d}$ for a sufficiently large constant $C=C(d)$. In this paper we prove the missing part of the result, that is, the random graph $G(n,p)$ is $\\mathcal{F}_n(2)$-universal with high probability provided $p\\geq C\\big(\\frac{\\log n}{n}\\big)^{1/2}$ for a sufficiently large constant $C$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-22T10:43:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C80",
      "05C60"
    ],
    "keywords": [
      "random graph",
      "maximum degree",
      "sufficiently large constant",
      "universality",
      "high probability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.5873K"
    }
  }
}