A large-deviations principle for all the components in a sparse inhomogeneous random graph (Q6045832): Difference between revisions

The paper under review is about a model of random graphs introduced in [\textit{B. Bollobás} et al., Random Struct. Algorithms 31, No. 1, 3--122 (2007; Zbl 1123.05083)]. Crudely speaking, each vertex is assigned a type, and the edges arise, conditionally on the types of the two endpoints, independently with probability depending on the types of the two endpoints. Bollobás, Janson, and Riordan [loc. cit.] studied, amongst other things, the phase transition in these graphs, i.e. the emergence of a component containing a large proportion of the vertices. The paper under review revisits and extends these results, putting more explicit emphasis on large deviation principles. In particular, they give a large deviations principle which keeps track of all components (whether large or small) and of the vertex types within the clusters. The approach allows additional information to be brought out. The authors allow the types to take values in a compact metric space, though the case of finite types (presented in Section 3 of the paper) is a nice introduction to the more general ideas. A building block is a result on the probability that a subgraph on a strictly positive proportion of the vertices (macroscopic) is connected which is of independent interest. Links with a coagulation process are explored and various limit laws are derived from the LDP, including recovering the result of Bollobás, Janson, and Riordan [loc. cit.] on when there is a phase transition.