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.

# Computer Science/Discrete Mathematics Seminar I

## 2-universality of random graphs.

### Featuring

Gal Kronenberg

### Speaker Affiliation

Tel Aviv University

### Affiliation

Mathematics

### Event Series

### Video

https://video.ias.edu/csdm/2018/1029-GalKronenbergDate & Time

October 29, 2018 | 11:15am – 12:15pm

### Location

Simonyi Hall 101