Deviation probabilities for arithmetic progressions and other regular discrete structures. Issue 3 (28th September 2021)

• Record Type: Journal Article
• Authors: Fiz Pontiveros, Gonzalo; Griffiths, Simon; Secco, Matheus; Serra, Oriol
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 367
• Page End: 405
• Publication Date: 2021-09-28
• Subjects: additive Combinatorics -- deviations -- martingales; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21044
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .