Tese de Doutorado - Leonardo Gonçalves de Oliveira

Moderate Deviations of Triangle Counts in Sparse Random Graphs

In the first part of this thesis, we study the deviation of the number of triangles with respect to its mean in both the random graph models G(n,m) and G(n,p). We focus on the case where the random graph is sparse, in which the edge density goes to zero as the number of vertices increases to infinity. Also, our focus is in the case of moderate deviations, i.e., those of order in between the standard deviation and the mean. In addition, we derive the same kind of results for cherries (paths of length two). In the second part of this thesis, we study Freedman's inequality. This inequality gives bounds on the probability of the deviation of a bounded martingale using its conditional variance. In our work, we obtain a strengthening of Freedman's inequality, under additional symmetry conditions on the increments of the martingale process