Título: Cliques quase-maximais em grafos aleatórios
Data: 09/01/2023, às 15:30h
Local: CT - Instituto de Matemática/UFRJ, Bloco B - sala B106-A
Palestrante: Simon Griffiths (PUC/RJ)

Resumo: Consideramos a questão de quantos cliques quase-maximais disjuntos podem ser encontrados num grafo aleatório G(n,p). Em 1992, Alon e Spencer conjecturaram que existe uma família de ordem n^2/(log n)^2 tais cliques disjuntos. Recentemente Acan e Kahn mostraram que a conjectura é falsa, provando uma cota superior da forma O(n^2/(log n)^3). Nós fornecemos uma cota inferior da mesma ordem.

Informações sobre todo o programa dos seminários de probabilidade clique AQUI