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.

w3c valid   accessible website
redesigned by barak soreq