论文标题
块模型的大偏差原理
A large deviation principle for block models
论文作者
论文摘要
我们启动了密集制度中块模型随机图的大偏差的研究。在Chatterjee-Varadhan（2011）之后，我们为被视为随机图形的密集块模型建立了一家LDP。作为结果的应用，我们研究了上尾的大偏差，以实现常规图的同态密度。我们确定了一个“对称”阶段的存在，其中该图在罕见事件上以与生成图形相同的块大小相同的块模型。在特定示例中，我们还确定了“对称破坏”制度的存在，其中条件结构不是具有兼容维度的块模型。这确定了此问题的“重进入相变”现象 - 类似于用于Erdos-Renyi随机图的现象（Chatterjee-Dey（2010），Chatterjee-Varadhan（2011））。最后，扩展了Lubetzky-Zhao（2015）的分析，我们确定了常规图的同态密度与Erdos-Renyi pipartite图的对称性和对称性破坏态度之间的精确边界。
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.
