{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T19:22:45Z","timestamp":1773688965784,"version":"3.50.1"},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T00:00:00Z","timestamp":1751241600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We initiate a study of large deviations for block model random graphs in the dense regime. Following [14], 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 \u2018symmetric\u2019 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 \u2018symmetry breaking\u2019 regime, where the conditional structure is not a block model with compatible dimensions. This identifies a \u2018reentrant phase transition\u2019 phenomenon for this problem \u2013 analogous to one established for Erd\u0151s\u2013R\u00e9nyi random graphs [13, 14]. Finally, extending the analysis of [34], we identify the precise boundary between the symmetry and symmetry breaking regimes for homomorphism densities of regular graphs and the operator norm on Erd\u0151s\u2013R\u00e9nyi bipartite graphs.<\/jats:p>","DOI":"10.1017\/s0963548325000008","type":"journal-article","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T03:16:36Z","timestamp":1751253396000},"page":"680-753","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["A large deviation principle for block models"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5653-0498","authenticated-orcid":false,"given":"Christian","family":"Borgs","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4020-8618","authenticated-orcid":false,"given":"Jennifer","family":"Chayes","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Gaudio","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Management Sciences, Northwestern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8281-8161","authenticated-orcid":false,"given":"Samantha","family":"Petti","sequence":"additional","affiliation":[{"name":"Tufts University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhabrata","family":"Sen","sequence":"additional","affiliation":[{"name":"Department of Statistics, Harvard University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2025,6,30]]},"reference":[{"key":"S0963548325000008_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1427"},{"key":"S0963548325000008_ref25","first-page":"1","article-title":"Upper tails via high moments and entropic stability","volume":"1","author":"Harel","year":"2022","journal-title":"Duke Math. J."},{"key":"S0963548325000008_ref26","volume-title":"New York Journal of Mathematics Monographs","volume":"4","author":"Janson","year":"2013"},{"key":"S0963548325000008_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-022-01181-1"},{"key":"S0963548325000008_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/18M1230852"},{"key":"S0963548325000008_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20440"},{"key":"S0963548325000008_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107289"},{"key":"S0963548325000008_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2016.05.017"},{"key":"S0963548325000008_ref13","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP542"},{"key":"S0963548325000008_ref32","volume-title":"Large Networks and Graph Limits","volume":"60","author":"Lov\u00e1sz","year":"2012"},{"key":"S0963548325000008_ref37","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1017\/S0963548300004545","article-title":"A large deviation result on the number of small subgraphs of a random graph","volume":"10","author":"Van","year":"2001","journal-title":"Comb. Prob. Comput."},{"key":"S0963548325000008_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.08.003"},{"key":"S0963548325000008_ref2","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOP1352"},{"key":"S0963548325000008_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03311-7"},{"key":"S0963548325000008_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"S0963548325000008_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10031"},{"key":"S0963548325000008_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21011"},{"key":"S0963548325000008_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20382"},{"key":"S0963548325000008_ref11","first-page":"xi","volume-title":"Lecture Notes in Math.","volume":"2197","author":"Chatterjee","year":"2017"},{"key":"S0963548325000008_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.014"},{"key":"S0963548325000008_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-018-0461-z"},{"key":"S0963548325000008_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20381"},{"key":"S0963548325000008_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0038-3"},{"key":"S0963548325000008_ref31","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20975"},{"key":"S0963548325000008_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771528"},{"key":"S0963548325000008_ref21","doi-asserted-by":"publisher","DOI":"10.1017\/9781108591034"},{"key":"S0963548325000008_ref18","doi-asserted-by":"publisher","DOI":"10.1214\/18-ECP181"},{"key":"S0963548325000008_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.22036"},{"key":"S0963548325000008_ref20","doi-asserted-by":"publisher","DOI":"10.1214\/21-AAP1745"},{"key":"S0963548325000008_ref9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.1.2"},{"key":"S0963548325000008_ref23","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989534"},{"key":"S0963548325000008_ref24","unstructured":"[24] Greb\u00edk, J. and Pikhurko, O. (2021) Large deviation principles for block and step graphon random graph models. arXiv preprint arXiv: 2101.07025."},{"key":"S0963548325000008_ref34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20536"},{"key":"S0963548325000008_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"S0963548325000008_ref6","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rny022"},{"key":"S0963548325000008_ref36","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20859"},{"key":"S0963548325000008_ref30","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10113"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548325000008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,16]],"date-time":"2025-09-16T00:12:18Z","timestamp":1757981538000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548325000008\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,30]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["S0963548325000008"],"URL":"https:\/\/doi.org\/10.1017\/s0963548325000008","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,30]]},"assertion":[{"value":"\u00a9 The Author(s), 2025. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}