Department of Mathematics - Mathematics Colloquium - Unusually large components in some critical random graphs

In this talk we consider component sizes in random graphs. In particular, we focus on the simplest model for a random graph, namely the binomial random graph (also called the Erdős and Rényi random graph), which is obtained from the complete graph on n vertices by independently retaining each edge with probability p and deleting it with probability 1-p. This model exhibits an interesting phase transition in the size of its maximal component. By letting p=c/n, with c>0 constant, it happens that: if c<1, then the components are small (of logarithmic size), whereas when c>1 then most vertices are contained in a unique (giant) component and the remaining nodes are contained in tiny clusters (namely, of logarithmic size). Our focus is on the critical regime where c=1 (whence p=1/n). In this regime, it is known that a maximal component contains a polynomial (in n) number of vertices; our goal is to estimate the probability of seeing unusually large components in this (critical) regime. We illustrate a robust probabilistic methodology to obtain matching upper and lower bounds for the above-mentioned probability. Our argument is simple and relies on three ingredients: (1) an exploration process, which is an algorithm that we use to reveal the connected components and which reduces the study of component sizes to the problem of analyzing the trajectory of a random process; (2) a “ballot-type” estimate, concerning the probability that a random walk stays positive for a given number of steps and finishes at a certain level; (3) and a Brownian motion approximation to random walk. Time permitting, we also briefly mention how the above estimates on the probability of seeing unusually large clusters can be used to analyze a dynamical version of the random graph, where edges are resampled in continuous time.