Maya Stein
Posdoc do DCC-IME-USP
Sexta-feira, 23 de março de 2007, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Our talk is about an interesting conjecture of Loebl, Komlós, and Sós, which affirms the following. Given some natural number k, and some graph G, assume that at least half of the vertices of G have degree at least k. Then each tree with k edges is a subgraph of G.
Using Szemerédi's regularity lemma, and a version of Edmonds' and Gallai's matching theorem, we prove an approximate version of this conjecture for large enough graphs G, under the additional requirement that k is linear in n.
This is joint work with Diana Piguet.