Speaker: Walner Mendonça, IST Austria.
Date: 01 dec 2021, 14h.
Place: Google Meet: swt-uoda-eyn.
Abstract:
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 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 de grau limitado F, 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 F. Eles conjecturaram que para r-colorações, também deve ser possível particionar V(K_n) em uma quantidade exponencial de cópias monocromáticas de grafos da sequência F. 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 F. Neste trabalho apresentamos o primeiro progresso na conjectura de Grinshpun e Sárkőzy estabelecendo um limitante super-exponencial.
Apresentação baseada em um trabalho conjunto com Jan Corsten (LSE, UK).