Propriedades anti-Ramsey: não-existência de cópias multicoloridas

• Processo: 21/09306-1
• Linha de fomento: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de setembro de 2021
• Vigência (Término): 31 de agosto de 2022
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Guilherme Oliveira Mota
• Beneficiário: Victor Manuel Dias Saliba
• 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 aleatórios Teorema de Ramsey

Resumo

Neste projeto estamos interessados em estudar os conceitos fundamentais referentes a grafos aleatórios para, a partir daí, investigar resultados recentes de pesquisa sobre problemas anti-Ramsey. Estamos interessados em investigar o seguinte problema: dado um grafo fixo $H$ e um grafo aleatório binomial $G(n,p)$, qual o maior valor de $p$ tal que existe uma coloração própria das arestas de $G(n,p)$ que não contém uma cópia multicolorida de $H$ com alta probabilidade. Na fase inicial deste projeto o aluno irá estudar capítulos de livros sobre grafos aleatórios, obtendo o conhecimento necessário para iniciar pesquisas na área. Em um segundo momento o aluno trabalhará no sentido de compreender artigos de pesquisa recentes sobre o tema, aprendendo as técnicas utilizadas para provar $0$-afirmações em problemas do tipo Ramsey e anti-Ramsey. (AU)