Deviation probabilities for arithmetic progressions and other regular discrete structures

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 .