로그인
ACTIVITIES
Preprints
Home > Activities > Basic Research > Preprints
    Title      l  UNIVERSALITY OF RANDOM GRAPHS FOR GRAPHS OF MAXIMUM DEGREE TWO
    Author   l  JEONG HAN KIM AND SANG JUNE LEE
    Date   l  2013-10-24
    Category   l  ASARC-Prepint-13-11
    Download    l 1382591541_0.996827.pdf  
Abstract:
For a family $cF$ of graphs, a graph $G$ is called emph{$cF$-universal} if $G$ contains every graph in $cF$ as a subgraph. Let $cF_n(d)$ be the family of all graphs on $n$ vertices with maximum degree at most $d$. Dellamonica, Kohayakawa, Rodl~and Rucinski showed that, for $dgeq 3$, the random graph $G(n,p)$ is $cF_n(d)$-universal with high probability provided $pgeq Cig(frac{log n}{n}ig)^{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 $cF_n(2)$-universal with high probability provided $pgeq Cig(frac{log n}{n}ig)^{1/2}$ for a sufficiently large constant~$C$.