Exceptional times of the critical dynamical Erdős-Rényi graph

Abstract

In this paper we introduce a network model which evolves in time, and study its largest connected component. We consider a process of graphs $(G_t:t\in [0,1])$, where initially we start with a critical Erdős-Rényi graph ER(n, 1/n), and then evolve forwards in time by resampling each edge independently at rate 1. We show that the size of the largest connected component that appears during the time interval $[0,1]$ is of order $n^{2/3}lo{g}^{1/3}n$ with high probability. This is in contrast to the largest component in the static critical Erdős-Rényi graph, which is of order $n^{2/3}$.

37 pages. Various corrections and improvements. This version accepted by the Annals of Applied Probability