Abstract
We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee and Varadhan (2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric'' phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking'' regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition'' phenomenon for this problem---analogous to one established for Erdős–Rényi random graphs (Chatterjee and Dey (2010), Charrerjee and Varadhan (2011)). Finally, extending the analysis of Lubetzky and Zhao (2015), we identify the precise boundary between the symmetry and symmetry breaking regimes for homomorphism densities of regular graphs and the operator norm on Erdős–Rényi bipartite graphs.
Joint work with Christian Borgs, Jennifer Chayes, Subhabrata Sen, and Samantha Petti