← All problems

Erdős Problem #197 — Two-set permutations avoiding monotone progressions

46 years old · traced to

Write Z+={1,2,3,…}\mathbf{Z}^{+}=\{1,2,3,\ldots\} and N0={0,1,2,…}\mathbb{N}_{0}=\{0,1,2,\ldots\}. Is there a partition Z+=A⊔B\mathbf{Z}^{+}=A\sqcup B such that each part has a bijection πA ⁣:N0→A\pi_A\colon\mathbb{N}_{0}\to A or πB ⁣:N0→B\pi_B\colon\mathbb{N}_{0}\to B, respectively, for which no three terms in increasing order of position form a monotone three-term arithmetic progression? Explicitly, for each X∈{A,B}X\in\{A,B\}, there must be no i<j<ki<j<k and a,d∈Z+a,d\in\mathbf{Z}^{+} with d>0d>0 such that

(πX(i),πX(j),πX(k))=(a,a+d,a+2d)or(a+2d,a+d,a).(\pi_X(i),\pi_X(j),\pi_X(k))=(a,a+d,a+2d) \quad\text{or}\quad (a+2d,a+d,a).

Thus each part is countably infinite as a consequence of having such a bijective sequence; this is not an additional partition hypothesis. The sequence has order type ω\omega, rather than being an arbitrary linear ordering of the set. Erdős Problem #197 Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint)

Background

The question grows out of a sharp difference between finite and infinite permutations. Davis, Entringer, Graham, and Simmons showed that every permutation of Z+\mathbf{Z}^{+} of order type ω\omega contains an increasing three-term arithmetic progression, so the whole set cannot be ordered to avoid even the increasing case. They also constructed a partition into three sets, each of which can be ordered to avoid both increasing and decreasing three-term progressions, and asked whether two sets suffice. Erdős and Graham later repeated the question, calling it “a very annoying question.” Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint)

The indexing condition is essential: an order indexed by all integers, or a general linear order, is not a bijective sequence indexed by N0\mathbb{N}_{0}. Results about those different kinds of order therefore do not directly answer this partition question. Structural rigidity in the Erdős–Graham two-set permutation problem (2026 preprint) Density bounds for permutations avoiding monotone arithmetic progressions (2026 preprint)

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

Source: 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

Never refreshed

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.