Title: Embedding Large Graphs in Random Graphs
Speaker: Kyle Luh (Harvard University)
Abstract: In this talk, we consider the problem of embedding almost-spanning, bounded degree graphs in a random graph. In particular, let $\Delta\geq 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 $p\gg (n^{-1}\log^{1/\Delta}n)^{2/(\Delta+1)}$. Our assumption on $p$ is optimal up to the $polylog$ factor. We will also 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}$ simultaneously.
Seminar URL: https://u.osu.edu/probability/
