Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

Thursday, November 8, 2018 — 3:30 PM EST

**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.

Location

MC - Mathematics & Computer Building

6486

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

200 University Avenue West

Waterloo, ON N2L 3G1

Canada

Please email any errors or updates to our website support/editor.

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1