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

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

Título:      Uma melhora do Lema Local de Lovász via técnicas 
             de mecânica estatística

Palestrante: Aldo Procacci
             Universidade Federal de Minas Gerais

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

Local:       auditório do NUMEC

Resumo:

Um  velho resultado  de Shearer  relaciona o  Lema  Local de
Lovász   com   o  polinômio   dos   conjuntos  de   vértices
independentes   de  um   grafo  e,   consequentemente,  como
observado por  Scott e Sokal,  com a função partição  do gás
hard-core sobre  o próprio grafo.  Usamos esta  conexão e um
recente  resultado  sobre a  analiticidade  do logarítmo  da
função partição do gás  de polímeros abstrato para obter uma
versão melhorada do Lema  Local de Lovász.  Como exemplos de
aplicações  apresentamos novas  cotas para  as  condições de
existência   de   transversais   latinas   em   matrizes   e
satisfatibilidade de k-SAT.