Topics in random graph theory: limit theorems and mixing times of random walks

This doctoral dissertation is concerned with the study of static and dynamical observables of random graphs, with a particular attention to concentration phenomena and phase transitions. The thesis is divided in two parts. The first part of the thesis is devoted to the asymptotic analysis of two types of static graph observables. In the first chapter, we analyze the edge-triangle model, a random graph exhibiting dependence among edges. We prove concentration of the triangle count and, for some approximations of the model, we obtain more refined results including standard and non-standard central limit theorems, depending on the value of the parameters. In a mean-field setting, our results are supported by simulations. The results rely on large deviation principles and the analyticity properties of the free energy of the model. In the second chapter we consider a family of inhomogeneous directed random graphs, which includes the Chung--Lu directed graph and stochastic block models, and we consider their adjacency matrices. We establish the existence of eigenvalues outside the bulk of their spectrum, for which we prove Gaussian fluctuations. The results are based on the trace method and a perturbative analysis. In the second part of the thesis, we consider the simple random walk (SRW) on directed random graphs, we characterize its mixing properties and we give particular emphasis to the cutoff phenomenon. In the third chapter we analyze the SRW on the Chung--Lu directed graph. For this dynamics we prove the occurrence of the cutoff phenomenon at entropic time. We characterize the size of the cutoff window, in which the total variation profile converges to a universal Gaussian shape, independent of the parameters. Finally, the fourth chapter is concerned with the mixing properties of the SRW on a directed graph exhibiting a community structure, corresponding to a directed version of the stochastic block model. For this model, depending on the strength of the community structure, we show the occurrence of a mixing trichotomy. In particular, we identify three mixing regimes, where the cutoff survives to the bottleneck perturbation or is substituted by an exponential relaxation, and we provide a first-order characterization of the total variation profile. A substantial part of the analysis is given by a control on the homogenization of the random environment.