Repository: Freie Universität Berlin, Math Department

A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph

Andreis, Luisa and König, Wolfgang and Patterson, Robert I.A. (2021) A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph. Random Structures and Algorithms . pp. 1-32.

Full text not available from this repository.

Official URL:


Abstract Let urn:x-wiley:rsa:media:rsa21007:rsa21007-math-0001 be the Erdős–Rényi graph with connection probability urn:x-wiley:rsa:media:rsa21007:rsa21007-math-0002 as N → ∞ for a fixed t ∈ (0, ∞). We derive a large‐deviations principle for the empirical measure of the sizes of all the connected components of urn:x-wiley:rsa:media:rsa21007:rsa21007-math-0003, registered according to microscopic sizes (i.e., of finite order), macroscopic ones (i.e., of order N), and mesoscopic ones (everything in between). The rate function explicitly describes the microscopic and macroscopic components and the fraction of vertices in components of mesoscopic sizes. Moreover, it clearly captures the well known phase transition at t = 1 as part of a comprehensive picture. The proofs rely on elementary combinatorics and on known estimates and asymptotics for the probability that subgraphs are connected. We also draw conclusions for the strongly related model of the multiplicative coalescent, the Marcus–Lushnikov coagulation model with monodisperse initial condition, and its gelation phase transition.

Item Type:Article
Subjects:Mathematical and Computer Sciences > Mathematics > Applied Mathematics
Divisions:Department of Mathematics and Computer Science > Institute of Mathematics
ID Code:2568
Deposited By: Monika Drueck
Deposited On:29 Apr 2021 10:25
Last Modified:29 Apr 2021 10:25

Repository Staff Only: item control page