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

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

Título:      O método de condicionamento em subgrafos
            
Palestrante: Carlos Hoppen
             Universidade Federal do Rio Grande do Sul

Hora e Data: 14h00, sexta-feira, 16 de abril de 2010

Local:       auditório do NUMEC

Resumo:

Uma série de resultados probabilísticos em teoria dos grafos
pode ser obtida através  da desigualdade de Chebyshev, em um
argumento conhecido como o método do segundo momento. Porém,
há casos em que tal  método não produz o resultado desejado,
pois  a  variância  da   variável  aleatória  em  questão  é
excessivamente  grande.  O   método  de  condicionamento  em
subgrafos,  introduzido  por  Robinson  e Wormald  em  1995,
procura  reduzir essa variância  ao considerar  tal variável
condicionada  à  existência  de  subgrafos  de  determinados
tipos. Dentre os resultados  obtidos com este método, está o
fato  que, para cada  inteiro d  maior ou  igual a  três, um
grafo aleatório d-regular  é quase sempre Hamiltoniano. Além
disso,  um  resultado  recente  de Kemkes,  Pérez-Giménez  e
Wormald  encontra o  número  cromático de  tais grafos  para
diversos valores  de d. Por  exemplo, o número  cromático de
grafos  5-regulares é  quase  sempre 3,  enquanto que,  para
grafos   10^6-regulares,   este   número  é   quase   sempre
46523.  Nessa palestra, pretendemos  apresentar o  método de
condicionamento em subgrafos sob o ponto de vista de números
cromáticos.