Erdős Problem #195 — Monotone arithmetic progressions in permutations of the integers
For a bijection , regard the values as ordered by increasing index . A monotone -term arithmetic progression in this order means that there are indices and integers , with , such that
Thus gives increasing values and decreasing values along the selected indices. The question is to determine the largest such that every bijection has such indices and such . This is the doubly infinite ordering convention, not an enumeration indexed only by the positive integers. Erdős Problems #195 Adenwalla, Avoiding Monotone Arithmetic Progressions in Permutations of Integers (2024 preprint)
Background
This is an ordering problem: the permutation uses every integer, and the question is whether some arithmetic progression appears as a subsequence in that order. The one-sided and doubly infinite conventions matter. For example, results about enumerations of the positive integers do not by themselves describe orders indexed by all of . The problem is listed with the original references [ErGr79] and [ErGr80]; later work also studies permutations of the positive integers and restricted sets of common differences. Erdős Problems #195 Adenwalla, Avoiding Monotone Arithmetic Progressions in Permutations of Integers (2024 preprint)
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.