Large deviations of empirical neighborhood distribution in sparse random graphs

DOI10.1007/s00440-014-0590-8zbMath1327.60067arXiv1308.5725OpenAlexW2131348552MaRDI QIDQ748442

Pietro Caputo, Charles Bordenave

Publication date: 29 October 2015

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.5725

zbMATH Keywords

entropyrandom graphslarge deviationslocal convergenceconfiguration modelGalton-Watson treesempirical neighborhood distributionunimodular measure

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Large deviations (60F10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items

Rare event asymptotics for exploration processes for random graphs, Limits of discrete distributions and Gibbs measures on random graphs, Proof of the satisfiability conjecture for large \(k\), A large-deviations principle for all the components in a sparse inhomogeneous random graph, Harnessing the Bethe free energy, A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph, Bernoulli random matrices, Rare events in random matrix theory, Scale-free graphs with many edges, Interacting diffusions on sparse graphs: hydrodynamics from local weak limits, Structure of eigenvectors of random regular digraphs, Ising critical exponents on random trees and graphs, Local convergence of random graph colorings, From Boltzmann to random matrices and beyond, The condensation phase transition in random graph coloring, Spectral edge in sparse random graphs: upper and lower tail large deviations, Central limit theorem for statistics of subcritical configuration models, Distances and large deviations in the spatial preferential attachment model, Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics, Graphs with prescribed local neighborhoods of their universal coverings, Typicality and entropy of processes on infinite trees, Large deviations for the largest eigenvalue of Gaussian networks with constant average degree, Optimal low-degree hardness of maximum independent set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• A large deviation principle for Wigner matrices without Gaussian tails
• Large deviation principles for empirical measures of colored random graphs
• The large deviation principle for the Erdős-Rényi random graph
• On the limit of large girth graph sequences
• On large deviation properties of Erdős-Rényi random graphs
• Properties of atypical graphs from negative complexities
• Limits of dense graph sequences
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Large deviations techniques and applications.
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Some large deviation results for sparse random graphs
• Periodicity and circle packings of the hyperbolic plane
• Recurrence of distributional limits of finite planar graphs
• Bins and balls: Large deviations of the empirical occupancy process
• Processes on unimodular random networks
• Stochastic processes in random graphs
• Large deviations of Markov chains indexed by random trees
• Information, Physics, and Computation
• A critical point for random graphs with a given degree sequence
• Sparse graphs: Metrics and random models
• Unimodular random trees
• Large‐deviations/thermodynamic approach to percolation on the complete graph
• On Recent Theorems Concerning the Supercritical Galton-Watson Process
• Extension of a Result of Seneta for the Super-Critical Galton-Watson Process
• Probability