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

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

Título:      Dense H-free graphs are almost (\chi(H)-1)-partite
            
Palestrante: Peter Allen
             University of Warwick

Hora e Data: 14h00, sexta-feira, 11 de dezembro de 2009

Local:       auditório do NUMEC

Resumo:

Zarankiewicz  proved  that an  n-vertex  graph with  minimum
degree   exceeding  (r-1)n/r   must  contain   K_{r+1}.  The
Andr\'asfai-Erd\H{o}s-S\'os   theorem   provides  a   strong
stability result for the Zarankiewicz theorem.

Erd\H{o}s  and Stone  generalised the  Zarankiewicz theorem,
replacing the complete  graph with any (r+1)-chromatic graph
at the cost of an o(n) increase in the minimum degree. Quite
recently,  Alon and  Sudakov  used the  Regularity Lemma  to
obtain a corresponding stability result: however this result
was  not best  possible.  I will  describe  a simpler  proof
(avoiding  the Regularity  Lemma)  of a  statement which  is
conjectured to be best possible.