Seminários em Computação: Conjectura 1/50 de Erdős para grafos de Andrásfai

• Responsável: Programa de Pós-Graduação em Ciência da Computação
• Câmpus: Santo André
• Local: Bloco A, auditório 205-0
• Data: 10/08/2016
• Horário: 16:00 às 17:20
• Descrição:

  Palestrante: Guilherme Oliveira Mota (IME-USP)

  Título: Conjectura 1/50 de Erdős para grafos de Andrásfai

  Resumo: Seja G um grafo livre de triângulos com n vértices. Um resultado conhecido em Combinatória Extremal é que se G possui número cromático $chi(G)n/3$, então G é um blow-up de um certo grafo d-regular $F_d$ para algum d <= 1. Esses grafos são conhecidos como Grafos de Andrásfai. Erdős conjecturou que todo grafo livre de triângulos com n vértices contém um subconjunto de n/2 vértices que induzem no máximo de $n^2/50$ arestas. Nós confirmamos essa conjectura para todos os blow-ups de $F_d$, para d <= 1.
  (Trabalho em conjunto com Wiebke Bedenknecht, Mathias Schacht e Christian Reiher)

• Necessita inscrição: Não
• Link de divulgação: http://poscomp.ufabc.edu.br/index.php/15-portuguese/seminarios-em-computacao/96-seminario-guilherme-oliveira-mota
• Calendário do Google: https://www.google.com/calendar/event?ei ...

Para visualizar o calendário completo ou para solicitar divulgação de eventos, acesse aqui.