Large deviation for uniform graphs with given degrees

DOI10.1214/21-AAP1745MaRDI QIDQ6317278arXivFDO

Authors Souvik Dhara, Subhabrata Sen

Publication date 16 April 2019

Published in arXiv

Full work available at URL https://doi.org/10.1214/21-AAP1745

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Large deviations (60F10)

arXiv classification

math.PR

Abstract: Consider the random graph sampled uniformly from the set of all simple graphs with a given degree sequence. Under mild conditions on the degrees, we establish a Large Deviation Principle (LDP) for these random graphs, viewed as elements of the graphon space. As a corollary of our result, we obtain LDPs for functionals continuous with respect to the cut metric, and obtain an asymptotic enumeration formula for graphs with given degrees, subject to an additional constraint on the value of a continuous functional. Our assumptions on the degrees are identical to those of Chatterjee, Diaconis and Sly (2011), who derived the almost sure graphon limit for these random graphs.

This page was built for publication: Large deviation for uniform graphs with given degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317278)