Let (Formula presented.) be the Erdős–Rényi graph with connection probability (Formula presented.) 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 (Formula presented.), 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.
A large-deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph
Andreis L.;
2021-01-01
Abstract
Let (Formula presented.) be the Erdős–Rényi graph with connection probability (Formula presented.) 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 (Formula presented.), 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.File | Dimensione | Formato | |
---|---|---|---|
rsa.21007.pdf
accesso aperto
:
Publisher’s version
Dimensione
674.46 kB
Formato
Adobe PDF
|
674.46 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.