Combinatorics Seminar

When: Sunday, March 2, 10am

Where: Schreiber 309

Speaker: Asaf Ferber, ETH Zurich

Title: Universality of random graphs and rainbow embedding


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.

w3c valid   accessible website
redesigned by barak soreq