[pt] DUAS ABORDAGENS EM DESVIOS MODERADOS PARA CONTAGEM DE TRIÂNGULOS EM GRAFOS G(N, M)

• Ano de defesa: 2022
• Autor(a) principal: GABRIEL DIAS DO COUTO
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] GRAFOS ALEATORIOS; [pt] TRIANGULOS; [pt] TEORIA ESPECTRAL DE GRAFOS; [pt] MARTINGAIS; [pt] DESVIOS MODERADOS; [en] RANDOM GRAPHS; [en] TRIANGLES; [en] SPECTRAL GRAPH THEORY; [en] MARTINGALES; [en] MODERATE DEVIATIONS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=60043&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=60043&idi=2; http://doi.org/10.17771/PUCRio.acad.60043

[pt] O estudo de desvios, e em particular grandes desvios, tem uma história longa na teoria de probabilidade. Nas últimas décadas muitos artigos consideraram essas questões no contexto de subgrafos de grafos aleatórios G(n, p) e G(n, m). Esta dissertação considera a cauda inferior para o número de triângulos no grafo aleatório G(n, m). Duas abordagens estão consideradas: Martingales, a partir artigo de Christina Goldschmidt, Simon Griffiths e Alex Scott; e Teoria Espectral de Grafos, a partir do artigo de Joe Neeman, Charles Radin e Lorenzo Sadun. Essas duas abordagens conseguem encontrar o comportamento da cauda em dois regimes diferentes. Na dissertação discutiremos a visão geral do artigo de Goldschmidt, Griffiths e Scott, e discutiremos em detalhes o artigo de Neeman, Radin e Sadun. Em particular, exploraremos a conexão entre a cauda inferior do número de triângulos e o comportamento dos autovalores mais negativos da matriz de adjacência. Veremos que a contagem tende a depender, essencialmente, do autovalor mais negativo.