RECORD
A large-deviations principle for all the cluster sizes of a sparse Erd\H{o}s-R\'enyi graph
Probability · Submitted 7 Jan 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We derive a large-deviations principle for the empirical measure of the sizes of all the connected components of $\mathcal{G}(N,\frac 1Nt_N)$, registered according to microscopic sizes (i.e., of finite order), macroscopic ones (i.e., of order $N$), and mesoscopic ones (everything in between).
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Let $\mathcal{G}(N,\frac 1Nt_N)$ be the Erd\H{o}s-R\'enyi graph with connection probability $\frac 1Nt_N\sim t/N$ as $N\to\infty$ for a fixed $t\in(0,\infty)$. We derive a large-deviations principle for the empirical measure of the sizes of all the connected components of $\mathcal{G}(N,\frac 1Nt_N)$, 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Let $\mathcal{G}(N,\frac 1Nt_N)$ be the Erd\H{o}s-R\'enyi graph with connection probability $\frac 1Nt_N\sim t/N$ as $N\to\infty$ for a fixed $t\in(0,\infty)$. | background 0.92 | 0.11 | 0.02 | asserted 0.87 |
| s1 | We derive a large-deviations principle for the empirical measure of the sizes of all the connected components of $\mathcal{G}(N,\frac 1Nt_N)$, registered according to microscopic sizes (i.e., of finite order), macroscopic ones (i.e., of order $N$), and mesoscopic ones (everything in between). | contribution 0.79 | 0.97 | 0.85 | asserted 1.00 |
| s2 | The rate function explicitly describes the microscopic and macroscopic components and the fraction of vertices in components of mesoscopic sizes. | result 0.97 | 0.92 | 0.32 | asserted 1.00 |
| s3 | Moreover, it clearly captures the well known phase transition at $t=1$ as part of a comprehensive picture. | interpretation 0.65 | 0.78 | 0.12 | asserted 1.00 |
| s4 | The proofs rely on elementary combinatorics and on known estimates and asymptotics for the probability that subgraphs are connected. | method 1.00 | 0.59 | 0.02 | asserted 1.00 |
| s5 | 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. | contribution 0.39 | 0.89 | 0.06 | asserted 0.99 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Let $\mathcal{G}(N,\frac 1Nt_N)$ be the Erd\H{o}s-R\'enyi graph with connection probability $\frac 1Nt_N\sim t/N$ as $N\to\infty$ for a fixed $t\in(0,\infty)$. We derive a large-deviations principle for the empirical measure of the sizes of all the connected components of $\mathcal{G}(N,\frac 1Nt_N)$, 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.
Human review
How the literature uses it
3 arXiv papers cite this in 7 sentences
Papers citing it · 4 sentences without a confident label
Uses its method or tool 1 paper
-
Let $n/n ν$ and $κ_n κ$, then [equation] Loosely speaking, the idea of the proof in [ref] consists in finding a larger inhomogeneous graph with the same connection kernel $κ_n$ whose (unique) giant component has profile $≈n$.
Counting connected multitype graphs with prescribed edge counts · The inhomogeneous random graph model · 0.81
Cites it as background 2 papers
-
Starting from the seminal work of Bollobás, Janson, and Riordan [ref] , which established explicit criteria for the phase transition in multitype Erdős–Rényi graphs (introduced earlier in [ref] ), a substantial body of research has explored structural, spectral, and large-deviation properties of these models; see, for instance, [ref] .
Counting connected multitype graphs with prescribed edge counts · Introduction · 0.99
-
Other studies of the LDF in CCA include the study of the gelation transition in the product kernel using large deviation theory in the probability literature (see [ref] and references within), and a Monte Carlo algorithm for numerically determining the LDF for arbitrary collision kernels [ref] .
Exact calculation of the large deviation function for $k$-nary coalescence · Introduction · 0.93
What it cites · 1 sentence without a confident label
Cites as background 1 paper
-
Under assumptions that imply that the connection probability of the Erdős–Rényi graph $(N,p)$ satisfies $p ≫N^-1/2$, recent progress has been made on the upper tails of sub-graph counts [ref] .
Large deviations of subgraph counts for sparse Erd\H{o}s--R\'enyi graphs · Related works on LDPs for Erdős-Rényi graphs · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.