Coloracao de grafos e o metodo probabilistico.

• Processo: 03/12046-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2004
• Data de Término da vigência: 31 de julho de 2005
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Daniel Morgato Martin
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Coloracao Total | Conjectura De Vizing | Desigualdades Exponenciais | Lema Local De Lovasz | Metodo Probabilistico | Teoria Dos Grafos

Resumo

O objetivo principal deste projeto é a investigação de problemas de coloração de grafos atacáveis pelo método probabilístico. O tema central será a coloração total de grafos. Igualmente importante será o conjunto de técnicas probabilísticas que o candidato estudará, obtendo uma formação sólida tanto na teoria dos grafos clássica como na área de combinatória probabilística. Ao término do projeto, o candidato conhecerá ferramentas como resultados de concentração exponencial (cotas do tipo Chernoff, cotas exponenciais para grandes desvios de martingais, as desigualdades de Talagrand), o Lema Local de Lovász, e o método semi-aleatório de Rödl (o Rödl Nibble). (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

MARTIN, Daniel Morgato. Coloração de grafos e método probabilístico. 2005. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.