============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      The tree packing conjecture of Gyárfás and Lehel
            
Palestrante: Julia Böttcher
             London School of Economics and Political Science

Hora e Data: 16h, sexta-feira, 31 de agosto de 2012

Local:       Sala Multi-usos do Numec

Resumo:

An old  and surprising  conjecture of Gy\'arf\'as  and Lehel
states the following.  Let T_1,T_2,T_3,...,T_n be any family
of trees such that T_i has i vertices for each i. Then these
trees  can  be packed  into  the  complete  graph K_n  on  n
vertices.  In  the talk I  will outline the history  of this
conjecture and  explain some aspects of  our recent approach
(in joint  work with Jan  Hladk\'y, Diana Piguet  and Anusch
Taraz) for  an approximate  version for families  of bounded
degree trees.  Our proof uses a random  embedding method and
relies on properties of  pseudo-random graphs, which I shall
also illustrate.