Computer Science/Discrete Mathematics Seminar I

For a family of graphs F, a graph G is F-universal if G contains every graph in F as a (not necessarily induced) subgraph. A natural candidate to serve as universal graph G is the random graph G(n,p). In this case, we want to find an optimal p for which a typical G(n,p) is universal with respect to some given family F. We focus on the family H(n,d), consisting of all graphs on n vertices with maximum degree bounded by d. We prove that there exists a constant C such that for p > C ((log n)/(n^2))^{1/3}, the binomial random graph G(n,p) is typically H(n,2)-universal. This bound is optimal up to the constant factor as illustrated in the seminal work of Johansson, Kahn, and V u for triangle factors.

Our result improves significantly on the previous best bound of p > C ((log n)/n)^{1/2} and yielding the first tight result for the H(n,d)-universality problem. In fact, we prove the stronger result. Let H^{r}(n,2) be the family of all graphs on n vertices, of maximum degree at most two and of girth at least r. Then G(n,p) is typically H^{r}(n,2)-universal when p > C ((log n)/(n^{r -1}))^{1/r}. This result is also optimal up to the constant factor.

Joint work with Asaf Ferber and Kyle Luh.