# Combinatorics Seminar

When: Sunday, March 2, 10am

Where: Schreiber 309

Speaker: Asaf Ferber, ETH Zurich

Title: Universality of random graphs and rainbow embedding

## Abstract:

In this talk we discuss how to use simple partitioning lemmas combined
with an embedding argument based on matching (due to Alon and F\"uredi) in
order to embed spanning graphs in a typical member of G(n,p). First, we
improves a result of Johannsen, Krivelevich and Samotij, by providing a
better (smaller) p than their n^{-1/3} for which w.h.p a graph G~ G(n,p)
contains copies of all the spanning trees with maximum degree bounded
by \Delta=O(1) (in our case p=\omega(n^{-1/2}\polylog)). Next, using
similar methods we show that for p=\omega(n^{-1/2d}\log^2n), a graph G~
G(n,p) w.h.p contains copies of all spanning graphs H with maximum degree
bounded by \Delta and with density d, where d is the maximal average
degree of all the subgraphs of H. In case that the density is smaller
than half of the maximum degree, this improves a result of Dellamonica,
Kohayakawa, R\"odl and Ruci\'ncki. Finally, in the same spirit, we
show that for any spanning graph H with maximum degree \Delta=O(1),
and for an appropriate p, if we randomly color a graph G~G(n,p) with
(1+o(1))e(H) colors, then w.h.p there exists a rainbow copy of H in G
(that is, a copy of H with all edges colored with distinct colors).

Joint work with: Rajko Nenadov and Ueli Peter, two excellent PhD
students in my group.

redesigned by barak soreq