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

Matthew Roberts, Bati Sengul

Research output: Contribution to journalArticlepeer-review

9 Citations (SciVal)


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∈[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}log^{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}.
Original languageEnglish
Pages (from-to)2275-2308
Number of pages34
JournalAnnals of Applied Probability
Issue number4
Early online date9 Aug 2018
Publication statusPublished - 31 Aug 2018


  • Dynamical random graphs
  • Erdos–Renyi
  • Giant component
  • Noise sensitivity
  • Temporal networks

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Exceptional times of the critical dynamical Erdős-Rényi graph'. Together they form a unique fingerprint.

Cite this