Erdős Problem #196 — Monotone arithmetic progressions in permutations
Let denote the positive integers, and let be a permutation of , meaning a bijective sequence. Must there exist indices and integers and such that
Equivalently, must every permutation of the positive integers contain a four-term arithmetic progression as a subsequence whose terms are monotone—increasing if , decreasing if ? Erdős Problem #196 Erdős and Graham (1979)
Background
Erdős and Graham raised the question in their discussion of arithmetic progressions in ordered sequences. The infinite-permutation setting differs from the finite one: their account notes that finite sets can be ordered to avoid monotone three-term progressions, whereas every permutation of the positive integers contains one. This contrast makes the four-term case a natural next question. Erdős and Graham (1979)
The elementary reason a three-term progression is unavoidable is that, after the first term , take the earliest term . The positive integer occurs somewhere in the permutation; since it exceeds , its occurrence must be later than position . Thus form an increasing three-term progression in their sequence order. On Permutations Avoiding Arithmetic Progressions (arXiv:1004.1740)
References
Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28 (1980).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.