UPPER TAILS FOR ARITHMETIC PROGRESSIONS IN RANDOM SUBSETS

摘要

We study the upper tail of the number of arithmetic progressions of a given length in a random subset of {1,..., n}, establishing exponential bounds which are best possible up to constant factors in the exponent. The proof also extends to Schur triples, and, more generally, to the number of edges in random induced subhypergraphs of 'almost linear' k-uniform hypergraphs.