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

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

Título:      Induced C_5-free graphs of fixed density: 
                     counting and homogenous sets

            
Palestrante: Andreas Würfl
             Technische Universität München

Hora e Data: 15h30m, sexta-feira, 18 de março de 2011

Local:       auditório do NUMEC

Resumo:

For c in (0,1) let P_n(c) denote the set of n-vertex perfect
graphs with density c and  C_n(c) the set of n-vertex graphs
without induced C_5 and with density c. We show that

  log |P_n(c)|/n^2 = log|C_n(c)|/n^2 = 0.5 h(c) + o(1)

with h(c) = 0.5 if 0.25 < c < 0.75  and  h(c) = 2H(|2c - 1|)
otherwise,   where  H  is   the  binary   entropy  function.
Furthermore, we  use this result  to deduce that  almost all
graphs in C_n(c) have  homogeneous sets of linear size. This
answers a special case of a question raised by Loebl et al.

The  proofs  of these  results  combine elementary  counting
arguments with  the regularity  method. We will  sketch both
and point out how these  could be used to extend the results
to  counting graphs  without induced  F for  F being  an odd
cycle of length at least 7.

This is based on  joint work  with Julia Böttcher and Anusch
Taraz.