Data: 13/08/2020, às 14:00 horas (GMT-3, horário de Brasília).
Título: Particionando grafos completos coloridos em poucos subgrafos esparsos monocromáticos
Palestrante: Walner Mendonça (University of Warwick)


Resumo: Gerencsér e Gyárfás provaram em 1967 que para qualquer 2-coloração das arestas de K_n, é possível particionar V(K_n) em dois caminhos monocromáticos. Tal resultado, cuja a prova é bastante simples, motivou inúmeros outros problemas desafiantes os quais têm sido objetos de extensa pesquisa em combinatória extremal nos últimos anos. Por exemplo, Erdős, Gyárfás e Pyber conjecturaram em 1991 que para toda r-coloração de K_n existem r caminhos monocromáticos particionando V(K_n). Podemos também encontrar na literatura outras versões do problema onde ao invés de obtermos particionamento por caminhos, foca-se em obter particionamento por árvores, ciclos ou até mesmo potência de ciclos.

Grinshpun e Sárközy estudaram uma versão mais geral do problema onde interessa-se em particionar V(K_n) em subgrafos monocromáticos de grau limitado. Eles provaram que para toda sequência de grafos S = (F_i, i \in \mathbb{N}) com |F_i| = i e \Delta(F_i) \leq D, o seguinte vale: para qualquer 2-coloração das arestas de K_n é possível particionar V(K_n) em no máximo 2^{O(D \log D)} cópias monocromáticas de grafos da sequência S. Eles conjecturaram que para r-colorações, também deve ser verdade que é possível particionar V(K_n) em uma quantidade exponencial de cópias monocromáticas de grafos da sequência S. Mais precisamente, a conjectura deles afirma que para todo inteiro positivo r, existe uma constante C=C(r) para o qual o seguinte vale: para qualquer r-coloração das arestas de K_n, é possível particionar V(K_n) em no máximo 2^{D^C} cópias monocromáticas de grafos da sequência S. Neste trabalho apresentamos o primeiro progresso na conjectura de Grinshpun e Sárközy estabelecendo um limitante triplamente exponencial.

Esta apresentação é baseada em um trabalho conjunto com Jan Corsten (LSE, UK).