  We initiate a study of large deviations for block model random graphs in the
dense regime. Following Chatterjee-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 Erdos-Renyi random graphs (Chatterjee-Dey(2010),
Chatterjee-Varadhan(2011)). Finally, extending the analysis of
Lubetzky-Zhao(2015), we identify the precise boundary between the symmetry and
symmetry breaking regime for homomorphism densities of regular graphs and the
operator norm on Erdos-Renyi bipartite graphs.
