Title: 2-universality of random graphs.
| Speaker: | Gal Kronenberg |
| Affiliation: | Tel Aviv University |
| Room: | *MC 6486* |
Abstract: 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 Vu 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.