A large deviation principle for the Erdős–Rényi uniform random graph

Amir Dembo, Eyal Lubetzky

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Article number79
Number of pages13
JournalElectronic Communications in Probability
Volume23
DOIs
StatePublished - 2018

Keywords

  • Constrained random graphs
  • Erdős-Rényi graphs
  • Large deviations

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'A large deviation principle for the Erdős–Rényi uniform random graph'. Together they form a unique fingerprint.

Cite this