Embedding Almost Spanning Bounded Degree Trees

COMPUTER SCIENCE/DISCRETE MATH SEMINAR, I
Topic:	Embedding Almost Spanning Bounded Degree Trees
Speaker:	Michael Krivelevich
Affiliation:	Tel Aviv University
Date:	Monday, February 7
Time/Room:	11:15am - 12:15pm/S-101

---

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d>=2 and 0<epsilon<1, there exists a constant c=c(d,epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-epsilon)n vertices with maximum degree at most d.
We also prove that if an (n,D,lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most lambda in their absolute values) has large enough spectral gap D/lambda as a function of d and epsilon, then G has a copy of every tree T as above.

Joint work with Benny Sudakov, Princeton University.