Fronteiras na Teoria de Ramsey (CNPq - Universal 2021)

Descrição:Tipicamente, em Teoria de Ramsey, investigamos a existência ou não de partições de uma dada estrutura matemática de forma que todas as partes evitem uma propriedade de interesse. Resultados célebres da teoria afirmam que não existem tais partições que evitam subestruturas de interesse em todas as partes. A Teoria de Ramsey também pode ser entendida como uma grande generalização da teoria de coloração de grafos e hipergrafos. Aqui, focaremos em grafos, tanto determinísticos quanto aleatórios. Investigaremos principalmente problemas dos tipos "size-Ramsey", "Coberturas/partições monocromáticas" e "colorações irregulares". A seguir apresentamos uma breve descrição desses tipos de problemas e variações: (i) Estimar para certos grafos H a menor quantidade de arestas m tal que existe um grafo G com m arestas de modo que toda k-coloração de E(G) contém uma cópia monocromática de H; (ii) Investigar o quão denso deve ser um grafo aleatório para que, dada qualquer coloração das arestas desse grafo com k cores, consigamos cobrir/particionar seus vértices em f(k) cópias de grafos de uma dada família; (iii) Estimar, para grafos G, a menor quantidade de cores necessárias para colorir as arestas de G evitando um certo subgrafo pequeno monocromático.

Membros: Guilherme Oliveira Mota (USP) - coordenador, Roberto Freitas Parente (UFBA), Antonio Josefran de Oliveira Bastos (UFC), Carlos Hoppen (UFRGS), Cristiane Maria Sato (UFABC), Lucas Colucci Cavalcante de Souza (USP), Maurício de Lemos Rodrigues Collares Neto (TU Graz), Maycon Sambinelli (UFABC), Taísa Lopes Martins (UFF), Yoshiharu Kohayakawa (USP)