Abstract
Starting with the large deviation principle (LDP) for the Erdős–Rényi binomial random graph G(n, p) (edge indicators are i.i.d.), due to Chatterjee and Varadhan (2011), we derive the LDP for the uniform random graph G(n, m) (the uniform distribution over graphs with n vertices and m edges), at suitable m = mn. Applying the latter LDP we find that tail decays for subgraph counts in G(n, mn) are controlled by variational problems, which up to a constant shift, coincide with those studied by Kenyon et al. and Radin et al. in the context of constrained random graphs, e.g., the edge/triangle model.
Original language | English (US) |
---|---|
Article number | 79 |
Number of pages | 13 |
Journal | Electronic Communications in Probability |
Volume | 23 |
DOIs | |
State | Published - 2018 |
Keywords
- Constrained random graphs
- Erdős-Rényi graphs
- Large deviations
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty