voltarData: 01/12/2021
Título: Particionando grafos completos coloridos em poucos subgrafos esparsos monocromáticos.
Palestrante: Walner Mendonça, IST - Austria.
Data: 01 de Dezembro de 2021, 14 h.
Sala: Google Meet.
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 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.
Obs. Joint work with Jan Corsten (LSE, UK).
Veja: Vídeo