Partições monocromáticas de grafos completos

• Processo: 21/09286-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2021
• Data de Término da vigência: 31 de agosto de 2022
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Guilherme Oliveira Mota
• Beneficiário: André Yuji Hisatsuga
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática, AP.JP
• Assunto(s): Combinatória Grafos Modelagem de partição bayesiana Teorema de Ramsey
• Palavra(s)-Chave do Pesquisador: grafos completos | lema da regularidade | partição | Ramsey | Combinatória

Resumo

Problemas em Teoria de Ramsey relacionados a particionar o conjunto de vértices de um grafo $G$ em estruturas monocromáticas (dada uma certa coloração das arestas do grafo) sempre intrigou os pesquisadores da área. Recentemente, diversos avanços foram obtidos através do uso de diferentes técnicas (antigas e modernas). Neste projeto, planejamos que o aluno estude em detalhes os artigos que levaram à solução definitiva do problema de particionar em circuitos monocromáticos todos os grafos completos cujas arestas são coloridas. Isso levará o aluno a compreender em detalhes algumas das técnicas usualmente aplicadas em Teoria de Ramsey. Por fim, o aluno estudará um trabalho recente de Grinshpun e Sárközy que trata de uma generalização do problema de particionar grafos completos em circuitos monocromáticos. (AU)