Sparse Random Graphs: Interplay of Local and Global Structure
11Mihyun Kang (Technische Universität Graz, Austria)
https://simons.berkeley.edu/node/22595
Graph Limits, Nonparametric Models, and Estimation
In the theory of random graphs the giant component has remained a guiding theme since the seminal paper of Erdos and Renyi. It has long been observed that the emergence of the giant component is analogous to the survival of a Galton-Watson branching process. This analogy crystallises the interplay between the local and the global structure of a sparse random graph. In fact, the notion that the Galton-Watson tree is the limiting object of the 'local structure' of the Erdos and Renyi random graph can be formalised nicely in the language of 'local weak convergence' introduced by Benjamini and Schramm and by Aldous and Steele. The local structure and local weak limits found their applications also in message passing algorithms, such as Belief Propagation and Warning Propagation, to mention a few.
Turning our attention to a random graph with a topological constraint (e.g., a random planar graph) where the independence of edges is lost, we will show that the planarity constraint affects the global component structure substantially, which in turn affects the local structure.