Colóquio do Departamento de Matemática - Combinatória assintótica e o estudo de grafos e outros objetos discretos de grandes proporções

RESUMO

 

Yoshiharu Kohayakawa (USP)

Um resultado fundamental da teoria dos grafos, conhecido como o lema de regularidade de Szemerédi, diz que grafos grandes podem ser descritos de forma sucinta quando estamos interessados em certos tipos de problemas assintóticos. Quando uma sequencia de grafos cujas ordens tendem ao infinito é consistente em termos das estatísticas de subgrafos de tamanho fixo, podemos definir uma certa distribuição de probabilidade como o limite de tal sequência. Esses limites são os objetos limite de Lovász e Szegedy. Nesta palestra de caráter introdutório, discutiremos essas duas abordagens desenvolvidas nas últimas décadas para o estudo de grafos e outros objetos combinatórios de grandes proporções.

Carregando