Seminário de combinatória do IME-UFF

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.