Inevitabilidade de estruturas combinatórias em grafos e hipergrafos

• Processo: 25/07186-0
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de outubro de 2025
• Data de Término da vigência: 30 de setembro de 2028
• Área de 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: Henrique Stagni
• 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: 24/13859-4 - Teoria de Ramsey: de estruturas monocromáticas a canônicas, AP.R
• Assunto(s): Contêineres Grafos aleatórios Teoria de Ramsey
• Palavra(s)-Chave do Pesquisador: Contêineres | Grafos Aleatórios | imersão de estruturas em hipergrafos | Regularidade | Teoria de Ramsey | teste de propriedades | Combinatória e Algoritmos

Resumo

Este projeto descreve a pesquisa de pós-doutorado de Henrique Stagni, a ser desenvolvida sob a supervisão de Guilherme Mota, no Instituto de Matemática e Estatística da USP, no período de 01/06/2025 a 31/05/2028. A proposta está vinculada ao auxílio Regular 2024/13859-4, coordenado pelo supervisor, e contribuirá significativamente para o avanço de uma das linhas do projeto Temático 2023/03167-5, coordenado por Yoshiharu Kohayakawa, colaborador da pesquisa aqui proposta.O principal objetivo deste projeto consiste em obter avanços relevantes em problemas relacionados a condições que garantem a emergência de certas estruturas combinatórias inevitáveis em grafos e hipergrafos. Dividimos o estudo desse fenômeno em três vertentes distintas.Na primeira, esse fenômeno é estudado para hipergrafos (determinísticos). Mais especificamente, propomos problemas relacionados à obtenção de \emph{condições sobre o grau mínimo de um hipergrafo} que asseguram a emergência de certas estruturas, como árvores geradoras e emparelhamentos perfeitos.Na segunda vertente, abordamos esse tipo de fenômeno para grafos aleatórios, propondo problemas relacionados à \emph{Teoria de Ramsey}. Estudamos funções limiares que garantam a existência de certas estruturas ``canônicas'' que são inevitáveis em colorações arbitrárias do grafo aleatório $G(n,p)$.Por fim, analisamos esse tipo de fenômeno de forma mais quantitativa, propondo problemas sobre \emph{teste de propriedades} --- o foco dessa área está em determinar como a distância em relação uma dada propriedade faz emergir um grande número de estruturas locais que testemunham o não pertencimento àquela propriedade. Em particular, estudamos problemas relacionados a ``testadores alheios à proximidade'' --- uma versão mais restrita de testadores --- e problemas sobre propriedades de (hipergrafos que representam) configurações de pontos no plano.O candidato à bolsa possui excelente formação acadêmica e tem experiência prévia nos temas que serão investigados. O supervisor do projeto é um pesquisador experiente na área de combinatória extremal e probabilística, é autor de artigos cujos resultados e técnicas empregadas serão valiosos para a investigação dos problemas propostos, além de ser coautor do livro ``Combinatória''. (AU)