DIMACS Theoretical Computer Science Seminar

Title: Loebl-Komlos-Sos Conjecture: dense case

Speaker: Jan Hladky, Charles University, Prague

Date: Wednesday, January 23, 2008 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


The Loebl-Komlos-Sos conjecture asserts that any graph of order n which has at least half of its vertices of degrees at least k contains any tree with k edges as a subgraph. In the talk, I shall sketch a proof of this conjecture in the case when k is linear in n. The proof uses the Regularity lemma and combines tools developed by Piguet and Stein and by Zhao. This is joint work with Diana Piguet.