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

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

Título:      The structure of a typical H-free graph

            
Palestrante: Robert Morris
             IMPA

Hora e Data: 14h, sexta-feira, 29 de setembro de 2010

Local:       auditório do NUMEC

Resumo:

A collection of graphs  \P is called a "hereditary property"
if it is closed under taking induced subgraphs; for example,
consider the  family of all  graphs which do not  contain an
induced  copy  of some  graph  H. The  speed  of  \P is  the
function n \to  |\P_n|, where \P_n denotes the  graphs in \P
of order n.

It was shown by Alekseev, and by Bollobas and Thomason, that
if  \P is  a hereditary  property of  graphs then  

(1 / {n \choose 2}) \log_2 |\P_n| \to 1-1/r as n \to \infty,

where r =  r(\P) \in \N is the  so-called 'colouring number'
of \P. However, their results  tell us very little about the
structure of a typical graph G \in \P.

In this talk I shall  describe the structure of almost every
graph  in  a  hereditary   property  of  graphs,  \P.  As  a
corollary, we  shall obtain  an essentially optimal  rate of
convergence in the Alekseev-Bollobas-Thomason Theorem. These
results generalize some of  those proved by Balogh, Bollobas
and Simonovits for 'monotone' properties of graphs.

This is joint work with Noga Alon, Jozsi Balogh and Bela
Bollobas.