Título: | TWO APPROACHES TO MODERATE DEVIATIONS IN TRIANGLE COUNT IN G(N, M) GRAPHS | ||||||||||||
Autor: |
GABRIEL DIAS DO COUTO |
||||||||||||
Colaborador(es): |
SIMON RICHARD GRIFFITHS - Orientador |
||||||||||||
Catalogação: | 04/AGO/2022 | Língua(s): | ENGLISH - UNITED STATES |
||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=60043&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=60043&idi=2 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.60043 | ||||||||||||
Resumo: | |||||||||||||
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.
|
|||||||||||||
|