Busca avançada
Ano de início
Entree

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

Processo: 19/27350-8
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de abril de 2020
Vigência (Término): 31 de março de 2022
Área do 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

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)