Deviation probabilities for arithmetic progressions and irregular discrete structures

0581051 - ÚI 2024 RIV US eng J - Journal Article
Griffiths, S. - Koch, Ch. - Secco, Matheus
Deviation probabilities for arithmetic progressions and irregular discrete structures.
Electronic Journal of Probability. Roč. 28, č. 2023 (2023), č. článku 172 (s. 1-31). ISSN 1083-6489. E-ISSN 1083-6489
R&D Projects: GA ČR(CZ) GJ20-27757Y
Institutional support: RVO:67985807
Keywords : arithmetic progressions * hypergraphs * Martingales * Moderate deviations * Random processes
OECD category: Pure mathematics
Impact factor: 1.4, year: 2022
Method of publishing: Open access
https://doi.org/10.1214/23-EJP1012

Let the random variable X:=e(H[B]) count the number of edges of a hypergraph H induced by a random m-element subset B of its vertex set. Focussing on the case that the degrees of vertices in 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,…,N}. Furthermore, our main theorem allows us to deduce results for the case B∼Bp is generated by including each vertex independently with probability p. In this setting our result on arithmetic progressions extends a result of Bhattacharya, Ganguly, Shao and Zhao [5]. We also mention connections to related central limit theorems.
Permanent Link: https://hdl.handle.net/11104/0349622