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