Deviation probabilities for arithmetic progressions and other regular discrete structures
Gonzalo Fiz Pontiveros, Simon Griffiths, Matheus Secco, Oriol Serra · Random Structures and Algorithms · 2021
Abstract Let the random variable 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 . Furthermore, we show that our main theorem is essentially best possible and we deduce results for the case is generated by including each vertex independently with probability p.