Título
[pt] DUAS ABORDAGENS EM DESVIOS MODERADOS PARA CONTAGEM DE TRIÂNGULOS EM GRAFOS G(N, M)
Título
[en] TWO APPROACHES TO MODERATE DEVIATIONS IN TRIANGLE COUNT IN G(N, M) GRAPHS
Autor
[pt] GABRIEL DIAS DO COUTO
Vocabulário
[pt] GRAFOS ALEATORIOS
Vocabulário
[pt] TRIANGULOS
Vocabulário
[pt] TEORIA ESPECTRAL DE GRAFOS
Vocabulário
[pt] MARTINGAIS
Vocabulário
[pt] DESVIOS MODERADOS
Vocabulário
[en] RANDOM GRAPHS
Vocabulário
[en] TRIANGLES
Vocabulário
[en] SPECTRAL GRAPH THEORY
Vocabulário
[en] MARTINGALES
Vocabulário
[en] MODERATE DEVIATIONS
Resumo
[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.
Resumo
[en] The study of deviations, and in particular large deviations, has a long
history in Probability Theory. In recent decades many articles have considered
these questions in the context of subgraphs of the random graphs G(n, p) and
G(n, m). This dissertation considers the lower tail for the number of triangles in
the random graph G(n, m). Two approaches are considered: Martingales, based
on the article of Christina Goldschmidt, Simon Griffiths and Alex Scott; and
Spectral Graph Theory, based on the article of Joe Neeman, Charles Radin and
Lorenzo Sadun. These two approaches manage to find the behavior of the tail
in two different regimes. In this dissertation we give an overview of the article of
Goldschmidt, Griffiths and Scott, discuss in detail the article of artigo Neeman,
Radin and Sadun. In particular, we shall explore the connection between the
lower tail of the number of triangles and the behavior of the most negative
eigenvalues of the adjacency matrix. We shall see that the triangle count tends
to especially depend on the most negative eigenvalue.
Orientador(es)
SIMON RICHARD GRIFFITHS
Banca
ROBERT DAVID MORRIS
Banca
SIMON RICHARD GRIFFITHS
Banca
MARIA EULALIA VARES
Banca
JOSE DIEGO ALVARADO MORALES
Catalogação
2022-08-04
Apresentação
2022-04-19
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=60043@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=60043@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.60043
Arquivos do conteúdo
NA ÍNTEGRA PDF