Moderate deviations of triangle counts – the lower tail
EUROCOMB’23
28–35
F. Augeri. Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdős-Rényi graphs. ArXiv:, (1810.01558), 2018.
A.D. Barbour, M. Karoński, and A. Ruciński. A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B, 47(2):125-145, 1989.
https://doi.org/10.1016/0095-8956(89)90014-2
S. Chatterjee. An introduction to large deviations for random graphs. Bull. Amer. Math. Soc., 53(4):617-642, 2016.
https://doi.org/10.1090/bull/1539
S Chatterjee and S.R.S. Varadhan. The large deviation principle for the Erdős-Rényi random graph. European J. Combin., 32(7):1000-1017, 2011.
https://doi.org/10.1016/j.ejc.2011.03.014
N. Cook and A. Dembo. Large deviations of subgraph counts for sparse Erdős-Rényi graphs. Adv. Math., 343, 2020.
https://doi.org/10.1016/j.aim.2020.107289
L. G. de Oliveira. Moderate deviations of triangle counts in sparse random graphs. Doctoral thesis, https://www.maxwell.vrac.puc-rio.br/61161/61161.PDF.
H. Döring and P. Eichelsbacher. Moderate deviations in a random graph and for the spectrum of bernoulli random matrices. Electron. J. Probab., 14:2636-2656, 2009.
https://doi.org/10.1214/EJP.v14-723
H. Döring and P. Eichelsbacher. Moderate deviations via cumulants. J. Theoret. Probab., 2:360-385, 2013.
https://doi.org/10.1007/s10959-012-0437-0
R. Eldan. Gaussian-width gradient complexity, reverse log-sobolev inequalities and nonlinear large deviations. Geom. Funct. Anal., 28:1548-1596, 2018.
https://doi.org/10.1007/s00039-018-0461-z
V. Féray, P.-L. Méliot, and A. Nikeghbali. Mod-φ convergence: Normality zones and precise deviations. Springer Briefs in Probability and Mathematical Statistics, 2016.
https://doi.org/10.1007/978-3-319-46822-8
C. Goldschmidt, S. Griffiths, and A. Scott. Moderate deviations of subgraph counts in the Erdős-Rényi random graphs g(n, m) and g(n, p). Trans. Amer. Math. Soc., 343:5517-5585, 2020.
https://doi.org/10.1090/tran/8117
M. Harel, F. Mousset, and W. Samotij. Upper tails via high moments and entropic stability. ArXiv:, (1904.08212), 2019.
S. Janso. Orthogonal decompositions and functional limit theorems for random graph statistics. Mem. Amer. Math. Soc., (534), 1994.
https://doi.org/10.1090/memo/0534
S. Janson. A functional limit theorem for random graphs with applications to subgraph count statistics. Random Structures Algorithms, 1:15-37, 1990.
https://doi.org/10.1002/rsa.3240010103
S. Janson and K. Nowicki. The asymptotic distributions of generalized U -statistics with applications to random graphs. Probab. Theory Related Fields, 90(3):341-375, 1991.
https://doi.org/10.1007/BF01193750
S. Janson and A. Ruciński. The infamous upper tail. Random Structures Algorithms, 20(3):317-342, 2002.
https://doi.org/10.1002/rsa.10031
K. Krokowski, A. Reichenbachs, and C. Thäle. Discrete Malliavin-Stein method: Berry-Esseen bounds for random graphs and percolation. Ann. Probab., 47(2):1071-1109, 2017.
https://doi.org/10.1214/15-AOP1081
E. Lubetzky and Y. Zhao. On the variational problem for upper tails in sparse random graphs. Random Structures Algorithms, 50:420-436, 2017.
https://doi.org/10.1002/rsa.20658
J. Neeman, C. Radin, and L. Sadun. Moderate deviations in cycle count. ArXiv:, (2101.08249), 2021.
G. Reinert and A. Röllin. Random subgraph counts and U -statistics: multivariate normal approximation via exchangeable pairs and embedding. J. Appl. Probab., 47(2):378-393, 2010.
https://doi.org/10.1239/jap/1276784898
A. Röllin. Kolmogorov bounds for the Normal approximation of the number of triangles in the Erdős-Rényi random graph. ArXiv:, 1704.00410, 2017.
A. Ruciński. When are small subgraphs of a random graph normally distributed? Probab. Theory Related Fields, 78(1):1-10, 1988.
https://doi.org/10.1007/BF00718031
V. Vu. A large deviation result on the number of small subgraphs of a random graph. Combin. Probab. Comput., 10(1):79-94, 2001.
https://doi.org/10.1017/S0963548300004545
Y. Zhao. On the lower tail variational problem for random graphs. Combin. Probab. Comput., 26(2):301-320, 2017.
https://doi.org/10.1017/S0963548316000262
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 José D. Alvarado, Gabriel D. Do Couto, Simon Griffiths