Rutgers Discrete Mathematics Seminar

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.