Embedding spanning trees in random graphs

We prove that if T is a tree on n vertices with maximum degree D and the edge probability p(n) satisfies:
np c maxD*log n,nε
for some positive ε0, then with high probability (w.h.p.) the random graph G(n,p) contains a copy of T. In particular, G(n,n-1+ε) w.h.p. contains a copy of any given bounded degree tree T on n vertices. The obtained bound on the edge probability is shown to be essentially tight for D=nΘ(1).

Speaker Details

Michael Krivelevich is a Professor of Mathematics at Tel Aviv University. He got his PhD in Tel Aviv in 1997 under the supervision of Noga Alon and returned to Tel Aviv University after a postdoc with the Institute for Advanced Study in Princeton and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Rutgers University. He works in the field of Combinatorics and its applications and has authored more than 130 papers on the subject.

Michael Krivelevich
Tel Aviv University
    • Portrait of Jeff Running

      Jeff Running