Deviation probabilities for arithmetic progressions and other regular discrete structures. Issue 3 (28th September 2021) - Fiz Pontiveros, Gonzalo; Griffiths, Simon; Secco, Matheus; Serra, Oriol
Abstract: 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 p is generated by including each vertex independently with probability p .