Yoshiharu Kohayakawa
IME-USP
Sexta-feira, 24 de maio de 2002, 15:15
Sala 267, Bloco A, IME-USP
Resumo:
Um trabalho recente complexo de E. Friedgut, V. Rödl, A. Ruci\'nski, e P. Tetali prova a existência de uma função limiar severa para a propriedade de Ramsey para triângulos em grafos aleatórios. Este trabalho contém a aplicação mais sofisticada até o momento do resultado de Friedgut sobre a exitência de funções limiares severas.
Um pequeno lema dentro deste trabalho versa sobre um jogo solitário em que um jogador pinta as arestas de um grafo aleatório, procurando evitar enquanto possível um triângulo monocromático. Relataremos alguns resultados que obtivemos com aqueles autores na análise desse jogo.
Encerraremos com um problema em aberto na área de teoria da complexidade computacional que tem leve relação com um dos tópicos que discutiremos nesta palestra.