Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
This book is a set of lecture notes for a summer school on the topic of large deviations in random graphs. Large deviation theory is, crudely speaking, getting good estimates of the probabilities of rare events occurring and conditional probabilities of other events of interest given that some rare event has occurred. Until recently, for example, questions like estimating accurately the probability that the number \(T_{n,p}\) of triangles in an Erdős-Rényi random graph \(G(n,p)\) is at least \((1+\varepsilon)\mathbb{E}(T_{n,p})\) (for \(\varepsilon>0\)) had not been answered very well. However, the work of the author and Varadhan, and subsequently other authors, using both probabilistic large deviations ideas and some interesting recent developments in combinatorics -- including the theory of graph limits/graphons -- have recently led to exciting progress. This book is a summary of highlights of that story, which has worked hard to be reasonably self-contained. After an introductory overview and a chapter on (in one sense standard) probabilistic and functional-analytic background, there is a chapter giving a self-contained introduction to the parts of the theory of graph limits relevant to the book. Chapter 4 discusses general large deviations ideas, centering on the rate function. The heart of the book, in some sense, is Chapters 5 and 6 which establish large deviations principles for dense Erdős-Rényi random graphs and applications to various graph parameters: some interesting ``phase transition phenomena emerge. In Chapter 7, the results are extended to so-called exponential random graph models, which are arguably more realistic in various applied contexts. Chapter 8 deals with sparse graphs, where the theory is somewhat less well developed but interesting results can still be proven by different approaches.
- Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
- Ensemble equivalence for dense graphs
- The role of topology in large deviations
- Anti-concentration for subgraph counts in random graphs
- Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
- The large deviation principle for interacting dynamical systems on random graphs
- Rare event asymptotics for exploration processes for random graphs
- Upper tails via high moments and entropic stability
- Large deviation for uniform graphs with given degrees
- Replica symmetry in upper tails of mean-field hypergraphs
- The structure of low-complexity Gibbs measures on product spaces
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Approximating the cumulant generating function of triangles in the Erdös-Rényi random graph
- Stochastic processes in random graphs
- An introduction to large deviations for random graphs
- On replica symmetry of large deviations in random graphs
- Random Simplicial Complexes: Models and Phenomena
- Random obstacle problems. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- The number of triangles in random intersection graphs
- A numerical method for a nonlocal diffusion equation with additive noise
- The large deviation principle for inhomogeneous Erdős-Rényi random graphs
- A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
- Breaking of ensemble equivalence for dense random graphs under a single constraint
- The large deviation principle for the Erdős-Rényi random graph
- Typical structure of sparse exponential random graph models
- Limit theorems for exponential random graphs
- Optimal graphons in the edge-2star model
- A large deviation principle for block models
- Universality in prelimiting tail behavior for regular subgraph counts in the Poisson regime
- Continuum graph dynamics via population dynamics: well-posedness, duality and equilibria
- Statistics for the triangle density in ERGM and its mean-field approximation
- Higher-Order Accurate Two-Sample Network Inference and Network Hashing
- Graphon-valued processes with vertex-level fluctuations
- On the chromatic number of random triangle-free graphs
- Urn modeling of random graphs across granularity scales: a framework for origin-destination human mobility networks
- Large deviations of empirical neighborhood distribution in sparse random graphs
- The importance sampling technique for understanding rare events in Erdős-Rényi random graphs
This page was built for publication: Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2399894)
