Moderate deviations of triangle counts – the lower tail

EUROCOMB’23

José D. Alvarado Gabriel D. Do Couto Simon Griffiths

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-004

PDF
Abstract
Two recent papers \cite{GGS} and \cite{NRS22} study the lower tail of triangle count deviations in random graphs $G(n,m)$ with positive density $t:=m/\binom{n}{2}\in (0,1)$. Let us write $D_{\triangle}(G)$ for the deviation of the triangle count from its mean. Results of \cite{GGS} and \cite{NRS22} determine the order of magnitude of the log probability $\log(\mathbb{P}(D_{\triangle}(G(n,m)) \, < \, - \tau\binom{n}{3}))$ for the ranges $n^{-3/2}\ll \tau\ll n^{-1}$ and $n^{-3/4}\ll\tau\ll 1$ respectively. Furthermore, in \cite{NRS22} it is proved that the log probability is at least $\Omega(\tau^2 n^{3})$ in the ``missing‘‘ range $n^{-1}\ll \tau\ll n^{-3/4}$, and they conjectured that this result gives the correct order of magnitude. Our main contribution is to prove this conjecture.

Pages:
28–35
References

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

Metrics

0

Views

0

PDF views

Creative Commons License

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

PDF