{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T14:52:10Z","timestamp":1772376730155,"version":"3.50.1"},"reference-count":45,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2017,3]]},"abstract":"<jats:p>We study the lower tail large deviation problem for subgraph counts in a random graph. Let<jats:italic>X<\/jats:italic><jats:sub><jats:italic>H<\/jats:italic><\/jats:sub>denote the number of copies of<jats:italic>H<\/jats:italic>in an Erd\u0151s\u2013R\u00e9nyi random graph<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000262_inline1\"\/><jats:tex-math>$\\mathcal{G}(n,p)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We are interested in estimating the lower tail probability<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548316000262_inline2\"\/><jats:tex-math>$\\mathbb{P}(X_H \\le (1-\\delta) \\mathbb{E} X_H)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>for fixed 0 &lt; \u03b4 &lt; 1.<\/jats:p><jats:p>Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for<jats:italic>p<\/jats:italic>\u2265<jats:italic>n<\/jats:italic><jats:sup>\u2212\u03b1<jats:sub><jats:italic>H<\/jats:italic><\/jats:sub><\/jats:sup>(and conjecturally for a larger range of<jats:italic>p<\/jats:italic>). We study this variational problem and provide a partial characterization of the so-called \u2018replica symmetric\u2019 phase. Informally, our main result says that for every<jats:italic>H<\/jats:italic>, and 0 &lt; \u03b4 &lt; \u03b4<jats:sub><jats:italic>H<\/jats:italic><\/jats:sub>for some \u03b4<jats:sub><jats:italic>H<\/jats:italic><\/jats:sub>&gt; 0, as<jats:italic>p<\/jats:italic>\u2192 0 slowly, the main contribution to the lower tail probability comes from Erd\u0151s\u2013R\u00e9nyi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite<jats:italic>H<\/jats:italic>and \u03b4 close to 1.<\/jats:p>","DOI":"10.1017\/s0963548316000262","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T10:25:31Z","timestamp":1471343131000},"page":"301-320","source":"Crossref","is-referenced-by-count":16,"title":["On the Lower Tail Variational Problem for Random Graphs"],"prefix":"10.1017","volume":"26","author":[{"given":"YUFEI","family":"ZHAO","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"S0963548316000262_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-007-0599-6"},{"key":"S0963548316000262_ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-1151-3"},{"key":"S0963548316000262_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOS1155"},{"key":"S0963548316000262_ref30","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2010-05189-X"},{"key":"S0963548316000262_ref43","doi-asserted-by":"crossref","unstructured":"Yin M. and Zhu L. Asymptotics for sparse exponential random graph models. Braz. J. Prob. Stat., to appear","DOI":"10.1214\/16-BJPS319"},{"key":"S0963548316000262_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0005-1"},{"key":"S0963548316000262_ref3","unstructured":"Aristoff D. and Zhu L. On the phase transition curve in a directed exponential random graph model. arXiv:1404.6514"},{"key":"S0963548316000262_ref12","doi-asserted-by":"crossref","unstructured":"Conlon D. , Fox J. and Sudakov B. (2015) Recent developments in graph Ramsey theory. In Surveys in Combinatorics, pp. 49\u2013118.","DOI":"10.1017\/CBO9781316106853.003"},{"key":"S0963548316000262_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.014"},{"key":"S0963548316000262_ref45","unstructured":"Zhu L. Asymptotic structure of constrained exponential random graph models. arXiv:1408.1536"},{"key":"S0963548316000262_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200009918"},{"key":"S0963548316000262_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0097-0"},{"key":"S0963548316000262_ref24","unstructured":"Li J. L. X. and Szegedy B. On the logarithmic calculus and Sidorenko's conjecture. Combinatorica, to appear."},{"key":"S0963548316000262_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548316000262_ref38","unstructured":"Szegedy B. An information theoretic approach to Sidorenko's conjecture. arXiv:1406.6738"},{"key":"S0963548316000262_ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02988307"},{"key":"S0963548316000262_ref39","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-39.2.246"},{"key":"S0963548316000262_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0044-0"},{"key":"S0963548316000262_ref31","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/47\/17\/175001"},{"key":"S0963548316000262_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20382"},{"key":"S0963548316000262_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6487"},{"key":"S0963548316000262_ref14","doi-asserted-by":"publisher","DOI":"10.2307\/2310464"},{"key":"S0963548316000262_ref23","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1525\/9780520319875-014","volume-title":"Mathematical Optimization Techniques","author":"Kruskal","year":"1963"},{"key":"S0963548316000262_ref28","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20536"},{"key":"S0963548316000262_ref35","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009085"},{"key":"S0963548316000262_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"S0963548316000262_ref19","first-page":"187","volume-title":"Theory of Graphs: Proc. Colloq. Tihany 1966","author":"Katona","year":"1968"},{"key":"S0963548316000262_ref21","unstructured":"Kenyon R. and Yin M. On the asymptotics of constrained exponential random graphs. arXiv:1406.3662"},{"key":"S0963548316000262_ref42","doi-asserted-by":"crossref","unstructured":"Yin M. , Rinaldo A. and Fadnavis S. Asymptotic quantization of exponential random graphs. Ann. Appl. Probab., to appear","DOI":"10.1214\/16-AAP1175"},{"key":"S0963548316000262_ref32","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/46\/30\/305002"},{"key":"S0963548316000262_ref6","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.176.1.2"},{"key":"S0963548316000262_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"S0963548316000262_ref25","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"S0963548316000262_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.spa.2015.06.004"},{"key":"S0963548316000262_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2015.12.008"},{"key":"S0963548316000262_ref29","doi-asserted-by":"crossref","unstructured":"Lubetzky E. and Zhao Y. On the variational problem for upper tails in sparse random graphs. Random Struct. Alg., to appear","DOI":"10.1002\/rsa.20658"},{"key":"S0963548316000262_ref34","doi-asserted-by":"publisher","DOI":"10.1214\/12-AAP907"},{"key":"S0963548316000262_ref18","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20590"},{"key":"S0963548316000262_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-013-0874-x"},{"key":"S0963548316000262_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"S0963548316000262_ref36","doi-asserted-by":"crossref","unstructured":"Reiher C. The clique density theorem. Ann. Math., to appear","DOI":"10.4007\/annals.2016.184.3.1"},{"key":"S0963548316000262_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20381"},{"key":"S0963548316000262_ref20","unstructured":"Kenyon R. , Radin C. , Ren K. and Sadun L. Multipodal structure and phase transitions in large constrained graphs. arXiv:1405.0599"},{"key":"S0963548316000262_ref41","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v20-4010"},{"key":"S0963548316000262_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2016.05.017"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548316000262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T02:01:29Z","timestamp":1657072889000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548316000262\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["S0963548316000262"],"URL":"https:\/\/doi.org\/10.1017\/s0963548316000262","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,16]]}}}