Title: Embedding Large Graphs in Random Graphs
Speaker: Kyle Luh, Yale University
Date: Monday, April 3, 2017 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $Deltageq 5$, $varepsilon > 0$ and let $H$ be a graph on $(1-varepsilon)n$ vertices and with maximum degree $Delta$. We show that a random graph $G_{n,p}$ with high probability contains a copy of $H$, provided that $pgg (n^{-1}log^{1/Delta}n)^{2/(Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. Time permitting, we will discuss recent progress on the "universality" problem, which entails finding the threshold for all graphs of degree at most $Delta$ to appear in $G_{n,p}$ emph{simultaneously}.