Dissertação de Mestrado - Gabriel Dias do Couto

Two Approaches on Moderate Deviations in Triangle Count in G(n,m) Graphs

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.