voltarData: 31/05/2023
Título: Grafos aleatórios.
Palestrante: Luiz Moreira, UFPE.
Data: 31 de Maio de 2023, 14:30 h.
Sala: Google Meet.
Resumo: Nas últimas décadas, o estudo dos grafos aleatórios tem ocupado posição de destaque na área de Combinatória. Inicialmente como uma ferramenta inovadora, mas, atualmente, também de forma independente. Um dos modelos mais estudado de grafo aleatório é o de Erdös-Rényi, G(n,p), que é o seguinte: num conjunto de n vértices cada par de vértices é conectado, independentemente, com probabilidade p. As perguntas naturais para o modelo são da forma: qual a probabilidade de G(n,p) satisfazer uma dada propriedade? E, de forma geral, as perguntas mais desafiadoras são para grafos esparsos, quando p = p(n) (uma função de n) vai para zero quando n vai para infinito.
Um resultado clássico sobre G(n,p), provado pelos próprios Erdös e Rényi é: se p >> (log n)/n, então a probabilidade de G(n,p) ser conexo converge para 1 quando n vai para o infinito.
O interessante desse resultado é que ele garante que o jeito mais “fácil” para G(n,p) ser desconexo é ter um vértice isolado.
Nessa palestra usaremos um outro modelo para dígrafo aleatório, mas provaremos um resultado esteticamente parecido. Que no momento em que os impedimentos mais óbvios desaparecem, a propriedade que estamos procurando também começa a valer.