Deviation probabilities for arithmetic progressions and irregular discrete structures

Abstract

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.