Upper tails for arithmetic progressions in a random set
arXiv:1605.02994 · doi:10.1093/imrn/rny022
Abstract
Let denote the number of -term arithmetic progressions in a random subset of or where every element is included independently with probability . We determine the asymptotics of (also known as the large deviation rate) where with for some constant , which answers a question of Chatterjee and Dembo. The proofs rely on the recent nonlinear large deviation principle of Eldan, which improved on earlier results of Chatterjee and Dembo. Our results complement those of Warnke, who used completely different methods to estimate, for the full range of , the large deviation rate up to a constant factor.
References in corpus (10)
- Applications of Stein's method for concentration inequalities
- On replica symmetry of large deviations in random graphs
- Upper tails for triangles
- Upper tails and independence polynomials in random graphs
- On the variational problem for upper tails in sparse random graphs
- Upper Tails for Cliques
- Upper tails for arithmetic progressions in random subsets
- Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
- On the lower tail variational problem for random graphs
- On the maximal number of three-term arithmetic progressions in subsets of Z/pZ
Cited by in corpus (6)
- Gaussian width bounds with applications to arithmetic progressions in random settings
- Local limit theorems for subgraph counts
- Maximising the number of solutions to a linear equation in a set of integers
- A large deviation principle for block models
- The maximal number of -term arithmetic progressions in finite sets in different geometries
- Preferential Attachment When Stable