A probabilidade de não existir ciclos curtos num grafo esparso

Abstract

Consider a sequence of graphs, (Gn)n∈N, where each Gn is taken with distribution CM(D~ (n) ). Fixing h ∈ N and assuming certain regularity conditions on the sequence (D(n) )n∈N, Bordenave and Caputo proved in [Bordenave e Caputo 2015] that the asymptotic probability of Gn not having cycles of size ≤ h is positive. As a consequence, in [Bordenave e Caputo 2015], we have an asymptotic formula for the cardinality of the set of graphs with the same degree sequence as Gn that have short cycles, which was also presented and proven here. The proofs of these results presented here were divided into several smaller results, aiming to make the path as linear as possible during the reading. Additionally, we aimed to provide a much greater wealth of details during the demonstrations, as well as the requirements, in order to make the work (almost) self-contained.