Deviation probabilities for arithmetic progressions and other regular discrete structures

Abstract

Let $\HH$ be a $k$-uniform hypergraph on a vertex set $V$ and $B_m$ be a uniformly sampled $m$-set from $V$. Set $X$ to be the random variable given by the number of edges induced by the set $B_m$. We provide tight upperbounds (up to a constant in the exponent) for the tail distribution of $X-\exn{}{X}$ for a wide range of deviations, provided some near regularity conditions are satisfied by the hypergraph $\HH$. In particular, the bounds may be applied to the setting of arithmetic progressions and more generally to solutions of linear systems.