Partição de grafos aleatórios em cópias monocromáticas

• Processo: 19/27350-8
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de abril de 2020
• Data de Término da vigência: 30 de junho 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: Juliane Kristine de Lima
• Instituição Sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , 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 aleatórios Teorema de Ramsey
• Palavra(s)-Chave do Pesquisador: cópias monocromáticas | Função limiar | Grafos Aleatórios | partição | Combinatória

Resumo

Bal e DeBiasio apresentaram uma conjectura a respeito da função limiar para a seguinte propriedade do tipo Ramsey para grafos G: em toda coloração das arestas de G com r cores, existem r árvores monocromáticas duas a duas disjuntas nos vértices que particionam todo o conjunto de vértices de G. Recentemente foi provado que quando consideramos colorações com 2 cores, a função limiar para essa propriedade é dada por ((\log n)/n)^{1/2}. Neste projeto, estudaremos em detalhes esse resultado e investigaremos qual a função limiar dessa propriedade quando temos mais que 2 cores. Ademais, investigaremos problemas similares que dizem respeito a partições e coberturas dos vértices de G(n,p) em outras estruturas monocromáticas (e.g., caminhos, circuitos). (AU)