Some asymptotic problems for dynamical random graphs

Wang, Xuan

Download PDF

Request Version for Screen Reader

Last Modified

March 21, 2019

Creator

Wang, Xuan
- Affiliation: College of Arts and Sciences, Department of Statistics and Operations Research

Abstract

This dissertation consists of two parts. In the first part we study the phase transition of a class of dynamical random graph processes, that evolve via the addition of new edges in a manner that incorporates both randomness as well as limited choice. As the density of edges increases, the graphs display a phase transition from the subcritical regime, where all components are small, to the supercritical regime, where a giant component emerges. We are interested in the behavior at criticality. First, we consider the simplest model of this kind, namely the Bohman-Frieze process. We show that the stochastic process of component sizes, in the critical window for the Bohman-Frieze process after proper scaling, converges to the standard multiplicative coalescent. Next, we study a more general family of dynamical random graph models, namely, the bounded-size-rule processes. We prove a useful upper bound on the size of the largest component in the barely subcritical regime. We then use this upper bound to study both sizes and surplus of the components of the bounded-size-rule processes in the critical window. In order to describe the joint evolution of sizes and surplus, we introduce the augmented multiplicative coalescent. Our main result shows that the vector of suitably scaled component sizes and surplus converges in distribution to the augmented multiplicative coalescent. In the second part of this dissertation, we study a large deviation problem related to the configuration model with a given degree distribution. We define a random walk associated with the depth-first-exploration of the random graph constructed from the configuration model. The large deviation principle of this random walk is studied using weak convergence techniques. Some large deviation bounds on the probabilities related to the sizes of the largest component are proved.

Date of publication