Maximal arithmetic progressions in random subsets

DOI10.1214/ECP.V12-1321MaRDI QIDQ2461042zbMATH OpenFDO

Authors Itai Benjamini, Ariel Yadin, Ofer Zeitouni

Publication date 19 November 2007

Published in Electronic Communications in Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.3888, https://eudml.org/doc/128675

zbMATH Keywords

arithmetic progressionextreme type limit distributionrandom subset

Mathematics Subject Classification ID

Combinatorial probability (60C05) Central limit and other weak theorems (60F05)

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)).

Review text

The authors study the length of maximal progressions in a random uniform subset of \(\{0,1\}^N\). That is, let \(\xi_1,\xi_2,\dots,\xi_N\) be a random word in \(\{0,1\}^N\), chosen uniformly. Consider the random set \(\Xi_N\) of elements \(i\) such that \(\xi_i=1\). Let \(U^{(N)}\) denote the maximal length arithmetic progression in \(\Xi_N\), and let \(W^{(N)}\) denote the maximal length aperiodic arithmetic progression \(\pmod N\) in \(\Xi_N\). A consequence of the main result is that the expectation of both \(U^{(N)}\) is roughly \(2\log N/\log 2'\). They also show that the limit law of the centered version of both \(W^{(N)}\) is of the same extreme type as that of the longest run in \(\Xi_n\).

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)

• 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
• Arithmetic subsequences in a random ordering of an additive set
• Approximating dependent rare events
• On the maximal length of arithmetic progressions
• The largest super-increasing subset of a random set
• Arithmetic progressions of length three in subsets of a random set
• Upper tail large deviations for arithmetic progressions in 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)