[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:60043 |
| Date | 04 August 2022 |
| Creators | GABRIEL DIAS DO COUTO |
| Contributors | SIMON RICHARD GRIFFITHS |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0034 seconds