Maximal arithmetic progressions in random subsets
From MaRDI portal
Abstract: Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}^N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to an extreme type (asymmetric) distribution. The same result holds for the maximal length W(N) of arithmetic progressions (mod N). When considered in the natural way on a common probability space, we observe that U(N)/log(N) converges almost surely to 2/log(2), while W(N)/log(N) does not converge almost surely (and in particular, limsup W(N)/log(N) is at least 3/log(2)).
Recommendations
- On the maximal length of arithmetic progressions
- Upper tail large deviations for arithmetic progressions in a random set
- Upper tails for arithmetic progressions in random subsets
- Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
- Bivariate fluctuations for the number of arithmetic progressions in random sets
Cited in
(10)- The largest super-increasing subset of a random set
- Number of arithmetic progressions in dense random subsets of \(\mathbb{Z}/n\mathbb{Z}\)
- Arithmetic subsequences in a random ordering of an additive set
- Approximating dependent rare events
- Bivariate fluctuations for the number of arithmetic progressions in random sets
- On the maximal length of arithmetic progressions
- Upper tails for arithmetic progressions in random subsets
- Upper tail large deviations for arithmetic progressions in a random set
- Arithmetic progressions of length three in subsets of a random set
- ON MAXIMAL SUBSET-SUM-DISTINCT SEQUENCES
This page was built for publication: Maximal arithmetic progressions in random subsets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2461042)
