Premium
Deviation probabilities for arithmetic progressions and other regular discrete structures
Author(s) -
Fiz Pontiveros Gonzalo,
Griffiths Simon,
Secco Matheus,
Serra Oriol
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21044
Subject(s) - mathematics , vertex (graph theory) , hypergraph , combinatorics , discrete mathematics , set (abstract data type) , expected value , arithmetic progression , random variable , element (criminal law) , statistics , computer science , graph , political science , law , programming language
Let the random variable X : = e ( ℋ [ B ] ) count the number of edges of a hypergraph ℋ induced by a random m element subset B of its vertex set. Focussing on the case that ℋ satisfies some regularity condition 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 the cyclic groupℤ N. Furthermore, we show that our main theorem is essentially best possible and we deduce results for the case B ∼ B pis generated by including each vertex independently with probability p .