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

  Tarde de Combinatória Extremal e Métodos Probabilísticos
============================================================

Título:      On two Ramsey type problems for K_{t+1}-free graphs
            
Palestrante: Vojtech Rödl 
             Emory University 

Hora e Data: 15h20, sexta-feira, 10 de maio de 2013

Local:       Sala Multi-usos do Numec

Resumo:

In 1970, Erdös and Hajnal asked  if for any r and t there is
a K_{t+1}-free graph H with the property that any r-coloring
of  the  edges  of  H  yields  a  monochromatic  K_t.   This
conjecture was resolved positively by Folkman for r=2 and by
Nesetril and  the speaker for  r arbitrary. In this  talk we
will  discuss  some old  and  new  results  related to  this
conjecture.

A   related  question   was   raised  by   A.  Hajnal.   The
t-independence  number  \alpha_t(H)  of  a graph  H  is  the
largest  size of  a subset  of vertices  of H  containing no
K_t. Let h_t(n) be the minimum value of \alpha_t(H) with the
minimum taken  over all graphs  on n vertices  containing no
K_{t+1}.  Hajnal  proposed   the  problem  of  investigating
h_t(n).  This  question was  addressed  first  by Erdös  and
Rogers, who  proved that  h_t(n) is at  most n^{1-\epsilon},
where \epsilon=\Theta(1/t^{4\log t}). Recently, jointly with
Dudek and Retter, we proved that h_t(n)=n^{1/2+o(1)} for any
given t.