## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Graphs and Matroids Seminar- Gal Kronenberg

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

### September 2021

S M T W T F S
29
30
31
1
2
4
5
6
7
8
11
12
14
15
16
18
19
21
22
23
25
26
27
28
29
30
1
2
1. 2021 (85)
1. October (1)
2. September (8)
3. August (7)
4. July (10)
5. June (12)
6. May (7)
7. April (9)
8. March (13)
9. February (8)
10. January (10)
2. 2020 (119)
1. December (5)
2. November (12)
3. October (12)
4. September (12)
5. August (11)
6. July (17)
7. June (11)
8. May (6)
9. March (11)
10. February (11)
11. January (11)
3. 2019 (167)
4. 2018 (136)
5. 2017 (103)
6. 2016 (137)
7. 2015 (136)
8. 2014 (88)
9. 2013 (48)
10. 2012 (39)
11. 2011 (36)
12. 2010 (40)
13. 2009 (40)
14. 2008 (39)
15. 2007 (15)