O Seminário de Combinatória continua as suas atividades de forma online, apoiando as medidas de distanciamento social determinadas durante a pandemia do COVID-19. Desta vez agradecemos a presença de Walner Mendonça do IST Austria.
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário.
Não é necessária inscrição prévia.
Agradecemos a presença e a ajuda na divulgação. Compartilhem!
Data: 01/12/2021 (quarta-feira)
Horário:14h
Sala: Meet – swt-uoda-eyn (google.com)
Palestrante: Walner Mendonça.
Título: Particionando grafos completos coloridos em poucos subgrafos esparsos monocromáticos
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.
Esta apresentação é baseada em um trabalho conjunto com Jan Corsten (LSE, UK).
Nossos seminários acontecem regularmente desde 2015 e todas as ações podem ser encontradas em:
http://www.antenabrasil.uff.br/index.php/pt-br/acoes/seminario-combinatoria
Cadastre-se na lista de emails para atualizações sobre os próximos seminários ou eventuais mudanças.