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

Amir Dembo, Eyal Lubetzky

Research output: Contribution to journalArticle

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
JournalElectronic Communications in Probability
Volume23
DOIs
StatePublished - Jan 1 2018

    Fingerprint

Keywords

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

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Cite this