×
Griffiths, Simon; Koch, Christoph; Secco, Matheus

Deviation probabilities for arithmetic progressions and irregular discrete structures. (English) Zbl 07790296

Electron. J. Probab. 28, Paper No. 172, 31 p. (2023).
Summary: Let the random variable \(X : = e(\mathcal{H} [B])\) count the number of edges of a hypergraph \(\mathcal{H}\) induced by a random \(m\)-element subset \(B\) of its vertex set. Focussing on the case that the degrees of vertices in \(\mathcal{H}\) vary significantly we prove bounds on the probability that \(X\) is far from its mean. It is possible to apply these results to discrete structures such as the set of \(k\)-term arithmetic progressions in \(\{1, \ldots, N \}\). Furthermore, our main theorem allows us to deduce results for the case \(B \sim B_p\) is generated by including each vertex independently with probability \(p\). In this setting our result on arithmetic progressions extends a result of B. B. Bhattacharya et al. [Int. Math. Res. Not. 2020, No. 1, 167–213 (2020; Zbl 1478.11012)]. We also mention connections to related central limit theorems.

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
05C65 Hypergraphs
11B25 Arithmetic progressions
60G42 Martingales with discrete parameter
60F10 Large deviations

Keywords:

arithmetic progressions; hypergraphs; martingales; moderate deviations; random processes

Citations:

Zbl 1478.11012
Cite Review PDF
Full Text: DOI arXiv

References:

[1] K. Azuma, Weighted sums of certain dependent random variables, Tohoku Math. J. 3 (1967), 357-367. MathSciNet: MR0221571 · Zbl 0178.21103
[2] R.R. Bahadur, Some approximations to the binomial distributions function, Ann. Math. Statist. 31 (1960), no. 1, 43-54. MathSciNet: MR0120675 · Zbl 0092.35203
[3] Y. Barhoumi-Andréani, C. Koch, and H. Liu, Bivariate fluctuations for the number of arithmetic progressions in random sets, Electronic Journal of Probability 24 (2019), 13-20. MathSciNet: MR4049081 · Zbl 1428.60022
[4] B. Bhattacharya and S. Mukherjee, Replica symmetry in upper tails of mean-field hypergraphs, Adv. Appl. Math 119 (2020), 102047. MathSciNet: MR4092987 · Zbl 1434.60050
[5] B.B. Bhattacharya, S. Ganguly, X. Shao, and Y. Zhao, Upper tail large deviations for arithmetic progressions in a random set, Int. Math. Res. Not. 2020 (2020), no. 1, 167-213. MathSciNet: MR4050566 · Zbl 1478.11012
[6] B.M. Brown, Martingale central limit theorems, Ann. Math. Statist. 42 (1971), no. 1, 59-66. MathSciNet: MR0290428 · Zbl 0218.60048
[7] S. Chatterjee and A. Dembo, Nonlinear large deviations, Adv. Math. 299 (2016), 396-450. MathSciNet: MR3519474 · Zbl 1356.60045
[8] S. Chatterjee and S.R.S. Varadhan, The large deviation principle for the Erdös Rényi random graph, European J. Combin. 32 (2011), no. 7, 1000-1017. MathSciNet: MR2825532 · Zbl 1230.05259
[9] A. Dvoretzky, Asymptotic normality for sums of dependent random variables, Proc. Sixth Berkeley Symp. on Math. Statist. and Prob. 2 (1972), 513-535. MathSciNet: MR0415728 · Zbl 0256.60009
[10] R. Eldan, Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations, Geom. Funct. Anal. 28 (2018), no. 6, 1548-1596. MathSciNet: MR3881829 · Zbl 1428.60045
[11] D.A. Freedman, On tail probabilities for martingales, Ann. Probab. 3 (1975), no. 1, 100-118. MathSciNet: MR0380971 · Zbl 0313.60037
[12] 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. 373 (2020), 5517-5585. MathSciNet: MR4127885 · Zbl 1443.05172
[13] M. Harel, F. Mousset, and W. Samotij, Upper tails via high moments and entropic stability, Duke Math. J. 171 (2022), no. 10, 2089-2192. MathSciNet: MR4484206 · Zbl 1500.60002
[14] T.E. Harris, Lower bound for the critical probability in a certain percolation process, Math. Proc. Cambridge Philos. Soc. 56 (1960), 13-20. MathSciNet: MR0115221 · Zbl 0122.36403
[15] C.C. Heyde and B.M. Brown, On the departure from normality of a certain class of martingales, Ann. Math. Statist. 41 (1970), no. 6, 2161-2165. MathSciNet: MR0293702 · Zbl 0225.60026
[16] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. zbMATH: 0127.10602 MathSciNet: MR0144363 · Zbl 0127.10602
[17] S. Janson, T. Łuczak, and A. Ruciński, Random Graphs, Wiley-Interscience, New York, 2000. MathSciNet: MR1782847 · Zbl 0968.05003
[18] S. Janson and A. Ruciński, Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs, Ark. Mat. 49 (2011), no. 1, 79-96. MathSciNet: MR2784258 · Zbl 1223.05201
[19] S. Janson and L. Warnke, The lower tail: Poisson approximation revisited, Random Structures Algorithms 48 (2015), no. 2, 219-246. MathSciNet: MR3449596 · Zbl 1332.05128
[20] J.H.Kim and V.H. Vu, Concentration of multivariate polynomials and its applications, Combinatorica 20 (2000), no. 3, 417-434. MathSciNet: MR1774845 · Zbl 0969.60013
[21] J.-C. Mourrat, On the rate of convergence in the martingale central limit theorem, Bernoulli 19 (2013), no. 2, 633-645. MathSciNet: MR3037167 · Zbl 1277.60051
[22] F. Mousset, A. Noever, K. Panagiotou, and W. Samotij, On the probability of nonexistence in binomial subsets, Ann. Probab. 48 (2020), no. 1, 493-525. MathSciNet: MR4079444 · Zbl 1451.60023
[23] G. Fiz Pontiveros, S. Griffiths, M. Secco, and O. Serra, Deviation probabilities for arithmetic progressions and other regular discrete structures, Random Structures Algorithms 60 (2022), no. 3, 367-405. MathSciNet: MR4388701 · Zbl 1522.05205
[24] M. Secco, Arithmetic structures in random sets, Ph.D. thesis, PUC-Rio, 2020, Available from http://www.maxwell.vrac.puc-rio.br/49323/49323.PDF.
[25] L. Warnke, Upper tails for arithmetic progressions in random subsets, Isr. J. Math. 221 (2017), no. 1, 317-365. MathSciNet: MR3705856 · Zbl 1407.05238
[26] L. Warnke, On the missing log in upper tail estimates, J. Combin. Theory Ser. B 140 (2020), 98-146. MathSciNet: MR4033098 · Zbl 1430.05085
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.