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