Colorações restritas de grafos aleatórios

Speakers: Guilherme Mota, USP.

Date: 28 apr 2021, 14h.

Place: Google Meet: meet.google.com/dra-gigp-gny.

Abstract: Dados grafos G, H_1 e H_2, denote por G ---> (H_1, H_2) a seguinte propriedade: em toda coloração das arestas de G há uma cópia monocromática de H_1 ou uma cópia "arco-íris" de H_2 (uma cópia de H_2 em que todas as arestas têm cores diferentes).

O número de Ramsey restrito, definido como o menor n tal que K_n ---> (H_1, H_2), existe se e somente se H_1 é uma estrela ou H_2 é uma floresta. Neste seminário vou determinar o "threshold" para a propriedade G (n, p) ---> (H_1, H_2) quando H_2 é uma floresta.

Este é um trabalho conjunto com Maurício Collares, Yoshiharu Kohayakawa e Carlos Gustavo Moreira.