Title: Embedding spanning trees in random graphs near the connectivity threshold
Speaker: Michael Krivelevich, Tel Aviv University
Date: Tuesday, October 18, 2011 2:00pm
Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
A disconnected graph G does not contain any spanning trees. Thus a tree T on n vertices typically does not appear in the binomial random graph G(n,p) before the threshold for connectivity, which is well known to be at p(n)=log n/n. We prove that a given tree T on n vertices with bounded maximum degree is contained almost surely in G(n,p) with p=(1+epsilon)log n/n, provided T belongs to one of the following two classes: (1) T has linearly many leaves; (2) T has a path of linear length all of whose vertices have degree two in T. Joint work with Dan Hefetz and Tibor Szabo.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math