Upper tails for arithmetic progressions in random subsets

Abstract

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.

28 pages. To appear in Israel Journal of Mathematics

References in corpus (1)

• Extremal results for random discrete structures

Cited by in corpus (17)

• Upper tails for arithmetic progressions in a random set
• Packing nearly optimal Ramsey R(3,t) graphs
• A counterexample to the DeMarco-Kahn Upper Tail Conjecture
• Gaussian width bounds with applications to arithmetic progressions in random settings
• On the missing log in upper tail estimates
• Upper tail bounds for Stars
• Prague dimension of random graphs
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• Local limit theorems for subgraph counts
• Counting extensions revisited
• Bounds on Ramsey Games via Alterations
• Number of arithmetic progressions in dense random subsets of $\mathbb{Z}/n\mathbb{Z}$
• An extension of the Erdős-Tetali theorem
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Edge sampling using network local information
• Normal limiting distributions for systems of linear equations in random sets
• Deviation probabilities for arithmetic progressions and irregular discrete structures