Deviation probabilities for arithmetic progressions and irregular discrete structures

0581051 - ÚI 2024 RIV US eng J - Článek v odborném periodiku
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
Grant CEP: GA ČR(CZ) GJ20-27757Y
Institucionální podpora: RVO:67985807
Klíčová slova: arithmetic progressions * hypergraphs * Martingales * Moderate deviations * Random processes
Obor OECD: Pure mathematics
Impakt faktor: 1.4, rok: 2022
Způsob publikování: 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.
Trvalý link: https://hdl.handle.net/11104/0349622