Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015 (Q2399894)

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.