Joint Technion and University of Haifa Combinatorics Seminar
The next meeting of the Combinatorics Seminar will take place on Wednesday,
March 9 in *University of Haifa*.
Speaker: Michael Krivelevich (Tel Aviv University)
Time: Wednesday, March 9, 13:10
Place: Science and Education Building, room #665, University of Haifa.
Title: 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 max{D*log n,n^{\epsilon}}
for some positive \epsilon>0, then with high probability the random graph
G(n,p) contains a copy of T. In particular, G(n,n^{-1+\epsilon}) whp
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^{\Theta(1)}.
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Raphael Yuster   <raphael.yuster@gmail.com>