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

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

Título:      Turán numbers of Linear and Equibipartite Forests
            
Palestrante: Neal Owen Bushaw
             University of Memphis

Hora e Data: 14h, sexta-feira, 14 de dezembro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

The  Turán number  of a  graph  H, ex(n,H),  is the  maximum
number of  edges in any graph  on n vertices  which does not
contain  H  as  a subgraph.  Let  P_l  denote  a path  on  l
vertices,  and  k*P_l denote  k  vertex  disjoint copies  of
P_l.  We  first  determine  ex(n,k*P_3),  answering  in  the
positive  a  conjecture  of  Gorgol. Further,  we  determine
ex(n,k*P_l)  for  arbitrary  l,  and n  appropriately  large
relative to  k and  l. We provide  a some background  on the
famous Erdös-Sós conjecture, and conditional on its truth we
determine  ex(n,H)   when  H  is  a   forest  consisting  of
equibipartite  trees,   for  appropriately  large   n.  Time
permitting,   we  will  also   discuss  extensions   to  the
hypergraph context.


This is joint work with Nathan Kettle at the University of
Cambridge.