Kozma, Gady; Samotij, Wojciech Lower tails via relative entropy. (English) Zbl 1518.05172 Ann. Probab. 51, No. 2, 665-698 (2023). Authors’ abstract: We show that the naive mean-field approximation correctly predicts the leading term of the logarithmic lower tail probabilities for the number of copies of a given subgraph in \(G(n,p)\) and of arithmetic progressions of a given length in random subsets of the integers in the entire range of densities where the mean-field approximation is viable.Our main technical result provides sufficient conditions on the maximum degrees of a uniform hypergraph \(\mathcal{H}\) that guarantee that the logarithmic lower tail probabilities for the number of edges, induced by a binomial random subset of the vertices of \(\mathcal{H}\), can be well approximated by considering only product distributions. This may be interpreted as a weak, probabilistic version of the hypergraph container lemma that is applicable to all sparser-than-average (and not only independent) sets. Reviewer: Oleg K. Zakusilo (Kyïv) Cited in 2 Documents MSC: 05C80 Random graphs (graph-theoretic aspects) 60F10 Large deviations Keywords:lower tail; random graph; subgraph counts × Cite Format Result Cite Review PDF Full Text: DOI arXiv References: [1] Augeri, F. (2020). Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs. Ann. Probab. 48 2404-2448. · Zbl 1456.60063 · doi:10.1214/20-AOP1427 [2] AVEZ, A. (1976). Harmonic functions on groups. In Differential Geometry and Relativity. Mathematical Phys. and Appl. Math. 3 27-32. Reidel, Dordrecht. · Zbl 0345.31004 [3] BALOGH, J., MORRIS, R. and SAMOTIJ, W. (2015). Independent sets in hypergraphs. J. Amer. Math. Soc. 28 669-709. · Zbl 1310.05154 · doi:10.1090/S0894-0347-2014-00816-X [4] BALOGH, J. and SAMOTIJ, W. (2020). An efficient container lemma. Discrete Anal. Paper No. 17, 56. · Zbl 1475.05124 · doi:10.19086/da [5] BASAK, A. and BASU, R. (2023). Upper tail large deviations of regular subgraph counts in Erdős-Rényi graphs in the full localized regime. Comm. Pure Appl. Math. 76 3-72. Available at arXiv:1912.11410. · Zbl 1530.05189 · doi:10.1002/cpa.22036 [6] Bhattacharya, B. B., Ganguly, S., Lubetzky, E. and Zhao, Y. (2017). Upper tails and independence polynomials in random graphs. Adv. Math. 319 313-347. · Zbl 1370.05099 · doi:10.1016/j.aim.2017.08.003 [7] CHATTERJEE, S. (2012). The missing log in large deviations for triangle counts. Random Structures Algorithms 40 437-451. · Zbl 1246.05140 · doi:10.1002/rsa.20381 [8] Chatterjee, S. and Dembo, A. (2016). Nonlinear large deviations. Adv. Math. 299 396-450. · Zbl 1356.60045 · doi:10.1016/j.aim.2016.05.017 [9] Chatterjee, S. and Varadhan, S. R. S. (2011). The large deviation principle for the Erdős-Rényi random graph. European J. Combin. 32 1000-1017. · Zbl 1230.05259 · doi:10.1016/j.ejc.2011.03.014 [10] CONLON, D. and GOWERS, W. T. (2016). Combinatorial theorems in sparse random sets. Ann. of Math. (2) 184 367-454. · Zbl 1351.05204 · doi:10.4007/annals.2016.184.2.2 [11] Cook, N. and Dembo, A. (2020). Large deviations of subgraph counts for sparse Erdős-Rényi graphs. Adv. Math. 373 107289, 53. · Zbl 1473.60058 · doi:10.1016/j.aim.2020.107289 [12] COOK, N., DEMBO, A. and PHAM, H. T. Regularity method and large deviation principles for the Erdős-Rényi hypergraph. arXiv:2102.09100 [math.PR]. [13] Cover, T. M. and Thomas, J. A. (2006). Elements of Information Theory, 2nd ed. Wiley Interscience, Hoboken, NJ. · Zbl 1140.94001 [14] CSISZÁR, I. (1984). Sanov property, generalized \(I\)-projection and a conditional limit theorem. Ann. Probab. 12 768-793. · Zbl 0544.60011 [15] Csiszár, I. and Körner, J. (2011). Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 1256.94002 · doi:10.1017/CBO9780511921889 [16] DEMARCO, B. and KAHN, J. (2012). Upper tails for triangles. Random Structures Algorithms 40 452-459. · Zbl 1246.05142 · doi:10.1002/rsa.20382 [17] Eldan, R. (2018). Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations. Geom. Funct. Anal. 28 1548-1596. · Zbl 1428.60045 · doi:10.1007/s00039-018-0461-z [18] ERDŐS, P., KLEITMAN, D. J. and ROTHSCHILD, B. L. (1976). Asymptotic enumeration of \[{K_n}\]-free graphs. In Colloquio Internazionale Sulle Teorie Combinatorie (Rome, 1973), Tomo II. Atti dei Convegni Lincei 17 19-27. Accad. Naz. Lincei, Rome. · Zbl 0358.05027 [19] Frieze, A. and Kannan, R. (1999). Quick approximation to matrices and applications. Combinatorica 19 175-220. · Zbl 0933.68061 · doi:10.1007/s004930050052 [20] HAREL, M., MOUSSET, F. and SAMOTIJ, W. (2022). Upper tails via high moments and entropic stability. Duke Math. J. 171 2089-2192. · Zbl 1500.60002 · doi:10.1215/00127094-2021-0067 [21] JAIN, V., RISTESKI, A. and KOEHLER, F. (2019). Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: A unified perspective. In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 1226-1236. ACM, New York. · Zbl 1434.68338 · doi:10.1145/3313276.3316299 [22] JANSON, S. (1990). Poisson approximation for large deviations. Random Structures Algorithms 1 221-229. · Zbl 0747.05079 · doi:10.1002/rsa.3240010209 [23] JANSON, S., ŁUCZAK, T. and RUCIŃSKI, A. (1990). An exponential bound for the probability of nonexistence of a specified subgraph in a random graph. In Random Graphs ’87 (Poznań, 1987) 73-87. Wiley, Chichester. · Zbl 0733.05073 [24] KOHAYAKAWA, Y., ŁUCZAK, T. and RÖDL, V. (1997). On \[{K^4}\]-free subgraphs of random graphs. Combinatorica 17 173-213. · Zbl 0889.05068 · doi:10.1007/BF01200906 [25] KOZMA, G., MEYEROVITCH, T., PELED, R. and SAMOTIJ, W. What does a typical metric space look like? Ann. Inst. Henri Poincaré Probab. Stat. To appear. Available at arXiv:2104.01689. · Zbl 1542.60012 · doi:10.1214/22-AIHP1262 [26] Lubetzky, E. and Zhao, Y. (2015). On replica symmetry of large deviations in random graphs. Random Structures Algorithms 47 109-146. · Zbl 1348.05195 · doi:10.1002/rsa.20536 [27] Lubetzky, E. and Zhao, Y. (2017). On the variational problem for upper tails in sparse random graphs. Random Structures Algorithms 50 420-436. · Zbl 1364.05063 · doi:10.1002/rsa.20658 [28] ŁUCZAK, T. (2000). On triangle-free random graphs. Random Structures Algorithms 16 260-276. · Zbl 0947.05071 · doi:10.1002/(SICI)1098-2418(200005)16:3<260::AID-RSA3>3.3.CO;2-H [29] MANURANGSI, P. and RAGHAVENDRA, P. (2017). A birthday repetition theorem and complexity of approximating dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming. LIPIcs. Leibniz Int. Proc. Inform. 80 Art. No. 78, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern. · Zbl 1441.68048 [30] MONTANARI, A. (2008). Estimating random variables from random sparse observations. Eur. Trans. Telecommun. 19 385-403. [31] RAGHAVENDRA, P. and TAN, N. (2012). Approximating CSPs with global cardinality constraints using SDP hierarchies. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms 373-384. ACM, New York. · Zbl 1422.68312 [32] SAXTON, D. and THOMASON, A. (2015). Hypergraph containers. Invent. Math. 201 925-992. · Zbl 1320.05085 · doi:10.1007/s00222-014-0562-8 [33] SCHACHT, M. (2016). Extremal results for random discrete structures. Ann. of Math. (2) 184 333-365. · Zbl 1351.05207 · doi:10.4007/annals.2016.184.2.1 [34] ZHAO, Y. (2017). On the lower tail variational problem for random graphs. Combin. Probab. Comput. 26 301-320 · Zbl 1371.05274 · doi:10.1017/S0963548316000262 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.